N-representability is QMA-complete

TitleN-representability is QMA-complete
Publication TypeJournal Article
Year of Publication2007
AuthorsLiu, Y-K, Christandl, M, Verstraete, F
JournalPhys. Rev. Lett.
Volume98
Issue11
Date Published2007/03/16
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.

URLhttp://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.110503
DOI10.1103/PhysRevLett.98.110503