00845nas a2200145 4500008004100000245003900041210003700080260001500117490000700132520042900139100001600568700002500584700001900609856007100628 2007 eng d00aN-representability is QMA-complete0 aNrepresentability is QMAcomplete c2007/03/160 v983 aWe 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.1 aLiu, Yi-Kai1 aChristandl, Matthias1 aVerstraete, F. uhttp://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.110503