Document Open Access Logo

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians

Authors Sevag Gharibian, Stephen Piddock, Justin Yirka

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2020.20.pdf
  • Filesize: 0.76 MB
  • 37 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Merlin Arthur (QMA)
  • simulation of local measurement
  • local Hamiltonian
  • oracle complexity class
  • physical Hamiltonians

Metrics

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

Abstract

The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results.
Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model:  
- We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. 
- Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. 
- Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. 
Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.

Cite As Get BibTex

Sevag Gharibian, Stephen Piddock, and Justin Yirka. Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 20:1-20:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.20

Author Details

Sevag Gharibian
  • Paderborn University, Paderborn, Germany
Stephen Piddock
  • University of Bristol, Bristol, UK
Justin Yirka
  • The University of Texas at Austin, Austin, TX, USA

Funding

  • Gharibian, Sevag: SG acknowledges support from NSF grants CCF-1526189 and CCF-1617710.
  • Piddock, Stephen: SP was supported by EPSRC.
  • Yirka, Justin: Part of this work was completed while JY was supported by a Virginia Commonwealth University Presidential Scholarship. JY acknowledges QIP 2019 student travel funding (NSF CCF-1840547).

Acknowledgements

We are grateful to Thomas Vidick for helpful discussions which helped initiate this work. We also thank an anonymous referee for [S. Gharibian and J. Yirka, 2018] (written by two of the present authors) for the suggestion to think about 1D systems.

References

  1. D. Aharonov, D. Gottesman, S. Irani, and J. Kempe. The power of quantum systems on a line. Communications in Mathematical Physics, 287(1):41-65, 2009. URL: https://doi.org/10.1007/s00220-008-0710-3.
  2. D. Aharonov and T. Naveh. Quantum NP - A survey. Available at arXiv:quant-ph/0210077v1, 2002. Google Scholar
  3. A. Ambainis. On physical problems that are slightly more difficult than QMA. In Proceedings of 29th IEEE Conference on Computational Complexity (CCC), pages 32-43, 2014. URL: https://doi.org/10.1109/ccc.2014.12.
  4. J. Bausch, T. Cubitt, and M. Ozols. The complexity of translationally invariant spin chains with low local dimension. Annales Henri Poincaré, 18(11):3449-3513, 2017. URL: https://doi.org/10.1007/s00023-017-0609-7.
  5. R. Beigel. Bounded queries to SAT and the Boolean hierarchy. Theoretical computer science, 84(2):199-223, 1991. URL: https://doi.org/10.1016/0304-3975(91)90160-4.
  6. A. D. Bookatz. QMA-complete problems. Quantum Information & Computation, 14(5-6):361-383, 2014. URL: https://doi.org/10.26421/QIC14.5-6.
  7. S. Bravyi and M. Hastings. On complexity of the quantum Ising model. Communications in Mathematical Physics, 349(1):1-45, 2017. URL: https://doi.org/10.1007/s00220-016-2787-4.
  8. Sergey Bravyi, David P. DiVincenzo, and Daniel Loss. Schrieffer–Wolff transformation for quantum many-body systems. Annals of Physics, 326(10):2793-2826, 2011. URL: https://doi.org/10.1016/j.aop.2011.06.004.
  9. B. Brown, S. Flammia, and N. Schuch. Computational difficulty of computing the density of states. Physical Review Letters, 107(4):040501, 2011. URL: https://doi.org/10.1103/physrevlett.107.040501.
  10. S. Buss and L. Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86-102, 1991. URL: https://doi.org/10.1016/0890-5401(91)90075-D.
  11. S. Cook. The complexity of theorem proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC), pages 151-158, 1972. URL: https://doi.org/10.1145/800157.805047.
  12. T. Cubitt and A. Montanaro. Complexity classification of local Hamiltonian problems. SIAM J. Comput., 45(2):268-316, 2016. URL: https://doi.org/10.1137/140998287.
  13. T. Cubitt, A. Montanaro, and S. Piddock. Universal quantum Hamiltonians. Proceedings of the National Academy of Sciences, 115(38):9497-9502, 2018. URL: https://doi.org/10.1073/pnas.1804949115.
  14. T. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528:207-211, 2015. URL: https://doi.org/10.1038/nature16059.
  15. G. De las Cuevas and T. Cubitt. Simple universal models capture all classical spin physics. Science, 351(6278):1180-1183, 2016. URL: https://doi.org/10.1126/science.aab3326.
  16. C. A. Fuchs and J. van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216-1227, 1999. URL: https://doi.org/10.1109/18.761271.
  17. J. Gao. Quantum union bounds for sequential projective measurements. Phys. Rev. A, 92(5):052331, 2015. URL: https://doi.org/10.1103/PhysRevA.92.052331.
  18. S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin. Quantum Hamiltonian complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159-282, 2015. URL: https://doi.org/10.1561/0400000066.
  19. S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. In Automata, Languages and Programming, volume 7319 of Lecture Notes in Computer Science, pages 387-398, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-31594-7_33.
  20. S. Gharibian, Z. Landau, S. W. Shin, and G. Wang. Tensor network non-zero testing. Quantum Information & Computation, 15(9-10):885-899, 2015. URL: https://doi.org/10.26421/QIC15.9-10.
  21. S. Gharibian and J. Sikora. Ground state connectivity of local Hamiltonians. ACM Transactions on Computation Theory, 10(2), 2018. URL: https://doi.org/10.1145/3186587.
  22. S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. In M. M. Wilde, editor, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl. URL: https://doi.org/10.4230/LIPIcs.TQC.2017.2.
  23. O. Goldreich. On promise problems: A survey. In O. Goldreich, A.L. Rosenberg, and A.L. Selman, editors, Theoretical Computer Science, volume 3895 of Lecture Notes in Computer Science, pages 254-290. Springer, Berlin, Heidelberg, 2006. URL: https://doi.org/10.1007/11685654_12.
  24. D. Gosset, J. C. Mehta, and T. Vidick. QCMA hardness of ground space connectivity for commuting Hamiltonians. Quantum, 1:16, 2017. URL: https://doi.org/10.22331/q-2017-07-14-16.
  25. D. Gottesman and S. Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Theory of Computing, 9(2):31-116, 2013. URL: https://doi.org/10.4086/toc.2013.v009a002.
  26. S. Hallgren, D. Nagaj, and S. Narayanaswami. The local Hamiltonian problem on a line with eight states is QMA-complete. Quantum Information & Computation, 13(9-10):721-750, 2013. URL: https://doi.org/10.26421/QIC13.9-10.
  27. L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299-322, 1989. URL: https://doi.org/10.1016/0022-0000(89)90025-1.
  28. J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. SIAM Journal on Computing, 35(5):1070-1097, 2006. URL: https://doi.org/10.1137/s0097539704445226.
  29. J. Kempe and O. Regev. 3-local Hamiltonian is QMA-complete. Quantum Information & Computation, 3(3):258-264, 2003. URL: https://doi.org/10.26421/QIC3.3.
  30. I. H. Kim. Markovian matrix product density operators : Efficient computation of global entropy. Available at arXiv:1709.07828v2 [quant-ph], 2017. Google Scholar
  31. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. Google Scholar
  32. A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pages 608-617, 2000. URL: https://doi.org/10.1145/335305.335387.
  33. L. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265-266, 1973. Google Scholar
  34. C. Marriott and J. Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, 2005. URL: https://doi.org/10.1007/s00037-005-0194-x.
  35. D. Nagaj. Local Hamiltonians in quantum computation. PhD thesis, Massachusetts Institute of Technology, 2008. Available at arXiv:0808.2117v1 [quant-ph]. Google Scholar
  36. R. Oliveira and B. M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation, 8(10):900-924, 2008. URL: https://doi.org/10.26421/QIC8.10.
  37. T. J. Osborne. Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001, 2012. URL: https://doi.org/10.1088/0034-4885/75/2/022001.
  38. S. K. Oskouei, S. Mancini, and M. M. Wilde. Union bound for quantum information processing. Proceedings of the Royal Society A, 475(2221), 2019. URL: https://doi.org/10.1098/rspa.2018.0612.
  39. S. Piddock and A. Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. Quantum Information & Computation, 17(7&8):636-672, 2017. URL: https://doi.org/10.26421/QIC17.7-8.
  40. S. Piddock and A. Montanaro. Universal qudit Hamiltonians. Available at arXiv:1802.07130v1 [quant-ph], 2018. Google Scholar
  41. G. Scarpa, A. Molnar, Y. Ge, J. J. Garcia-Ripoll, N. Schuch, D. Perez-Garcia, and S. Iblisdir. Computational complexity of PEPS zero testing. Available at arXiv1802.08214 [quant-ph], 2018. Google Scholar
  42. N. Schuch and F. Verstraete. Computational complexity of interacting electrons and fundamental limitations of Density Functional Theory. Nature Physics, 5:732-735, 2009. URL: https://doi.org/10.1038/nphys1370.
  43. P. Sen. Achieving the Han-Kobayashi inner bound for the quantum interference channel. In Proceedings of the 2012 IEEE International Symposium on Information Theory, pages 736-740, 2012. URL: https://doi.org/10.1109/ISIT.2012.6284656.
  44. Y. Shi and S. Zhang. Note on quantum counting classes. Available at URL: http://www.cse.cuhk.edu.hk/syzhang/papers/SharpBQP.pdf.
  45. M. Vyalyi. QMA=PP implies that PP contains PH. Available at Electronic Colloquium on Computational Complexity (ECCC), 2003. Google Scholar
  46. K.W. Wagner. Bounded query computations. In Proceedings of Structure in Complexity Theory Third Annual Conference, pages 260-277, 1988. URL: https://doi.org/10.1109/SCT.1988.5286.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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