Coauthors: Matthias Christandl and Frank Verstraete

We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is QMA-complete, which is the quantum generalization of NP-complete. Our proof uses a simple mapping from spin systems to fermionic systems, together with a convex optimization technique that reduces the problem of finding ground states to N-representability.

(This talk will include a short introduction to complexity theory and QMA-completeness.)