N-representability is QMA-complete

Author(s): Y.-K. Liu, M. Christandl, F. Verstraete

Journal: Physical Review Letters

Volume: 98

Page(s): 110503

Year: 2007

DOI Number: 10.1103/PhysRevLett.98.110503

Link: Link to publication


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, as well as a convex optimization technique that reduces the problem of finding ground states to N-representability.

Note: http://arxiv.org/abs/quant-ph/0609125

File: Link to PDF

Verstraete Group Verstraete Group