The complexity of simulating local measurements on quantum systems

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): (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] requires O(log n)-local observables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. (2) 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. (3) 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] is in PP. This improves the containment QMA is in 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.

38 pages, 0 figures. Fixed bug in proof of Lemma 4.3 by extending Lemma 4.1 and redefining gamma' (see footnote 13)

References in corpus (13)

• Universal Quantum Hamiltonians
• Complexity of quantum impurity problems
• Computational Difficulty of Computing the Density of States
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Hamiltonian sparsification and gap-simulations
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• QCMA hardness of ground space connectivity for commuting Hamiltonians
• Super-Additivity and Entanglement Assistance in Quantum Reading
• Oracle complexity classes and local measurements on physical Hamiltonians
• Approximation, Proof Systems, and Correlations in a Quantum World

Cited by in corpus (6)

• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Importance of the spectral gap in estimating ground-state energies
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• The 7 faces of quantum NP
• Energy gap of quantum spin glasses: a projection quantum Monte Carlo study