Search Results

Documents authored by Thompson, Kevin

Document
DOI: 10.4230/LIPIcs.TQC.2023.6
Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians

Authors: Daniel Hothem, Ojas Parekh, and Kevin Thompson

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We give a classical 1/(qk+1)-approximation for the maximum eigenvalue of a k-sparse fermionic Hamiltonian with strictly q-local terms, as well as a 1/(4k+1)-approximation when the Hamiltonian has both 2-local and 4-local terms. More generally we obtain a 1/O(qk²)-approximation for k-sparse fermionic Hamiltonians with terms of locality at most q. Our techniques also yield analogous approximations for k-sparse, q-local qubit Hamiltonians with small hidden constants and improved dependence on q.
Cite as

Daniel Hothem, Ojas Parekh, and Kevin Thompson. Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hothem_et_al:LIPIcs.TQC.2023.6,
  author =	{Hothem, Daniel and Parekh, Ojas and Thompson, Kevin},
  title =	{{Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.6},
  URN =		{urn:nbn:de:0030-drops-183163},
  doi =		{10.4230/LIPIcs.TQC.2023.6},
  annote =	{Keywords: Approximation algorithms, Extremal eigenvalues, Sparse Hamiltonians, Fermionic Hamiltonians, Qubit Hamiltonians}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.74
Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

Authors: Ojas Parekh and Kevin Thompson

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
Cite as

Ojas Parekh and Kevin Thompson. Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{parekh_et_al:LIPIcs.ESA.2021.74,
  author =	{Parekh, Ojas and Thompson, Kevin},
  title =	{{Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.74},
  URN =		{urn:nbn:de:0030-drops-146554},
  doi =		{10.4230/LIPIcs.ESA.2021.74},
  annote =	{Keywords: Quantum Approximation Algorithms, Local Hamiltonian}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.102
Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

Authors: Ojas Parekh and Kevin Thompson

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-2 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-2 hierarchy satisfies many physically-motivated constraints that the level-1 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.
Cite as

Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{parekh_et_al:LIPIcs.ICALP.2021.102,
  author =	{Parekh, Ojas and Thompson, Kevin},
  title =	{{Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.102},
  URN =		{urn:nbn:de:0030-drops-141718},
  doi =		{10.4230/LIPIcs.ICALP.2021.102},
  annote =	{Keywords: Quantum Max Cut, Quantum Approximation Algorithms, Lasserre Hierarchy, Local Hamiltonian, Heisenberg model}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact