title: Quantum computational complexity of the N-representability problem: QMA complete.
abstract: We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is quantum Merlin-Arthur complete, which is the quantum generalization of nondeterministic polynomial time 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.
authors.affiliation: Computer Science and Engineering, University of California, San Diego, California, USA.
authors.forename: Yi-Kai
authors.initials: YK
authors.lastname: Liu
authors.forename: Matthias
authors.initials: M
authors.lastname: Christandl
authors.forename: F
authors.initials: F
authors.lastname: Verstraete