Title | N-representability is QMA-complete |
Publication Type | Journal Article |
Year of Publication | 2007 |
Authors | Liu, Y-K, Christandl, M, Verstraete, F |
Journal | Phys. Rev. Lett. |
Volume | 98 |
Issue | 11 |
Date Published | 2007/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. |
URL | http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.110503 |
DOI | 10.1103/PhysRevLett.98.110503 |