Search Results

Documents authored by Hallgren, Sean

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.59
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Authors: Sean Hallgren, Eunou Lee, and Ojas Parekh

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.
Cite as

Sean Hallgren, Eunou Lee, and Ojas Parekh. An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hallgren_et_al:LIPIcs.APPROX/RANDOM.2020.59,
  author =	{Hallgren, Sean and Lee, Eunou and Parekh, Ojas},
  title =	{{An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.59},
  URN =		{urn:nbn:de:0030-drops-126629},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.59},
  annote =	{Keywords: approximation algorithm, quantum computing, local Hamiltonian, mean-field theory, randomized rounding}
}
Document
DOI: 10.4230/LIPIcs.TQC.2016.6
How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?

Authors: Nai-Hui Chia and Sean Hallgren

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

Abstract
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density > 1 and also to quantum sampling subset sum solutions. We examine a decision version of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density >1. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density >1 but approaching 1 as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.
Cite as

Nai-Hui Chia and Sean Hallgren. How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.TQC.2016.6,
  author =	{Chia, Nai-Hui and Hallgren, Sean},
  title =	{{How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.6},
  URN =		{urn:nbn:de:0030-drops-66877},
  doi =		{10.4230/LIPIcs.TQC.2016.6},
  annote =	{Keywords: Quantum algorithms, hidden subgroup problem, random subset sum problem}
}
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 About DROPS Imprint Privacy Contact