Document Open Access Logo

On the Complexity of Two Dimensional Commuting Local Hamiltonians

Authors Dorit Aharonov, Oded Kenneth, Itamar Vigdorovich

PDF
Thumbnail PDF

File

LIPIcs.TQC.2018.2.pdf
  • Filesize: 1 MB
  • 21 pages

Document Identifiers

Author Details

Dorit Aharonov
  • School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel
Oded Kenneth
  • School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel
Itamar Vigdorovich
  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

Funding

The authors are grateful for the generous funding of the ERC grant number 280157, and of the Simon grant number 385590

Cite As Get BibTex

Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. On the Complexity of Two Dimensional Commuting Local Hamiltonians. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TQC.2018.2

Abstract

The complexity of the commuting local Hamiltonians (CLH) problem still remains a mystery after two decades of research of quantum Hamiltonian complexity; it is only known to be contained in NP for few low parameters. Of particular interest is the tightly related question of understanding whether groundstates of CLHs can be generated by efficient quantum circuits. The two problems touch upon conceptual, physical and computational questions, including the centrality of non-commutation in quantum mechanics, quantum PCP and the area law. It is natural to try to address first the more physical case of CLHs embedded on a 2D lattice, but this problem too remained open apart from some very specific cases [Aharonov and Eldar, 2011; Hastings, 2012; Schuch, 2011]. Here we consider a wide class of two dimensional CLH instances; these are k-local CLHs, for any constant k; they are defined on qubits set on the edges of any surface complex, where we require that this surface complex is not too far from being "Euclidean". Each vertex and each face can be associated with an arbitrary term (as long as the terms commute). We show that this class is in NP, and moreover that the groundstates have an efficient quantum circuit that prepares them. This result subsumes that of Schuch [Schuch, 2011] which regarded the special case of 4-local Hamiltonians on a grid with qubits, and by that it removes the mysterious feature of Schuch's proof which showed containment in NP without providing a quantum circuit for the groundstate and considerably generalizes it. We believe this work and the tools we develop make a significant step towards showing that 2D CLHs are in NP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • local Hamiltonian complexity
  • commuting Hamiltonians
  • local Hamiltonian problem
  • trivial states
  • toric code
  • ground states
  • quantum NP
  • QMA
  • topological order
  • multiparticle entanglement
  • logical operators
  • ribbon

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miguel Aguado and Guifre Vidal. Entanglement renormalization and topological order. Physical review letters, 100(7):070404, 2008. Google Scholar
  2. Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The detectability lemma and quantum gap amplification. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 417-426. ACM, 2009. Google Scholar
  3. Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum pcp conjecture. Acm sigact news, 44(2):47-79, 2013. Google Scholar
  4. Dorit Aharonov and Lior Eldar. On the complexity of commuting local hamiltonians, and tight conditions for topological order in such systems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 334-343. IEEE, 2011. Google Scholar
  5. Dorit Aharonov and Lior Eldar. The commuting local hamiltonian problem on locally expanding graphs is approximable in $$1mathsf NP np. Quantum Information Processing, 14(1):83-101, 2015. Google Scholar
  6. Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. On the complexity of two dimensional commuting local hamiltonians. arXiv preprint arXiv:1803.02213, 2018. Google Scholar
  7. Dorit Aharonov and Tomer Naveh. Quantum np-a survey. arXiv preprint quant-ph/0210077, 2002. Google Scholar
  8. S Bravyi, MB Hastings, and F Verstraete. Lieb-robinson bounds and the generation of correlations and topological quantum order. Physical review letters, 97(5):050401, 2006. Google Scholar
  9. Sergey Bravyi and Mikhail Vyalyi. Commutative version of the k-local hamiltonian problem and common eigenspace problem. arXiv preprint quant-ph/0308021, 2003. Google Scholar
  10. Sergey B Bravyi and A Yu Kitaev. Quantum codes on a lattice with boundary. arXiv preprint quant-ph/9811052, 1998. Google Scholar
  11. Dmitri Burago, Yurĭ Dmitrievich Burago, and Sergeĭ Ivanov. A course in metric geometry. American Mathematical Society, 2001. URL: http://dx.doi.org/10.1090/gsm/033.
  12. Reinhard Diestel. Graph theory. Springer Publishing Company, Incorporated, 2017. Google Scholar
  13. Michael H Freedman and Matthew B Hastings. Quantum systems on non-k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs. arXiv preprint arXiv:1301.1363, 2013. Google Scholar
  14. David Gosset, Jenish C Mehta, and Thomas Vidick. Qcma hardness of ground space connectivity for commuting hamiltonians. Quantum, 1:16, 2017. Google Scholar
  15. Jonathan L Gross, Jay Yellen, and Ping Zhang. Handbook of graph theory. Chapman and Hall/CRC, 2013. Google Scholar
  16. Larry Guth and Alexander Lubotzky. Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. Journal of Mathematical Physics, 55(8):082202, 2014. Google Scholar
  17. Matthew B Hastings. Matrix product operators and central elements: Classical description of a quantum state. Geometry &Topology Monographs, 18(115-160):276, 2012. Google Scholar
  18. Matthew B Hastings. Trivial low energy states for commuting hamiltonians, and the quantum pcp conjecture. arXiv preprint arXiv:1201.3387, 2012. Google Scholar
  19. Allen Hatcher. Algebraic topology. Cambridge University Press, 2002. Google Scholar
  20. A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. Google Scholar
  21. Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47 in Graduate studies in mathematics. American Mathematical Soc., 2002. Google Scholar
  22. Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians. Nature Physics, 11(7):566, 2015. Google Scholar
  23. Leonid Anatolevich Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115-116, 1973. Google Scholar
  24. Norbert Schuch. Complexity of commuting hamiltonians on a square lattice of qubits. arXiv preprint arXiv:1105.2843, 2011. Google Scholar
  25. Richard Evan Schwartz. Mostly surfaces, volume 60. American Mathematical Soc., 2011. Google Scholar
  26. Masamichi Takesaki. Theory of operator algebras. i. reprint of the first (1979) edition. encyclopaedia of mathematical sciences, 124. operator algebras and noncommutative geometry, 5, 2002. Google Scholar
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