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

Papageorgiou, A.; Petras, I.; Traub, J.; Zhang, C.

doi:10.1090/S0025-5718-2013-02714-7

A fast algorithm for approximating the ground state energy on a quantum computer
HTML articles powered by AMS MathViewer

by A. Papageorgiou, I. Petras, J. F. Traub and C. Zhang PDF

Math. Comp. 82 (2013), 2293-2304 Request permission

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

D. S. Abrams and S. Lloyd, Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Phys. Rev. Lett., 83:5162–5165, 1999.
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, DOI 10.1137/S0097539796300933
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, DOI 10.1090/conm/305/05215
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, DOI 10.1007/s00220-008-0574-6
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
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.
James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
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.
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
H. Häffner, C. F. Roos, and R. Blatt, Quantum computing with trapped ions, Phys. Rep. 469 (2008), no. 4, 155–203. MR 2475413, DOI 10.1016/j.physrep.2008.09.003
A. Hams and H. DeRaedt, Fast algorithm for finding the eigenvalue distribution of very large matrices. Phys. Rev. E, 62(3):4365–4377, 2000.
P. Jaksch and A. Papageorgiou, Eigenvector approximation leading to exponential speedup of quantum eigenvalue estimation. Phys. Rev. Lett., 91:257902, 2003.
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.
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. http://arxiv.org/abs/1007.2648.
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, DOI 10.1137/S0097539704445226
A. Klappenecker and M. Rötteler, Discrete cosine transforms on quantum computers, 2001. http://arXiv.org/quant-ph/0111038.
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.
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, DOI 10.1137/1.9780898717839
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, DOI 10.4171/067
Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR 1796805
Erich Novak, Quantum complexity of integration, J. Complexity 17 (2001), no. 1, 2–16. MR 1817606, DOI 10.1006/jcom.2000.0566
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, DOI 10.1007/s10208-002-0074-6
S. Oh, Quantum computational method of finding the ground-state energy and expectation values. Phys. Rev. A, 77:012326, 2008.
A. Papageorgiou, On the complexity of the multivariate Sturm-Liouville eigenvalue problem, J. Complexity 23 (2007), no. 4-6, 802–827. MR 2371994, DOI 10.1016/j.jco.2007.03.002
A. Papageorgiou and C. Zhang, On the efficiency of quantum algorithms for Hamiltonian simulation. Quantum Information Processing, 11(2):541–561, 2012. DOI: http://dx.doi.org/10.1007/s11128-011-0263-9.
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, DOI 10.1016/0375-9601(90)90962-N
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, DOI 10.1063/1.529425
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.
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, DOI 10.1023/A:1023417813916
P. Varga and B. Apagyi, Phase estimation procedure to solve quantum-mechanical eigenvalue problems. Phys. Rev. A, 78:022337, 2008.
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.
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.
H. F. Weinberger, Upper and lower bounds for eigenvalues by finite difference methods, Comm. Pure Appl. Math. 9 (1956), 613–623. MR 84185, DOI 10.1002/cpa.3160090329
H. F. Weinberger, Lower bounds for higher eigenvalues by finite difference methods, Pacific J. Math. 8 (1958), 339–368; erratum, 941. MR 107372
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
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422