Quantum Computational Complexity of the N -Representability Problem: QMA Complete
Yi-Kai Liu, Matthias Christandl, Frank Verstraete · Physical Review Letters · 2007
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.