Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A fast algorithm for approximating the ground state energy on a quantum computer


Authors: A. Papageorgiou, I. Petras, J. F. Traub and C. Zhang
Journal: Math. Comp. 82 (2013), 2293-2304
MSC (2010): Primary 65D15, 81-08
Published electronically: May 16, 2013
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Estimating the ground state energy of a multiparticle system with relative error $ \varepsilon $ using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables $ d$ that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error $ \varepsilon $ using a number of qubits $ C^\prime d\log \varepsilon ^{-1}$ with total cost (number of queries plus other quantum operations) $ Cd\varepsilon ^{-(3+\delta )}$, where $ \delta >0$ is arbitrarily small and $ C$ and $ C^\prime $ are independent of $ d$ and $ \varepsilon $.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D15, 81-08

Retrieve articles in all journals with MSC (2010): 65D15, 81-08


Additional Information

A. Papageorgiou
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027
Email: ap@cs.columbia.edu

I. Petras
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027
Email: ipetras@cs.columbia.edu

J. F. Traub
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027
Email: traub@cs.columbia.edu

C. Zhang
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027
Email: czhang@cs.columbia.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02714-7
PII: S 0025-5718(2013)02714-7
Keywords: Eigenvalue problem, numerical approximation, quantum algorithms
Received by editor(s): May 28, 2011
Received by editor(s) in revised form: February 17, 2012
Published electronically: May 16, 2013
Additional Notes: This work has been supported in part by the National Science Foundation
Article copyright: © Copyright 2013 American Mathematical Society