Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ESAIM Proceedings and Surveys

Quantum lattice algorithms: similarities and connections to some classic finite difference algorithms

Paul J. Dellar

Published Dec 1, 2015• 3 citations
Publisher

Abstract

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.

DOI
10.1051/proc/201552005

Related papers

A quantum lattice algorithm with fourth-order accuracy for the one-dimensional Dirac equation

Paul J. Dellar

The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of an alternating sequence of unitary operators: streaming of wavefunction values to adjacent points, and a Hadamard-type unitary matrix to blend pairs of values at individual points. Each operator generates the exact evolution due to part of the Hamiltonian for the one-dimensional Dirac equation over a finite time step. Composing these operators thus creates a discrete approximation to the Dirac equation. However, the composition of two non-commuting operators creates a global splitting error proportional to the length of the time step. The global error can be reduced from first order to second order in the time step by a unitary pre- and post-processing of the initial conditions and final output. The algorithm then becomes equivalent to a symmetric composition, a Strang splitting, between the two operators. This paper describes a fourth-order accurate composition scheme using nine stages, the fewest possible when the lengths of the time steps employed in the different stages are constrained to be integer multiples of some base time step. Each stage is itself a symmetric composition between two operators. This fourth-order scheme produces quantitatively smaller errors for a typical benchmark problem on spatial lattices with 1024 or more points, and shows the expected fourth-order convergence on sufficiently fine lattices. It has greater accuracy, over sufficiently long times, than three better-known fourth-order composition schemes using fewer stages, but with lengths related by irrational coefficients. The truncation error for plane-wave solutions is due to an operator that separates into a resonant part proportional to the Hamiltonian, and a non-resonant part orthogonal to the Hamiltonian. The resonant part commutes with the exact evolution operator, so its error accumulates to grow linearly with time. The orthogonal part produces oscillations that remain bounded over many time steps. The nine-stage integer scheme has the smallest resonant truncation error of the four schemes, despite being the only scheme that can be implemented using local operations. The other schemes implement streaming by irrational fractions of the lattice spacing using discrete Fourier transforms. • A fourth-order accurate quantum algorithm using local operations on regular lattices. • Higher quantitative accuracy for relevant problem sizes than existing schemes. • Higher long-time accuracy than standard fourth-order schemes with global operations. • Discrete invariants give fourth and higher order approximations to the energy.

Journal of Computational Physics•Apr 8, 2025•0 citations

Quantum computing classical physics

DAVID A. MEYER

In the past decade, quantum algorithms have been found which outperform the best classical solutions known for certain classical problems as well as the best classical methods known for simulation of certain quantum systems. This suggests that they may also speed up the simulation of some classical systems. I describe one class of discrete quantum algorithms which do so--quantum lattice-gas automata--and show how to implement them efficiently on standard quantum computers.

arXiv:quant-ph/0111069•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Mar 15, 2002•33 citations

A time-reversible integrator for the time-dependent Schrödinger equation on an adaptive grid

Seonghoon Choi, Jiří Vaníček

One of the most accurate methods for solving the time-dependent Schrödinger equation uses a combination of the dynamic Fourier method with the split-operator algorithm on a tensor-product grid. To reduce the number of required grid points, we let the grid move together with the wavepacket but find that the naïve algorithm based on an alternate evolution of the wavefunction and grid destroys the time reversibility of the exact evolution. Yet, we show that the time reversibility is recovered if the wavefunction and grid are evolved simultaneously during each kinetic or potential step; this is achieved by using the Ehrenfest theorem together with the splitting method. The proposed algorithm is conditionally stable, symmetric, and time-reversible and conserves the norm of the wavefunction. The preservation of these geometric properties is shown analytically and demonstrated numerically on a three-dimensional harmonic model and collinear model of He–H2 scattering. We also show that the proposed algorithm can be symmetrically composed to obtain time-reversible integrators of an arbitrary even order. We observed 10 000-fold speedup by using the tenth-order instead of the second-order method to obtain a solution with a time discretization error below 10−9. Moreover, using the adaptive grid instead of the fixed grid resulted in a 64-fold reduction in the required number of grid points in the harmonic system and made it possible to simulate the He–H2 scattering for six times longer while maintaining reasonable accuracy. Applicability of the algorithm to high-dimensional quantum dynamics is demonstrated using the strongly anharmonic eight-dimensional Hénon–Heiles model.

arXiv:1909.06412•The Journal of Chemical Physics•Dec 16, 2019•8 citations

Feynman checkers: towards algorithmic quantum theory

Михаил Борисович Скопенков, A. Ustinov

We survey and develop the most elementary model of electron motion introduced by R$.$Feynman. In this game, a checker moves on a checkerboard by simple rules, and we count the turns. Feynman checkers are also known as a one-dimensional quantum walk or an Ising model at imaginary temperature. We solve mathematically a problem by R$.$Feynman from 1965, which was to prove that the discrete model (for large time, small average velocity, and small lattice step) is consistent with the continuum one. We study asymptotic properties of the model (for small lattice step and large time) improving the results by J$.$Narlikar from 1972 and by T$.$Sunada-T$.$Tate from 2012. For the first time we observe and prove concentration of measure in the small-lattice-step limit. We perform the second quantization of the model.

arXiv:2007.12879•Jul 25, 2020•1 citation

Fibre bundle formulation of relativistic quantum mechanics. II. Covariant approach

Bozhidar Zakhariev Iliev

We propose a fibre bundle formulation of the mathematical base of relativistic quantum mechanics. At the present stage the bundle form of the theory is equivalent to its conventional one, but it admits new types of generalizations in different directions. In the present, second, part of our investigation, we consider a covariant approach to bundle description of relativistic quantum mechanics. In it the wavefunctions are replaced with (state) sections of a suitably chosen vector bundle over space-time whose (standard) fibre is the space of the wavefunctions. Now the quantum evolution is described as a linear transportation (by means of the transport along the identity map of the space\nobreakdash-time) of the state sections in the (total) bundle space. Connections between the (retarded) Green functions of the relativistic wave equations and the evolution operators and transports are found. Especially the Dirac and Klein-Gordon equations are considered.

arXiv:quant-ph/0107002•Jun 30, 2001•0 citations

Discrete Time Quantum Lattice Systems

Holger Vogts

Discrete time quantum lattice systems recently have come into the focus of quantum computation because they provide a versatile tool for many different applications and they are potentially implementable in current experimental realizations. In this thesis we study the fundamental structures of such quantum lattice systems as well as consequences of experimental imperfections. Essentially, there are two models of discrete time quantum lattice systems, namely quantum cellular automata and quantum walks, which are quantum versions of their classical counterparts, i.e., cellular automata and random walks. In both cases, the dynamics acts locally on the lattice and is usually also translationally invariant. The main difference between these structures is that quantum cellular automata can describe the dynamics of many interacting particles, where quantum walks describe the evolution of a single particle. The first part of this thesis is devoted to quantum cellular automata. We characterize one-dimensional quantum cellular automata in terms of an index theory up to local deformations. Further, we characterize in detail a subclass of quantum cellular automata by requiring that Pauli operators are mapped to Pauli operators. This structure can be understood in terms of certain classical cellular automata. The second part of this thesis is concerned with quantum walks. We identify a quantum walk with the one-particle sector of a quantum cellular automaton. We also establish an index theory for quantum walks and we discuss decoherent quantum walks, i.e., the behavior of quantum walks with experimental imperfections.

•Jun 25, 2009•6 citations
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.
The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of an alternating sequence of unitary operators: streaming of wavefunction values to adjacent points, and a Hadamard-type unitary matrix to blend pairs of values at individual points. Each operator generates the exact evolution due to part of the Hamiltonian for the one-dimensional Dirac equation over a finite time step. Composing these operators thus creates a discrete approximation to the Dirac equation. However, the composition of two non-commuting operators creates a global splitting error proportional to the length of the time step. The global error can be reduced from first order to second order in the time step by a unitary pre- and post-processing of the initial conditions and final output. The algorithm then becomes equivalent to a symmetric composition, a Strang splitting, between the two operators. This paper describes a fourth-order accurate composition scheme using nine stages, the fewest possible when the lengths of the time steps employed in the different stages are constrained to be integer multiples of some base time step. Each stage is itself a symmetric composition between two operators. This fourth-order scheme produces quantitatively smaller errors for a typical benchmark problem on spatial lattices with 1024 or more points, and shows the expected fourth-order convergence on sufficiently fine lattices. It has greater accuracy, over sufficiently long times, than three better-known fourth-order composition schemes using fewer stages, but with lengths related by irrational coefficients. The truncation error for plane-wave solutions is due to an operator that separates into a resonant part proportional to the Hamiltonian, and a non-resonant part orthogonal to the Hamiltonian. The resonant part commutes with the exact evolution operator, so its error accumulates to grow linearly with time. The orthogonal part produces oscillations that remain bounded over many time steps. The nine-stage integer scheme has the smallest resonant truncation error of the four schemes, despite being the only scheme that can be implemented using local operations. The other schemes implement streaming by irrational fractions of the lattice spacing using discrete Fourier transforms. • A fourth-order accurate quantum algorithm using local operations on regular lattices. • Higher quantitative accuracy for relevant problem sizes than existing schemes. • Higher long-time accuracy than standard fourth-order schemes with global operations. • Discrete invariants give fourth and higher order approximations to the energy.
One of the most accurate methods for solving the time-dependent Schrödinger equation uses a combination of the dynamic Fourier method with the split-operator algorithm on a tensor-product grid. To reduce the number of required grid points, we let the grid move together with the wavepacket but find that the naïve algorithm based on an alternate evolution of the wavefunction and grid destroys the time reversibility of the exact evolution. Yet, we show that the time reversibility is recovered if the wavefunction and grid are evolved simultaneously during each kinetic or potential step; this is achieved by using the Ehrenfest theorem together with the splitting method. The proposed algorithm is conditionally stable, symmetric, and time-reversible and conserves the norm of the wavefunction. The preservation of these geometric properties is shown analytically and demonstrated numerically on a three-dimensional harmonic model and collinear model of He–H2 scattering. We also show that the proposed algorithm can be symmetrically composed to obtain time-reversible integrators of an arbitrary even order. We observed 10 000-fold speedup by using the tenth-order instead of the second-order method to obtain a solution with a time discretization error below 10−9. Moreover, using the adaptive grid instead of the fixed grid resulted in a 64-fold reduction in the required number of grid points in the harmonic system and made it possible to simulate the He–H2 scattering for six times longer while maintaining reasonable accuracy. Applicability of the algorithm to high-dimensional quantum dynamics is demonstrated using the strongly anharmonic eight-dimensional Hénon–Heiles model.
We survey and develop the most elementary model of electron motion introduced by R...Feynman. In this game, a checker moves on a checkerboard by simple rules, and we count the turns. Feynman checkers are also known as a one-dimensional quantum walk or an Ising model at imaginary temperature. We solve mathematically a problem by R...Feynman from 1965, which was to prove that the discrete model (for large time, small average velocity, and small lattice step) is consistent with the continuum one. We study asymptotic properties of the model (for small lattice step and large time) improving the results by J...Narlikar from 1972 and by T...Sunada-T...Tate from 2012. For the first time we observe and prove concentration of measure in the small-lattice-step limit. We perform the second quantization of the model.
We propose a fibre bundle formulation of the mathematical base of relativistic quantum mechanics. At the present stage the bundle form of the theory is equivalent to its conventional one, but it admits new types of generalizations in different directions. In the present, second, part of our investigation, we consider a covariant approach to bundle description of relativistic quantum mechanics. In it the wavefunctions are replaced with (state) sections of a suitably chosen vector bundle over space-time whose (standard) fibre is the space of the wavefunctions. Now the quantum evolution is described as a linear transportation (by means of the transport along the identity map of the space\nobreakdash-time) of the state sections in the (total) bundle space. Connections between the (retarded) Green functions of the relativistic wave equations and the evolution operators and transports are found. Especially the Dirac and Klein-Gordon equations are considered.
Discrete time quantum lattice systems recently have come into the focus of quantum computation because they provide a versatile tool for many different applications and they are potentially implementable in current experimental realizations. In this thesis we study the fundamental structures of such quantum lattice systems as well as consequences of experimental imperfections. Essentially, there are two models of discrete time quantum lattice systems, namely quantum cellular automata and quantum walks, which are quantum versions of their classical counterparts, i.e., cellular automata and random walks. In both cases, the dynamics acts locally on the lattice and is usually also translationally invariant. The main difference between these structures is that quantum cellular automata can describe the dynamics of many interacting particles, where quantum walks describe the evolution of a single particle. The first part of this thesis is devoted to quantum cellular automata. We characterize one-dimensional quantum cellular automata in terms of an index theory up to local deformations. Further, we characterize in detail a subclass of quantum cellular automata by requiring that Pauli operators are mapped to Pauli operators. This structure can be understood in terms of certain classical cellular automata. The second part of this thesis is concerned with quantum walks. We identify a quantum walk with the one-particle sector of a quantum cellular automaton. We also establish an index theory for quantum walks and we discuss decoherent quantum walks, i.e., the behavior of quantum walks with experimental imperfections.