A Caltech Library Service

Quantum Computational Complexity of the N-Representability Problem: QMA Complete

Liu, Yi-Kai and Christandl, Matthias and Verstraete, F. (2007) Quantum Computational Complexity of the N-Representability Problem: QMA Complete. Physical Review Letters, 98 (11). Art. No. 110503. ISSN 0031-9007.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2007 The American Physical Society. (Received 17 September 2006; published 16 March 2007) Y.K.L. and M.C. thank the Institute for Quantum Information for its hospitality. Y.K.L. is supported by ARO/DTO QuaCGR. M.C. acknowledges support from EPSRC and Magdalene College, Cambridge, and is supported by the EU under the FP6-FET Integrated Project SCALA, No. CT-015714. F.V. is supported by the Gordon and Betty Moore Foundation through Caltech’s Center for the Physics of Information, and by the NSF under Grant No. PHY-0456720.
Issue or Number:11
Record Number:CaltechAUTHORS:LIUprl07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7662
Deposited By: Archive Administrator
Deposited On:20 Mar 2007
Last Modified:02 Oct 2019 23:44

Repository Staff Only: item control page