Quantum computational complexity of the N-representability problem

Autor(en)

Yi-Kai Liu, Matthias Christandl, Frank Verstraete

Abstrakt

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

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

University of California, San Diego, University of Cambridge, California Institute of Technology (Caltech)

Journal

Physical Review Letters

Band

98

Anzahl der Seiten

4

ISSN

0031-9007

DOI

https://doi.org/10.1103/PhysRevLett.98.110503

Publikationsdatum

03-2007

Peer-reviewed

Ja

ÖFOS 2012

103025 Quantenmechanik

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/2700e828-d9c6-4c21-9870-f3ee6470582a