N-representability is QMA-complete

Abstract

We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is QMA-complete, which is the quantum generalization of NP-complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N-representability.

References in corpus (3)

• Matrix product states represent ground states faithfully
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Quantum state transformations and the Schubert calculus

Cited by in corpus (10)

• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Gaussian quantum marginal problem
• Merlin-Arthur Games and Stoquastic Complexity
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Some Open Problems in Quantum Information Theory
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Quantum Multi Prover Interactive Proofs with Communicating Provers
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• The quantum moment problem and bounds on entangled multi-prover games
• The Power of Unentanglement