Published March 16, 2007
| Version Published
Journal Article
Open
Quantum Computational Complexity of the N-Representability Problem: QMA Complete
Abstract
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.
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.Attached Files
Published - LIUprl07.pdf
Files
LIUprl07.pdf
Files
(103.7 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:35ef164a583802076eb35688b6a9db67
|
103.7 kB | Preview Download |
Additional details
Identifiers
- Eprint ID
- 7662
- Resolver ID
- CaltechAUTHORS:LIUprl07
Dates
- Created
-
2007-03-20Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field