Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


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
MathSciNet review: 3073201
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?)

  • 1. D. S. Abrams and S. Lloyd,
    Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.
    Phys. Rev. Lett., 83:5162-5165, 1999.
  • 2. C. H. Bennet, E. Bernstein, G. Brassard, and U. Vazirani,
    Strengths and weaknesses of quantum computing.
    SIAM J. Computing, 26:1510-1523, 1997. MR 1471991 (99e:68034)
  • 3. G. Brassard, P. Hoyer, M. Mosca, and A. Tapp,
    Quantum amplitude amplification and estimation, volume 305, page 53.
    In Contemporary Mathematics, Quantum Computation and Information, Samuel J. Lomonaco Jr. and Howard E. Brandt, Editors, AMS, Providence, RI, 2002. MR 1947332 (2004a:81048)
  • 4. S. Bravyi, D. DiVincenzo, and D. Loss,
    Polynomial-time algorithm for simulation of weakly interacting quantum spin systems.
    Communications in Mathematical Physics, 284:481-507, 2008. MR 2448138 (2009i:81043)
  • 5. P. G. Ciarlet and C. Le Bris,
    Handbook of Numerical Analysis, Special Volume Computational Chemistry, volume X.
    North Holland, Amsterdam, 2003. MR 2008385 (2005c:81001)
  • 6. C. R. Clark, T. S. Metodi, S. D. Gasster, and K. R. Brown,
    Resource requirements for fault-tolerant quantum simulation: The ground state of the transverse Ising model.
    Phys. Rev. A, 79:062314, 2009.
  • 7. J. W. Demmel,
    Applied Numerical Linear Algebra.
    SIAM, Philadelphia, PA, 1997. MR 1463942 (98m:65001)
  • 8. J. Du, N. Xu, X. Peng, P. Wang, S. Wu, and D. Lu,
    NMR implementation of a molecular hydrogen quantum simulation with adiabatic state preparation.
    Phys. Rev. Lett., 104:030502, 2010.
  • 9. G. E. Forsythe and W. R. Wasow,
    Finite-Difference Methods for Partial Differential Equations.
    Dover, New York, 2004. MR 2360350 (2008g:65107)
  • 10. H. Häffner, C. F. Roos, and R. Blatt,
    Quantum computing with trapped ions.
    Phys. Reports, 469:155, 2008. MR 2475413 (2009m:81039)
  • 11. A. Hams and H. DeRaedt,
    Fast algorithm for finding the eigenvalue distribution of very large matrices.
    Phys. Rev. E, 62(3):4365-4377, 2000.
  • 12. P. Jaksch and A. Papageorgiou,
    Eigenvector approximation leading to exponential speedup of quantum eigenvalue estimation.
    Phys. Rev. Lett., 91:257902, 2003.
  • 13. I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik,
    Polynomial-time quantum algorithm for the simulation of chemical dynamics.
    PNAS, 105:18681-18686, 2008.
  • 14. I. Kassal, J. D. Witfield, A. Perdomo-Ortiz, Man-Hong Yung, and A. Aspuru-Guzik,
    Quantum information and computation for chemistry.
    An. Rev. Phys. Chem., 62:185-207, 2011.
  • 15. J. Kempe, A. Kitaev, and O. Regev,
    The complexity of the local Hamiltonian problem.
    SIAM J. Computing, 35:1070-1097, 2006. MR 2217138 (2006m:68037)
  • 16. A. Klappenecker and M. Rötteler,
    Discrete cosine transforms on quantum computers, 2001.
  • 17. B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, A. Aspuru-Guzik, and A. G. White,
    Towards quantum chemistry on a quantum computer.
    Nature Chemistry, 2:106-111, 2010.
  • 18. R. J. LeVeque,
    Finite Difference Methods for Ordinary and Partial Differential Equations.
    SIAM, Philadelphia,PA, 2007. MR 2378550 (2009a:65173)
  • 19. C. Lubich,
    From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis.
    European Mathematical Society, Zürich, 2008. MR 2474331 (2010e:81268)
  • 20. M. A. Nielsen and I. L. Chuang,
    Quantum Computation and Quantum Information.
    Cambridge University Press, Cambridge, UK, 2000. MR 1796805 (2003j:81038)
  • 21. E. Novak,
    Quantum complexity of integration.
    J. Complexity, 19:19-42, 2001. MR 1817606 (2002e:68022a)
  • 22. E. Novak, I. H. Sloan, and H. Woźniakowski,
    Tractability of approximation for weighted Korobov spaces on classical and quantum computers.
    Journal of Foundations of Computational Mathematics, 4:121-156, 2004. MR 2049868 (2005h:81097)
  • 23. S. Oh,
    Quantum computational method of finding the ground-state energy and expectation values.
    Phys. Rev. A, 77:012326, 2008.
  • 24. A. Papageorgiou,
    On the complexity of the multivariate Sturm-Liouville eigenvalue problem.
    J. Complexity, 23:802-827, 2007. MR 2371994 (2008k:65152)
  • 25. A. Papageorgiou and C. Zhang,
    On the efficiency of quantum algorithms for Hamiltonian simulation.
    Quantum Information Processing, 11(2):541-561, 2012.
  • 26. M. Suzuki,
    Fractal decomposition of exponential operators with applications to many body theories and Monte Carlo simulations.
    Phys. Lett. A, 146:319-323, 1990. MR 1059400 (91d:81005)
  • 27. M. Suzuki,
    General theory of fractal path integrals with application to many-body theories and statistical physics.
    J. Math. Phys., 32:400-407, 1991. MR 1088360 (92k:81096)
  • 28. T. Szkopek, V. Roychowdhury, E. Yablonovitch, and D. S. Abrams,
    Eigenvalue estimation of differential operators with a quantum algorithm.
    Phys. Rev. A, 72:062318, 2005.
  • 29. J. F. Traub and W. Woźniakowski,
    Path integration on a quantum computer.
    Quantum Information Processing, 1:365-388, 2002. MR 1987457 (2004g:81042)
  • 30. P. Varga and B. Apagyi,
    Phase estimation procedure to solve quantum-mechanical eigenvalue problems.
    Phys. Rev. A, 78:022337, 2008.
  • 31. H. Wang, S. Ashhab, and F. Nori,
    Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer.
    Phys. Rev. A, 79:042335, 2009.
  • 32. H. Wang, S. Kais, A. Aspuru-Guzik, and M. R. Hoffmann,
    Quantum algorithm for obtaining the energy spectrum of molecular systems.
    Phys. Chem. Chem. Phys., 10:5388-5393, 2008.
  • 33. H. F. Weinberger,
    Upper and lower bounds for eigenvalues by finite difference methods.
    Comm. Pure Appl. Math, 9:613-623, 1956. MR 0084185 (18:826a)
  • 34. H. F. Weinberger,
    Lower bounds for higher eigenvalues by finite difference methods.
    Pacific J. Math., 8:339-368, 1958. MR 0107372 (21:6097)
  • 35. M. V. Wickerhauser,
    Adapted wavelet analysis from theory to software.
    A.K. Peters, Wellesley, MA, 1994. MR 1299983 (95j:94005)
  • 36. J. H. Wilkinson,
    The Algebraic Eigenvalue Problem.
    Oxford University Press, Oxford, UK, 1965. MR 0184422 (32:1894)

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

I. Petras
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027

J. F. Traub
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027

C. Zhang
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027

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

American Mathematical Society