The Complexity of the Consistency and N-representability Problems for Quantum States

Abstract

QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses 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 arise in calculating the ground state energies of molecular systems. N-representability 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 allowed us 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.

PhD thesis. Yay, no more grad school!! (Finished in August, but did not get around to posting it until now.) 91 pages, a few figures, some boring sections. Has detailed proofs of results in quant-ph/0604166 and quant-ph/0609125. Ch.4 is a preliminary sketch of 0712.1388. Ch.5 is quant-ph/0603012

References in corpus (23)

• The density-matrix renormalization group
• Strengths and Weaknesses of Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Fermionic quantum computation
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Matrix product states represent ground states faithfully
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Quantum Algorithms for Fermionic Simulations
• Quantum marginal problem and N-representability
• The power of quantum systems on a line
• N-representability is QMA-complete
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Quantum marginal problem and representations of the symmetric group
• Quantum NP - A Survey
• One-qubit reduced states of a pure many-qubit state: polygon inequalities
• Quantum state transformations and the Schubert calculus
• Merlin-Arthur Games and Stoquastic Complexity
• Compatibility of subsystem states and convex geometry
• Identity check is QMA-complete
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
• The Complexity of Quantum Systems on a One-dimensional Chain
• Quantum Certificate Verification: Single versus Multiple Quantum Certificates

Cited by in corpus (10)

• Thermodynamics of quantum systems with multiple conserved quantities
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• An improved semidefinite programming hierarchy for testing entanglement
• A Quantum Lovasz Local Lemma
• Quantum Strategies and Local Operations
• Detecting mixed-unitary quantum channels is NP-hard
• Limitations of semidefinite programs for separable states and entangled games
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• From Quantum Source Compression to Quantum Thermodynamics
• Properties of Local Quantum Operations with Shared Entanglement