We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class PQMA[log]: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for PUQMA[log], a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is PQMA[log]-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of PQMA[log].
Quantum mechanics has important consequences for machines that store and manipulate information. In particular, quantum computers might be more powerful than classical computers; examples of this include Shor's algorithm for factoring and discrete logarithms, and Grover's algorithm for black-box search. Because of these theoretical results, and the possibility that we may eventually succeed in building scalable quantum computers, it is interesting to study complexity classes based on quantum computation. QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most of which are variants of the Local Hamiltonian problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems which are very different from those known previously, and have applications in quantum chemistry. The first one is Consistency of Local Density Matrices : given a collection of density matrices describing different subsets of an n-qubit system (where each subset has constant size), decide whether these are consistent with some global state of all n qubits. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. Our reduction is based on algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, Fermionic Local Hamiltonian and N- representability, are QMA-complete. These problems involve systems of fermions, rather than qubits; they arise in calculating the ground state energies of molecular systems. N-representability is particularly interesting, as it is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has provided the right tools to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and stoquastic systems. We also give an alternative proof of a result due to Jaynes : whenever local density matrices are consistent, they are consistent with a Gibbs state
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 results: (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] above requires O(log(n))-local Hamiltonians and O(log(n))-local observables. Whether this could be improved to the more physically appealing O(1)-local setting was left as an open question. We resolve this question positively by showing that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete. (2) We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is P^QMA[log]-complete. (3) P^QMA[log] is thought of as slightly harder than QMA. We give a formal justification of this intuition by exploiting the technique of hierarchical voting of [Beigel, Hemachandra, and Wechsung, SCT 1989] to show P^QMA[log] is in PP. This improves the known containment that QMA is in PP [Kitaev, Watrous, STOC 2000]. (4) A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, 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.
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date. Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.