Quantum computational complexity of the N-representability problem: QMA complete.
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.
Liu
Yi-Kai
YK
Computer Science and Engineering, University of California, San Diego, California, USA.
Christandl
Matthias
M
Verstraete
F
F