Remote Access Mathematics of Computation
Green Open Access

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
MathSciNet review: 3073201
Full-text PDF Free Access

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. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26 (1997), no. 5, 1510–1523. MR 1471991,
  • 3. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Quantum computation and information (Washington, DC, 2000) Contemp. Math., vol. 305, Amer. Math. Soc., Providence, RI, 2002, pp. 53–74. MR 1947332,
  • 4. Sergey Bravyi, David DiVincenzo, and Daniel Loss, Polynomial-time algorithm for simulation of weakly interacting quantum spin systems, Comm. Math. Phys. 284 (2008), no. 2, 481–507. MR 2448138,
  • 5. C. Le Bris (ed.), Handbook of numerical analysis. Vol. X, Handbook of Numerical Analysis, X, North-Holland, Amsterdam, 2003. Special volume: computational chemistry. MR 2008385
  • 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. James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
  • 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. George E. Forsythe and Wolfgang R. Wasow, Finite-difference methods for partial differential equations, Dover Phoenix Editions, Dover Publications, Inc., Mineola, NY, 2004. Reprint of the 1960 original. MR 2360350
  • 10. H. Häffner, C. F. Roos, and R. Blatt, Quantum computing with trapped ions, Phys. Rep. 469 (2008), no. 4, 155–203. MR 2475413,
  • 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. Julia Kempe, Alexei Kitaev, and Oded Regev, The complexity of the local Hamiltonian problem, SIAM J. Comput. 35 (2006), no. 5, 1070–1097. MR 2217138,
  • 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. Randall J. LeVeque, Finite difference methods for ordinary and partial differential equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2007. Steady-state and time-dependent problems. MR 2378550
  • 19. Christian Lubich, From quantum to classical molecular dynamics: reduced models and numerical analysis, Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich, 2008. MR 2474331
  • 20. Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR 1796805
  • 21. Erich Novak, Quantum complexity of integration, J. Complexity 17 (2001), no. 1, 2–16. MR 1817606,
  • 22. Erich Novak, Ian H. Sloan, and Henryk Woźniakowski, Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math. 4 (2004), no. 2, 121–156. MR 2049868,
  • 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 (2007), no. 4-6, 802–827. MR 2371994,
  • 25. A. Papageorgiou and C. Zhang,
    On the efficiency of quantum algorithms for Hamiltonian simulation.
    Quantum Information Processing, 11(2):541-561, 2012.
  • 26. Masuo Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations, Phys. Lett. A 146 (1990), no. 6, 319–323. MR 1059400,
  • 27. Masuo Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, J. Math. Phys. 32 (1991), no. 2, 400–407. MR 1088360,
  • 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 H. Woźniakowski, Path integration on a quantum computer, Quantum Inf. Process. 1 (2002), no. 5, 365–388 (2003). MR 1987457,
  • 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 (1956), 613–623. MR 84185,
  • 34. H. F. Weinberger, Lower bounds for higher eigenvalues by finite difference methods, Pacific J. Math. 8 (1958), 339–368; erratum, 941. MR 107372
  • 35. Mladen Victor Wickerhauser, Adapted wavelet analysis from theory to software, A K Peters, Ltd., Wellesley, MA, 1994. With a separately available computer disk (IBM-PC or Macintosh). MR 1299983
  • 36. J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

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