Quantum computational complexity of the N-representability problem: QMA complete

Yi-Kai Liu, Matthias Christandl, Frank Verstraete

Publications: Contribution to journalArticlePeer Reviewed


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. © 2007 The American Physical Society
Original languageEnglish
Article number110503
Number of pages4
JournalPhysical Review Letters
Issue number11
Publication statusPublished - 16 Mar 2007

Austrian Fields of Science 2012

  • 103025 Quantum mechanics

Cite this