by François Fillion-Gourdeau (Institute for Quantum Computing and Infinite Potential Laboratories)
Quantum algorithms have been developed to solve two important classes of partial differential equations: the Dirac equation and linear symmetric hyperbolic systems of equations. These algorithms can be much more efficient than their classical counterparts.
Quantum computing is at the heart of a new revolution in information science where quantum effects and quantum states are leveraged to perform calculations. In recent decades, significant scientific resources have been devoted to this subject. A functional quantum computer could solve computational problems that are unsolvable on a classical computer, owing to quantum algorithms being much more efficient for a large class of problems, and giving a polynomial or an exponential speedup over classical ones.
Since the seminal works of R. Feynman in the 1980s, there has been growing evidence for the efficiency of quantum algorithms to simulate the time-evolution of quantum systems. However, this quantum advantage is not as clear for classical systems modelled by time-dependent partial differential equations (PDE). In 2015, we started to work on this topic to determine if some PDEs could be solved on existing quantum computer prototypes, even though the latter have limited resources.
Simulating the time-evolution of a physical system on a quantum computer requires two main ingredients: i) a mapping of the solution on the quantum register and ii) a mapping of the time-evolution operator on a set of quantum logic gates. The quantum register is usually a set of many entangled two-level quantum systems (or qubits). The quantum gates are fundamental unitary operations that transform the quantum state of the register. A sequence of quantum gates forms a quantum circuit that actually performs a calculation and such calculations are efficient when asymptotically, the number of quantum gates is lower than the number of operations required on a classical computer. In our work, we applied these principles to develop quantum algorithms that solve the Dirac equation [1] and symmetric linear hyperbolic systems of equations [2] more efficiently than on a classical computer.
The Dirac equation is one of the most important partial differential equations in theoretical physics because it describes relativistic fermions, like electrons or quarks, and some exotic systems in condensed matter physics called Dirac materials. To obtain a quantum algorithm, our approach was to adapt a known classical numerical scheme that solves the Dirac equation on a discrete spatial grid. For this purpose, we used amplitude encoding where the discrete wave function is stored in the quantum register probability amplitudes. The evolution operator was then approximated by a succession of streaming and spin rotation unitary steps. We have demonstrated that these steps can be decomposed as a sequence of quantum gates because they are unitary. The number of quantum gates to perform the spin rotation operation is small and does not scale with the number of grid points. In contrast, the streaming operation necessitates a quantum conditional shift operator, which is much more intricate and which requires more quantum gates as the number of grid points is increased. Nevertheless, we have found that this algorithm, reminiscent of quantum walks [3] and displayed in Figure 1, has an exponential speedup compared to its classical counterpart for a large number of grid points. Therefore, our algorithm is efficient, as confirmed by obtaining explicit quantum gate decompositions using the quantum compiler Quipper.
![Figure 1: Quantum circuit for one time step of the free Dirac equation algorithm. The shit operator are denoted by S and the rotation operator by R. Adapted from Ref. [1].](/images/stories/EN128/fillion.png "Figure 1: Quantum circuit for one time step of the free Dirac equation algorithm. The shit operator are denoted by S and the rotation operator by R. Adapted from Ref. [1].")
Figure 1: Quantum circuit for one time step of the free Dirac equation algorithm. The shit operator are denoted by S and the rotation operator by R. Adapted from Ref. [1].
A similar approach can be used to solve linear symmetric hyperbolic system of equations. These equations, characterised by symmetric coefficient matrices with real eigenvalues, are important because they describe many classical systems. Typical examples include the advection, the 1-D Maxwell, the telegraph and the linearised Euler equations. To solve these equations numerically, we used the reservoir method along with operator splitting. This combination of methods allowed us to map them onto a quantum walk algorithm, analogous to the one for the Dirac equation, with a diagonalisation and a shift operator (see Figure 1). However, the main challenge was the determination of the time steps, especially when the eigenvalues of the hyperbolic systems are not commensurate. We demonstrated that the time steps can actually be pre-computed efficiently using a simple classical algorithm. Then we performed a complexity analysis that demonstrated an exponential speedup of our algorithm, under some conditions, over the same algorithm implemented on a classical computer.
Although our results look promising for time-dependent problems, there are some other factors that limit the performance. First, the initialisation of the quantum register can be costly. There are some efficient alternatives for some classes of functions, but generally the quantum version is not more efficient than the classical version. Second, the reading of the solution requires the reconstruction of all probability amplitudes of the quantum register, a process called quantum tomography. This cannot be performed efficiently. How to manage these issues is still an open problem for many quantum simulation algorithms.
In the future, we would like to run these algorithms on actual quantum computers. Although we do not expect to reach quantum supremacy in the short term, this would be an important proof-of-principle experiment. Also, we would like to investigate if these algorithms can be generalised to non-linear partial differential equations like the Navier-Stokes equation. These equations of paramount importance in the development of new technologies and for our understanding of many physical systems. We hope, in the long term, that the quantum approach could improve our knowledge of these complex systems.
References:
[1] F. Fillion-Gourdeau, S. MacLean, and R. Laflamme: “Algorithm for the solution of the Dirac equation on digital quantum computers”, Physical Review A 95.4 (2017): 042343.
[2] F. Fillion-Gourdeau, E. Lorin: “Simple digital quantum algorithm for symmetric first-order linear hyperbolic systems”, Numerical Algorithms 82.3 (2019): 1009-1045.
[3] S. Succi, F. Fillion-Gourdeau, and S. Palpacelli: “Quantum lattice Boltzmann is a quantum walk”, EPJ Quantum Technology 2.1 (2015): 1-17.
Please contact:
François Fillion-Gourdeau
Institute for Quantum Computing and Infinite Potential Labs, Canada
