Document Open Access Logo

The Importance of the Spectral Gap in Estimating Ground-State Energies

Authors Abhinav Deshpande , Alexey V. Gorshkov , Bill Fefferman

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.54.pdf
  • Filesize: 0.52 MB
  • 6 pages

Document Identifiers

Author Details

Abhinav Deshpande
  • Joint Center for Quantum Information and Computer Science and Joint Quantum Institute, NIST/University of Maryland, College Park, MD, USA
  • Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA
Alexey V. Gorshkov
  • Joint Center for Quantum Information and Computer Science and Joint Quantum Institute, NIST/University of Maryland, College Park, MD, USA
Bill Fefferman
  • Department of Computer Science, University of Chicago, IL, USA

Funding

A. D. and A. V. G. acknowledge funding by the DoE ASCR Quantum Testbed Pathfinder program (award No. DE-SC0019040), DoE QSA, NSF QLCI, U.S. Department of Energy Award No. DE-SC0019449, DoE ASCR Accelerated Research in Quantum Computing program (award No. DE-SC0020312), NSF PFCQC program, AFOSR, ARO MURI, AFOSR MURI, and DARPA SAVaNT ADVENT. A. D. also acknowledges support from NSF RAISE/TAQS 1839204. B. F. acknowledges support from AFOSR (YIP number FA9550-18-1-0148 and FA9550-21-1-0008). This material is based upon work partially supported by the National Science Foundation under Grant CCF- 2044923 (CAREER) and by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers. The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center PHY-1733907.

Acknowledgements

We thank Sevag Gharibian, Hosho Katsura, Cedric Lin, Yupan Liu, Zachary Remscrim, and an anonymous referee for useful feedback on the manuscript and Peter Love, Yuan Su, Minh Tran, and Seth Whitsitt for helpful discussions.

Cite As Get BibTex

Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The Importance of the Spectral Gap in Estimating Ground-State Energies. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 54:1-54:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.54

Abstract

The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the Local Hamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the Local Hamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the Local Hamiltonian problem is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics.
In the setting of inverse-exponential precision (promise gap), there is a surprising result that the complexity of Local Hamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space (but possibly exponential time). We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Local Hamiltonian problem
  • PSPACE
  • PP
  • QMA

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. Math. Phys. Eng. Sci., 461(2063):3473-3482, 2005. URL: https://doi.org/10.1098/rspa.2005.1546.
  2. Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. Theory Comput., 3(1):129-157, 2007. URL: https://doi.org/10.4086/toc.2007.v003a007.
  3. Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandao, and Or Sattath. The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings. CoRR, 2008. URL: http://arxiv.org/abs/0810.4840.
  4. Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of quantum systems on a line. Commun. Math. Phys., 287(1):41-65, 2009. URL: https://doi.org/10.1007/s00220-008-0710-3.
  5. Sergey Bravyi, David DiVincenzo, and Daniel Loss. Schrieffer-Wolff transformation for quantum many-body systems. Ann. Phys., 326(10):2793-2826, 2011. URL: https://doi.org/10.1016/j.aop.2011.06.004.
  6. Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal. The Complexity of Stoquastic Local Hamiltonian Problems. Quantum Inf. Comput., 8(5):0361-0385, 2008. Google Scholar
  7. Jacob C. Bridgeman and Christopher T. Chubb. Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks. J. Phys. Math. Theor., 50(22):223001, 2017. URL: https://doi.org/10.1088/1751-8121/aa6dc3.
  8. Elizabeth Crosson and John Bowen. Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians. CoRR, 2018. URL: http://arxiv.org/abs/1703.10133.
  9. Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The importance of the spectral gap in estimating ground-state energies. CoRR, 2020. URL: http://arxiv.org/abs/2007.11582.
  10. Bill Fefferman and Shelby Kimmel. Quantum vs. Classical proofs and subset verification. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 22:1-22:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.22.
  11. Bill Fefferman and Cedric Yen-Yu Lin. Quantum Merlin Arthur with Exponentially Small Gap. CoRR, 2016. URL: http://arxiv.org/abs/1601.01975.
  12. Bill Fefferman and Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quantum Space. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:21, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPICS.ITCS.2018.4.
  13. Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPICS.MFCS.2018.58.
  14. Carlos E. González-Guillén and Toby S. Cubitt. History-state Hamiltonians are critical. CoRR, 2018. URL: http://arxiv.org/abs/1810.06528.
  15. Daniel Gottesman and Sandy Irani. The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. CoRR, 2009. URL: http://arxiv.org/abs/0905.2419.
  16. M. B. Hastings. An area law for one-dimensional quantum systems. J. Stat. Mech., 2007(08):P08024, 2007. URL: https://doi.org/10.1088/1742-5468/2007/08/P08024.
  17. Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang. On the Power of a Unique Quantum Witness. Theory Comput., 8(1):375-400, 2012. URL: https://doi.org/10.4086/toc.2012.v008a017.
  18. Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum Algorithms for Quantum Field Theories. Science, 336(6085):1130-1133, 2012. URL: https://doi.org/10.1126/science.1217069.
  19. Julia Kempe and Oded Regev. 3-local Hamitonian is QMA-complete. Quantum Inf. Comput., 3(3):258-264, 2003. URL: http://arxiv.org/abs/quant-ph/0302079.
  20. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2002. URL: https://doi.org/10.1090/gsm/047.
  21. Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nat. Phys., 11(7):566-569, 2015. URL: https://doi.org/10.1038/nphys3345.
  22. Chris Marriott and John Watrous. Quantum ArthurendashMerlin games. Comput. Complex., 14(2):122-152, 2005. URL: https://doi.org/10.1007/s00037-005-0194-x.
  23. Tomoyuki Morimae and Harumichi Nishimura. Merlinization of complexity classes above BQP. Quantum Inf. Comput., 17(11endash 12):959-972, 2017. URL: http://arxiv.org/abs/1704.01514.
  24. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Inf. Comput., 9(11):1053-1068, 2009. URL: http://arxiv.org/abs/0904.1549.
  25. Roberto Oliveira and Barbara M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):0900-0924, 2008. URL: http://arxiv.org/abs/quant-ph/0504050.
  26. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun., 5(1):4213, 2014. URL: https://doi.org/10.1038/ncomms5213.
  27. J. R. Schrieffer and P. A. Wolff. Relation between the Anderson and Kondo Hamiltonians. Phys. Rev., 149(2):491-492, 1966. URL: https://doi.org/10.1103/PhysRev.149.491.
  28. Christopher David White, ChunJun Cao, and Brian Swingle. Conformal field theories are magical. CoRR, 2020. URL: http://arxiv.org/abs/2007.01303.
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