# The complexity of simulating local measurements on quantum systems

Sevag Gharibian1,3 and Justin Yirka2,3

1Department of Computer Science, Paderborn University, Germany
2Department of Computer Science, The University of Texas at Austin, USA
3Department of Computer Science, Virginia Commonwealth University, USA

### Abstract

An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class ${P}^{{QMA}[{log}]}$, and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is ${P}^{{QMA}[{log}]}$-complete. In this paper, we continue the study of ${P}^{{QMA}[{log}]}$, obtaining the following lower and upper bounds.

Lower bounds (hardness results):

- The ${P}^{{QMA}[{log}]}$-completeness result of [Ambainis, CCC 2014] requires $O(\log n)$-local observables and Hamiltonians. We show that simulating even a $\textit{single qubit}$ measurement on ground states of $5$-local Hamiltonians is ${P}^{{QMA}[{log}]}$-complete, resolving an open question of Ambainis.

- We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly ${P}^{{QMA}[{log}]}$-complete.

- We identify a flaw in [Ambainis, CCC 2014] regarding a ${P}^{{UQMA}[{log}]}$-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a query validation'' technique, we build on [Ambainis, CCC 2014] to obtain ${P}^{{UQMA}[{log}]}$-hardness for estimating spectral gaps under polynomial-time Turing reductions.

Upper bounds (containment in complexity classes):

- ${P}^{{QMA}[{log}]}$ is thought of as slightly harder'' than QMA. We justify this formally by exploiting the hierarchical voting technique of [Beigel, Hemachandra, Wechsung, SCT 1989] to show ${P}^{{QMA}[{log}]}\subseteq {PP}$. This improves the containment ${QMA}\subseteq {PP}$ [Kitaev, Watrous, STOC 2000].

This work contributes a rigorous treatment of the subtlety involved in studying oracle classes in which the oracle solves a $promise$ problem. This is particularly relevant for quantum complexity theory, where most natural classes such as BQP and QMA are defined as promise classes.

A central question in quantum physics is how many-body systems behave when cooled to near absolute zero. This regime is of particular interest, since it is where phenomena such as superconductivity and superfluidity manifest themselves. If our goal is to understand the $behavior$ of such states, we must probe the properties of the $\textit{ground state}$ of the system, meaning the lowest energy configuration the system relaxes into at low temperature. The most natural avenue for achieving this is to perform local measurements on said ground state, raising the obvious physically motivated question: How difficult is it to simulate such a measurement?

It turns out that the right place to look for the answer is not where the field of quantum Hamiltonian complexity has typically concentrated its effort, Quantum Merlin Arthur (where QMA can be thought of as a “quantum NP”). Rather, Ambainis showed [Ambainis, CCC 2014] that the task of simulating local measurements on ground states is $\textit{even harder than QMA}$, and is characterized by the class PQMA[log] (i.e. the problem is PQMA[log]-complete). Intuitively, this means the problem is believed intractable: the minimal resources to solve it are a classical polynomial-time machine augmented with the “magic” ability to solve a logarithmic number of QMA problems.

The current work continues the study of PQMA[log] and additionally gives a gentle introduction to the topic for the interested reader. We show a variety of results, including (roughly): (1) Showing the problem of simulating measurements on ground states remains PQMA[log]-hard even for more physically motivated settings, such as measurements of just a single qubit of the ground state (as opposed to logarithmically many qubits as in [Ambainis, CCC 2014]). (2) We identify and correct a flaw in the treatment of oracles for promise problems from [Ambainis, CCC 2014] and give a corrected, significantly modified proof of an important result therein, namely for the problem of estimating $\textit{spectral gaps}$ of local Hamiltonians. (3) We show, in a rigorous sense, that while being harder than QMA, PQMA[log] is not $\textit{too much harder}$ (in the formal sense that the latter is still contained in the complexity class PP).

One of the main contributions of this work is a rigorous treatment of the subtlety involved in studying oracle classes in which the oracle solves a promise problem, such as PQMA[log]. This is particularly relevant for quantum complexity theory, where natural classes such as BQP and QMA are defined as promise classes.

### ► References

[1] S. Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd ACM Symposium on the Theory of Computing (STOC 2010), pages 141–150, 2010. 10.1145/​1806689.1806711.
https:/​/​doi.org/​10.1145/​1806689.1806711

[2] D. Aharonov and T. Naveh. Quantum NP - A survey. Available at arXiv:quant-ph/​0210077v1, 2002.
arXiv:quant-ph/0210077v1

[3] D. Aharonov and L. Zhou. Hamiltonian sparsification and gap-simulations. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:21. Dagstuhl Publishing, 2018. 10.4230/​LIPIcs.ITCS.2019.2.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2019.2

[4] D. Aharonov, M. Ben-Or, F. Brandão, and O. Sattath. The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings. Available at arXiv:0810.4840v1 [quant-ph], 2008.
arXiv:0810.4840v1

[5] 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. 10.1109/​ccc.2014.12.
https:/​/​doi.org/​10.1109/​ccc.2014.12

[6] J. Bausch and E. Crosson. Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum, 2: 94, 2018. 10.22331/​q-2018-09-19-94.
https:/​/​doi.org/​10.22331/​q-2018-09-19-94

[7] 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. 10.1007/​s00023-017-0609-7.
https:/​/​doi.org/​10.1007/​s00023-017-0609-7

[8] J. Bausch, T. Cubitt, A. Lucia, and D. Perez-Garcia. Undecidability of the spectral gap in one dimension. Available at arXiv:1810.01858v1 [quant-ph], 2018.
arXiv:1810.01858v1

[9] R. Beigel, L. A. Hemachandra, and G. Wechsung. On the power of probabilistic polynomial time: ${\rm P^{NP[log]}\subseteq PP}$. In Proceedings of the 4th IEEE Conference on Structure in Complexity Theory, pages 225–227, 1989. 10.1109/​sct.1989.41828.
https:/​/​doi.org/​10.1109/​sct.1989.41828

[10] A. D. Bookatz. QMA-complete problems. Quantum Information & Computation, 14 (5–6): 361–383, 2014. 10.26421/​QIC14.5-6.
https:/​/​doi.org/​10.26421/​QIC14.5-6

[11] S. Bravyi and D. Gosset. Gapped and gapless phases of frustration-free spin-1/​2 chains. Journal of Mathematical Physics, 56: 061902, 2015. 10.1063/​1.4922508.
https:/​/​doi.org/​10.1063/​1.4922508

[12] S. Bravyi and D. Gosset. Complexity of quantum impurity problems. Communications in Mathematical Physics, 356 (2): 451–500, 2017. 10.1007/​s00220-017-2976-9.
https:/​/​doi.org/​10.1007/​s00220-017-2976-9

[13] S. Bravyi and M. Hastings. On complexity of the quantum Ising model. Communications in Mathematical Physics, 349 (1): 1–45, 2017. 10.1007/​s00220-016-2787-4.
https:/​/​doi.org/​10.1007/​s00220-016-2787-4

[14] N. Breuckmann and B. Terhal. Space-time circuit-to-Hamiltonian construction and its applications. Journal of Physics A: Mathematical and Theoretical, 47 (19): 195304, 2014. 10.1088/​1751-8113/​47/​19/​195304.
https:/​/​doi.org/​10.1088/​1751-8113/​47/​19/​195304

[15] B. Brown, S. Flammia, and N. Schuch. Computational difficulty of computing the density of states. Physical Review Letters, 107 (4): 040501, 2011. 10.1103/​physrevlett.107.040501.
https:/​/​doi.org/​10.1103/​physrevlett.107.040501

[16] S. Buss and L. Hay. On truth-table reducibility to SAT. Information and Computation, 91 (1): 86 – 102, 1991. 10.1016/​0890-5401(91)90075-D.
https:/​/​doi.org/​10.1016/​0890-5401(91)90075-D

[17] L. Caha, Z. Landau, and D. Nagaj. Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning. Phys. Rev. A, 97 (6): 062306, 2018. 10.1103/​PhysRevA.97.062306.
https:/​/​doi.org/​10.1103/​PhysRevA.97.062306

[18] J. Castro and C. Seara. Characterizations of some complexity classes between $\theta_2^p$ and ${\Delta}_2^p$. In Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, pages 303–317, 1992.

[19] A. Chailloux and O. Sattath. The complexity of the separable Hamiltonian problem. In Proceedings of 27th IEEE Conference on Computational Complexity (CCC), pages 32–41, 2012. 10.1109/​ccc.2012.42.
https:/​/​doi.org/​10.1109/​ccc.2012.42

[20] L. Chen. A note on oracle separations for BQP. Available at arXiv:1605.00619v1 [quant-ph], 2016.
arXiv:1605.00619v1

[21] S. Cook. The complexity of theorem proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC), pages 151–158, 1972. 10.1145/​800157.805047.
https:/​/​doi.org/​10.1145/​800157.805047

[22] T. Cubitt and A. Montanaro. Complexity classification of local Hamiltonian problems. SIAM J. Comput., 45 (2): 268–316, 2016. 10.1137/​140998287.
https:/​/​doi.org/​10.1137/​140998287

[23] T. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528: 207–211, 2015. 10.1038/​nature16059.
https:/​/​doi.org/​10.1038/​nature16059

[24] T. Cubitt, A. Montanaro, and S. Piddock. Universal quantum Hamiltonians. Proceedings of the National Academy of Sciences, 115 (38): 9497–9502, 2018. 10.1073/​pnas.1804949115.
https:/​/​doi.org/​10.1073/​pnas.1804949115

[25] B. Fefferman and C. Lin. A complete characterization of unitary quantum space. In A. R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:21. Dagstuhl Publishing, 2018. 10.4230/​LIPIcs.ITCS.2018.4.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2018.4

[26] B. Fefferman, R. Shaltiel, C. Umans, and E. Viola. On beating the hybrid argument. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 468–483, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1115-1. 10.1145/​2090236.2090273. URL http:/​/​doi.acm.org/​10.1145/​2090236.2090273.
https:/​/​doi.org/​10.1145/​2090236.2090273

[27] R. Feynman. Quantum mechanical computers. Optics News, 11 (2): 11–20, 1985. 10.1364/​on.11.2.000011.
https:/​/​doi.org/​10.1364/​on.11.2.000011

[28] S. Gharibian. Approximation, proof systems, and correlations in a quantum world. PhD thesis, University of Waterloo, 2013. Available at arXiv:1301.2632 [quant-ph].
arXiv:1301.2632

[29] 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. 10.1007/​978-3-642-31594-7_33.
https:/​/​doi.org/​10.1007/​978-3-642-31594-7_33

[30] S. Gharibian and J. Sikora. Ground state connectivity of local Hamiltonians. ACM Transactions on Computation Theory, 10 (2), 2018. 10.1145/​3186587.
https:/​/​doi.org/​10.1145/​3186587

[31] 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. 10.1561/​0400000066.
https:/​/​doi.org/​10.1561/​0400000066

[32] S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). In I. Potapov, P. Spirakis, and J. Worrell, editors, 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 Publishing, 2018. 10.4230/​LIPIcs.MFCS.2018.58.
https:/​/​doi.org/​10.4230/​LIPIcs.MFCS.2018.58

[33] S. Gharibian, S. Piddock, and J. Yirka. Oracle complexity classes and local measurements on physical Hamiltonians. Available at arXiv:1909.05981 [quant-ph], 2019.
arXiv:1909.05981

[34] J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6 (4): 675–695, 1977. 10.1137/​0206049.
https:/​/​doi.org/​10.1137/​0206049

[35] A. P. Gilyén and O. Sattath. On preparing ground states of gapped Hamiltonians: An efficient quantum Lovász local lemma. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 439–450, 2017. 10.1109/​FOCS.2017.47.
https:/​/​doi.org/​10.1109/​FOCS.2017.47

[36] 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. 10.1007/​11685654_12.
https:/​/​doi.org/​10.1007/​11685654_12

[37] D. Gosset and E. Mozgunov. Local gap threshold for frustration-free spin systems. Journal of Mathematical Physics, 57: 091901, 2016. 10.1063/​1.4962337.
https:/​/​doi.org/​10.1063/​1.4962337

[38] D. Gosset, J. C. Mehta, and T. Vidick. QCMA hardness of ground space connectivity for commuting Hamiltonians. Quantum, 1: 16, 2017. 10.22331/​q-2017-07-14-16.
https:/​/​doi.org/​10.22331/​q-2017-07-14-16

[39] J. Hartmanis. Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy. In G. Rozenberg and A. Salomaa, editors, Current Trends in Theoretical Computer Science, pages 403–411. World Scientific, 1993. 10.1142/​9789812794499_0029.
https:/​/​doi.org/​10.1142/​9789812794499_0029

[40] L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39 (3): 299 – 322, 1989. 10.1016/​0022-0000(89)90025-1.
https:/​/​doi.org/​10.1016/​0022-0000(89)90025-1

[41] Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. Journal of the ACM, 44 (6): 806–825, 1997. 10.1145/​268999.269002.
https:/​/​doi.org/​10.1145/​268999.269002

[42] R. Karp. Reducibility among combinatorial problems. In R.E. Miller, J.W. Thatcher, and J.D. Bohlinger, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Springer, Boston, MA, 1972. 10.1007/​978-1-4684-2001-2_9.
https:/​/​doi.org/​10.1007/​978-1-4684-2001-2_9

[43] J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. SIAM Journal on Computing, 35 (5): 1070–1097, 2006. 10.1137/​s0097539704445226.
https:/​/​doi.org/​10.1137/​s0097539704445226

[44] 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. 10.1145/​335305.335387.
https:/​/​doi.org/​10.1145/​335305.335387

[45] A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002.

[46] L. Levin. Universal sequential search problems. Problems of Information Transmission, 9 (3): 265–266, 1973.

[47] Y. K. Liu. Consistency of local density matrices is QMA-complete. In J. Díaz, K. Jansen, J.D.P. Rolim, and U. Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 4110 of Lecture Notes in Computer Science, pages 438–449. Springer, Berlin, Heidelberg, 2006. 10.1007/​11830924_40.
https:/​/​doi.org/​10.1007/​11830924_40

[48] J. Lockhart and C. E. González-Guillén. Quantum state isomorphism. Available at arXiv:1709.09622v1 [quant-ph], 2017.
arXiv:1709.09622v1

[49] C. Marriott and J. Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14 (2): 122–152, 2005. 10.1007/​s00037-005-0194-x.
https:/​/​doi.org/​10.1007/​s00037-005-0194-x

[50] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th edition, 2011.

[51] 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. 10.26421/​QIC8.10.
https:/​/​doi.org/​10.26421/​QIC8.10

[52] T. J. Osborne. Hamiltonian complexity. Reports on Progress in Physics, 75 (2): 022001, 2012. 10.1088/​0034-4885/​75/​2/​022001.
https:/​/​doi.org/​10.1088/​0034-4885/​75/​2/​022001

[53] S. Piddock and A. Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. Quantum Information & Computation, 17 (7&8): 636–672, 2017. 10.26421/​QIC17.7-8.
https:/​/​doi.org/​10.26421/​QIC17.7-8

[54] S. Piddock and A. Montanaro. Universal qudit Hamiltonians. Available at arXiv:1802.07130v1 [quant-ph], 2018.
arXiv:1802.07130v1

[55] R. Raz and A. Tal. Oracle separation of BQP and PH. Available at Electronic Colloquium on Computational Complexity (ECCC), 2018.

[56] Z. Remscrim. The Hilbert function, algebraic extractors, and recursive Fourier sampling. In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 197–208, Oct 2016. 10.1109/​FOCS.2016.29.
https:/​/​doi.org/​10.1109/​FOCS.2016.29

[57] P. Schnoebelen. Oracle circuits for branching-time model checking. In J. C.M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, editors, Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 790–801, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. 10.1007/​3-540-45061-0_62.
https:/​/​doi.org/​10.1007/​3-540-45061-0_62

[58] N. Schuch and F. Verstraete. Computational complexity of interacting electrons and fundamental limitations of Density Functional Theory. Nature Physics, 5: 732–735, 2009. 10.1038/​nphys1370.
https:/​/​doi.org/​10.1038/​nphys1370

[59] Y. Shi and S. Zhang. Note on quantum counting classes. Available at http::/​/​www.cse.cuhk.edu.hk/​syzhang/​papers/​SharpBQP.pdf.
http::/​/​www.cse.cuhk.edu.hk/​syzhang/​papers/​SharpBQP.pdf

[60] L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47: 85–93, 1986. 10.1016/​0304-3975(86)90135-0.
https:/​/​doi.org/​10.1016/​0304-3975(86)90135-0

[61] M. Vyalyi. QMA$=$PP implies that PP contains PH. Available at Electronic Colloquium on Computational Complexity (ECCC), 2003.

[62] J. Watrous. Quantum computational complexity. In R. Meyers, editor, Encyclopedia of Complexity and System Science. Springer, 2013. 10.1007/​978-3-642-27737-5_428-3.
https:/​/​doi.org/​10.1007/​978-3-642-27737-5_428-3

[63] T. Yamakami. Quantum NP and a quantum hierarchy. In Baeza-Yates R., Montanari U., and Santoro N., editors, Foundations of Information Technology in the Era of Network and Mobile Computing, volume 96 of IFIP — The International Federation for Information Processing, pages 323–336. Springer, Boston, MA, 2002. 10.1007/​978-0-387-35608-2_27.
https:/​/​doi.org/​10.1007/​978-0-387-35608-2_27

### Cited by

[1] Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brandão, and Or Sattath, "The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings", Quantum 6, 668 (2022).

[2] Sevag Gharibian and François Le Gall, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 19 (2022) ISBN:9781450392648.

[3] James D. Watson and Toby S. Cubitt, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 764 (2022) ISBN:9781450392648.

[4] Dorit Aharonov and Sandy Irani, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 750 (2022) ISBN:9781450392648.

[5] James D. Watson, "Detailed Analysis of Circuit-to-Hamiltonian Mappings", arXiv:1910.01481.

The above citations are from Crossref's cited-by service (last updated successfully 2022-07-05 19:11:37) and SAO/NASA ADS (last updated successfully 2022-07-05 19:11:38). The list may be incomplete as not all publishers provide suitable and complete citation data.