Document Open Access Logo

Local Hamiltonians with No Low-Energy Stabilizer States

Authors Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

Nolan J. Coble
  • Joint Center for Quantum Information and Computer Science (QuICS), Department of Computer Science, University of Maryland, College Park, MD, USA
Matthew Coudron
  • Joint Center for Quantum Information and Computer Science (QuICS), Department of Computer Science, University of Maryland, College Park, MD, USA
  • National Institute of Standards and Technology, Gaithersburg, MD, USA
Jon Nelson
  • Joint Center for Quantum Information and Computer Science (QuICS), Department of Computer Science, University of Maryland, College Park, MD, USA
Seyed Sajjad Nezhadi
  • Joint Center for Quantum Information and Computer Science (QuICS), Department of Computer Science, University of Maryland, College Park, MD, USA

Acknowledgements

This paper is a contribution of NIST, an agency of the US government, and is not subject to US copyright. We thank Alexander Barg and Chinmay Nirkhe for helpful discussions.

Cite AsGet BibTex

Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. Local Hamiltonians with No Low-Energy Stabilizer States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.TQC.2023.14

Abstract

The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [Sevag Gharibian and François {Le Gall}, 2022] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [Anshu et al., 2022], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Hamiltonian complexity
  • Stabilizer codes
  • Low-energy states

Metrics

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

Related Versions

References

  1. Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The Detectability Lemma and Quantum Gap Amplification, November 2008. arXiv:0811.3412 [cond-mat, physics:quant-ph]. URL: http://arxiv.org/abs/0811.3412.
  2. Dorit Aharonov, Itai Arad, and Thomas Vidick. The Quantum PCP Conjecture, September 2013. arXiv: 1309.7495. URL: http://arxiv.org/abs/1309.7495.
  3. Dorit Aharonov and Tomer Naveh. Quantum NP - A Survey, October 2002. arXiv:quant-ph/0210077. URL: http://arxiv.org/abs/quant-ph/0210077.
  4. Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, June 2022. number: arXiv:2206.13228 arXiv:2206.13228 [cond-mat, physics:quant-ph]. URL: http://arxiv.org/abs/2206.13228.
  5. Anurag Anshu and Nikolas P. Breuckmann. A construction of Combinatorial NLTS, June 2022. number: arXiv:2206.02741 arXiv:2206.02741 [quant-ph]. URL: http://arxiv.org/abs/2206.02741.
  6. Anurag Anshu and Chinmay Nirkhe. Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.6.
  7. S. Arora and S. Safra. Probabilistic checking of proofs; a new characterization of NP. In Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, PA, USA, 1992. IEEE. URL: https://doi.org/10.1109/SFCS.1992.267824.
  8. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998. URL: https://doi.org/10.1145/278298.278306.
  9. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159-163, October 2018. URL: https://doi.org/10.1038/s41567-018-0318-2.
  10. S. Bravyi and M. Vyalyi. Commutative version of the k-local Hamiltonian problem and common eigenspace problem, December 2004. arXiv:quant-ph/0308021. URL: http://arxiv.org/abs/quant-ph/0308021.
  11. Sergey Bravyi and David Gosset. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Physical Review Letters, 116(25):250501, June 2016. URL: https://doi.org/10.1103/PhysRevLett.116.250501.
  12. A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane. Quantum Error Correction and Orthogonal Geometry. Physical Review Letters, 78(3):405-408, January 1997. URL: https://doi.org/10.1103/PhysRevLett.78.405.
  13. A.R. Calderbank, E.M. Rains, P.M. Shor, and N.J.A. Sloane. Quantum error correction via codes over GF(4). IEEE Transactions on Information Theory, 44(4):1369-1387, July 1998. URL: https://doi.org/10.1109/18.681315.
  14. M. H. Freedman and M. B. Hastings. Quantum Systems on Non-k-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs, July 2013. arXiv:1301.1363 [quant-ph]. URL: http://arxiv.org/abs/1301.1363.
  15. Héctor J. García, Igor L. Markov, and Andrew W. Cross. On the Geometry of Stabilizer States, November 2017. arXiv:1711.07848 [quant-ph]. URL: http://arxiv.org/abs/1711.07848.
  16. Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 19-32, June 2022. arXiv:2111.09079 [quant-ph]. URL: https://doi.org/10.1145/3519935.3519991.
  17. Daniel Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound. Physical Review A, 54(3):1862-1868, September 1996. URL: https://doi.org/10.1103/PhysRevA.54.1862.
  18. Daniel Gottesman. The Heisenberg Representation of Quantum Computers, July 1998. arXiv:quant-ph/9807006. URL: http://arxiv.org/abs/quant-ph/9807006.
  19. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, May 2002. URL: https://doi.org/10.1090/gsm/047.
  20. Anthony Leverrier and Gilles Zémor. Quantum Tanner codes, April 2022. number: arXiv:2202.13641 arXiv:2202.13641 [quant-ph]. URL: http://arxiv.org/abs/2202.13641.
  21. Ramis Movassagh. Quantum supremacy and random circuits, 2019. URL: https://doi.org/10.48550/ARXIV.1909.06210.
  22. Jordi Weggemans, Marten Folkertsma, and Chris Cade. Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture, 2023. URL: https://doi.org/10.48550/ARXIV.2302.11578.
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