×

Quantum lattice algorithms: similarities and connections to some classic finite difference algorithms. (English) Zbl 1355.82003

Summary: Quantum lattice algorithms originated with the Feynman checkerboard model for the one-dimensional Dirac equation. They offer discrete models of quantum mechanics in which the complex numbers representing wavefunction values on a discrete spatial lattice evolve through discrete unitary operations. This paper draws together some of the identical, or at least unitarily equivalent, algorithms that have appeared in three largely disconnected strands of research. Treated as conventional numerical algorithms, they are all only first order accurate under refinement of the discrete space/time grid, but may be raised to second order by a unitary change of variables. Much more efficient implementations arise from replacing the evolution through a sequence of unitary intermediate steps with a short path integral formulation that expresses the wavefunction at each spatial point on the most recent time level as a linear combination of values at immediately preceding time levels and neighbouring spatial points. In one dimension, a particularly elegant reformulation replaces two variables at two time levels with a single variable over three time levels. The resulting algorithm is a variational integrator arising from a discrete action principle, and coincides with the Ablowitz-Kruskal-Ladik finite difference scheme for the Klein-Gordon equation.

MSC:

82-08 Computational methods (statistical mechanics) (MSC2010)
35Q41 Time-dependent Schrödinger equations and Dirac equations
35Q53 KdV equations (Korteweg-de Vries equations)
65N06 Finite difference methods for boundary value problems involving PDEs

Software:

MATLAB expm; Expokit

References:

[1] R. P. Feynman and A. R. Hibbs, Quantum Mechanics and Path Integrals (McGraw–Hill, New York, 1965). · Zbl 0176.54902
[2] W. Heisenberg, Die Selbstenergie des Elektrons, Z. Phys. 65, 4 (1930). · JFM 56.0753.05
[3] B. Carazza and H. Kragh, Heisenberg’s lattice world: The 1930 theory sketch, Amer. J. Phys. 63, 595 (1995).
[4] P. J. Dellar, An exact energy conservation property of the quantum lattice Boltzmann algorithm, Phys. Lett. A 376, 6 (2011). · Zbl 1255.81133
[5] H.-L. Lai and C.-F. Ma, An implicit scheme of lattice Boltzmann method for sine-Gordon equation, Chinese Phys. Lett. 25, 2118 (2008). ESAIM: PROCEEDINGS AND SURVEYS103
[6] P. J. Dellar, Macroscopic descriptions of rarefied gases from the elimination of fast variables, Phys. Fluids 19, 107101 (2007). · Zbl 1182.76195
[7] L. L. Foldy and S. A. Wouthuysen, On the Dirac theory of spin 1/2 particles and its non-relativistic limit, Phys. Rev. 78, 29 (1950). · Zbl 0039.22605
[8] J. P. Costella and B. H. J. McKellar, The Foldy–Wouthuysen transformation, Amer. J. Phys. 63, 1119 (1995). · Zbl 1219.81143
[9] M. Reiher, Relativistic Douglas–Kroll–Hess theory, WIREs Comput. Mol. Sci. 2, 139 (2012).
[10] G. B. Whitham, Linear and Nonlinear Waves (Wiley Interscience, New York, 1974). · Zbl 0373.76001
[11] J. F. Reynolds, A proof of the random-walk method for solving Laplace’s equation in 2-D, Math. Gazette 49, 416 (1965). · Zbl 0132.11901
[12] J. Glimm, Solutions in the large for nonlinear hyperbolic systems of equations, Comm. Pure Appl. Math. 18, 697 (1965). · Zbl 0141.28902
[13] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48, 1687 (1993).
[14] D. A. Meyer, From quantum cellular automata to quantum lattice gases, J. Statist. Phys. 85, 551 (1996). · Zbl 0952.37501
[15] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the TwentyEighth Annual ACM Symposium on Theory of Computing (ACM, New York, NY, USA, 1996), STOC ’96, pp. 212–219. · Zbl 0922.68044
[16] L. K. Grover, From Schr”odinger’s equation to the quantum search algorithm, Amer. J. Phys. 69, 769 (2001).
[17] M. A. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and A. D. Spielman, Exponential algorithmic speedup by a quantum walk, in Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, NY, 2003), STOC ’03, pp. 59–68. · Zbl 1192.81059
[18] A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quant. Inf. 1, 507 (2003). · Zbl 1069.81505
[19] J. Kempe, Quantum random walks: An introductory overview, Contemp. Phys. 44, 307 (2003).
[20] V. Kendon, Decoherence in quantum walks – a review, Math. Struct. Comput. Sci. 17, 1169 (2007). · Zbl 1130.81325
[21] N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67, 052307 (2003).
[22] N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81, 042330 (2010).
[23] A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009).
[24] C. A. Ryan, M. Laforest, J. C. Boileau, and R. Laflamme, Experimental implementation of a discrete-time 104ESAIM: PROCEEDINGS AND SURVEYS
[25] J. Yepez, Relativistic path integral as a lattice-based quantum algorithm, Quant. Informat. Process. 4, 471 (2005). · Zbl 1130.81048
[26] J. Yepez, Quantum Algorithms for Computational Physics: Volume 3 of Lattice Gas Dynamics, Tech. Rep. AFRL-VS-HA-TR-2006-1143, Air Force Research Laboratory, Hanscom, MA (2007), available from http://www.dtic.mil/docs/citations/ADA474659.
[27] J. Yepez, G. Vahala, L. Vahala, and M. Soe, Superfluid turbulence from quantum Kelvin wave to classical Kolmogorov cascades, Phys. Rev. Lett. 103, 084501 (2009).
[28] T. Inamuro, M. Yoshino, and F. Ogino, Accuracy of the lattice Boltzmann method for small Knudsen number with finite Reynolds number, Phys. Fluids 9, 3535 (1997). · Zbl 1185.76869
[29] Y. Sone, Kinetic Theory and Fluid Dynamics (Birkh”auser, Boston, 2002). · Zbl 1021.76002
[30] X. He, S. Chen, and G. D. Doolen, A novel thermal model of the lattice Boltzmann method in incompressible limit, J. Comput. Phys. 146, 282 (1998). · Zbl 0919.76068
[31] S. Succi and R. Benzi, Lattice Boltzmann equation for quantum mechanics, Physica D 69, 327 (1993). · Zbl 0798.76080
[32] S. Succi, Numerical solution of the Schr”odinger equation using discrete kinetic theory, Phys. Rev. E 53, 1969 (1996).
[33] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev. 20, 801 (1978). · Zbl 0395.65012
[34] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev. 45, 3 (2003). · Zbl 1030.65029
[35] B. R. Sidje, Expokit: a software package for computing matrix exponentials, ACM Trans. Math. Softw. 24, 130 (1998). · Zbl 0917.65063
[36] N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM. J. Matrix Anal. Appl. 26, 1179 (2005). · Zbl 1081.65037
[37] R. Vichnevetsky and J. B. Bowles, Fourier Analysis of Numerical Approximations of Hyperbolic Equations (SIAM, Philadelphia, 1982). · Zbl 0495.65041
[38] L. Trefethen, Group velocity in finite difference schemes, SIAM Rev. 24, 113 (1982). · Zbl 0487.65055
[39] H. B. Nielsen and M. Ninomiya, Absence of neutrinos on a lattice: (I) Proof by homotopy theory, Nucl. Phys. B 185, 20 (1981).
[40] H. B. Nielsen and M. Ninomiya, Absence of neutrinos on a lattice: (II) Intuitive topological proof, Nucl. Phys. B 193, 173 (1981).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.