Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches have enabled near-linear scaling in the condition number $\kappa$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically suboptimal by a factor of $\log (\kappa )$. Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete-time evolutions. In combination with the qubitized quantum walk, our discrete adiabatic theorem gives a speed-up for all adiabatic algorithms. Here, we use this combination to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in $\kappa$, matching a known lower bound on the complexity. Our $\mathcal{O}[\kappa \log (1/ϵ)]$ complexity is also optimal in terms of the combined scaling in $\kappa$ and the precision $ϵ$. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

Popular Summary

Quantum computers offer the prospect of providing an exponential speed-up, in the dimension, for solving linear systems of equations. This was originally proposed in the work of Harrow, Hassidim, and Lloyd (HHL) in 2009, and since then has been used as the basis for a whole host of new quantum algorithms for tasks such as machine learning, data analysis, least-squares fitting, and solution of partial differential equations. The last is the most significant because partial differential equations are the key computational problem at the heart of a huge number of applications in science and engineering.

Although the HHL algorithm has logarithmic complexity in the dimension, it turns out to have complexity scaling as the square of the condition number for the system. In contrast, the lower bound that HHL proves is linear complexity in the condition number. In more than a decade of progress since then, the complexity of quantum algorithms for linear systems has gradually been improved but has never reached this lower bound. Here, we finally reach the lower bound for the complexity of solving linear systems, thereby providing the optimal quantum algorithm. In turn, this immediately speeds up all the algorithms that are based on solving linear systems.

In order to do this, we take the common method of adiabatic evolution under a slowly changing Hamiltonian and replace it with discrete adiabatic evolution under a quantum walk. This is a general method that can be applied to any quantum algorithm based on adiabatic evolution, and it provides a speed-up because the walk is easier to implement than Hamiltonian evolution. Therefore, our method potentially has many applications in other areas where adiabatic evolution is used; for example, discrete optimization.

Figure 1

An illustration of the choice of the contour $\mathrm{\Gamma }(s,k)$ for $k=0$. That is, we consider the eigenvalues for only a single step of the walk. The red dots indicate the spectrum of interest, which will often just be a single eigenvalue; for example, for a ground state. The contour around the spectrum of interest is used to obtain a projector onto the spectrum of interest. For the illustration, we use a contour with radius $2$ but in practice, we take the limit that the radius goes to infinity.

Figure 2

The upper bound on the error in the adiabatic evolution versus the condition number $\kappa$ for a range of values of $p$ used in the scheduling function $f(s)$. The upper bound on the error is computed using Theorem 7 and in all cases the number of steps of the walk is $T={10}^5$.

Figure 3

The upper bound on the error in the adiabatic evolution as a function of $p$ used in the scheduling function $f(s)$. In this plot, we use constant values $\kappa =40$ and $T={10}^5$.

Figure 4

A linear combination of steps using control registers prepared in unary using a linear sequence of controlled rotations. The state $|\psi ⟩$ would be the state output by the adiabatic walk and $W$ is used to indicate the final walk step $W(1)$ from the adiabatic walk. In this example, the four control qubits would encode $|j⟩$ in unary and the rotations would prepare the amplitudes proportional to $\sqrt{w_j}$. The rotations on the right invert this preparation. Given that the control qubits are measured in the state $|0⟩$, the target will be in a state proportional to that given in Eq. (108).

Figure 5

A linear combination of steps using control registers prepared in unary using a linear sequence of controlled rotations but with the inverse preparation performed with the linear sequence in the reverse order.

Figure 6

A linear combination of steps using control registers prepared in unary but with the order of the operations changed so that we only need to use two ancilla qubits at a time.

Figure 7

An illustration of the choice of the contour $\mathrm{\Gamma }(s,k)$ for $k=1$. That is, there are two successive steps of the walk and we would need to consider the spectrum for both. We need to be able to use a contour that separates out the spectrum of interest for both steps of the walk. This ensures that we have projectors onto the spectrum of interest that are consistent for both steps, with a gap between the contour and the eigenvalues. We do not allow eigenvalues of interest to cross the gap between one step and the next. Again, we show a contour with radius $2$ but we would take the infinite limit of the radius.

Figure 8

The contour $\mathrm{\Gamma }(s,1,a)$ that passes through the two gaps and has a closure of the contour via an arc at radius $a+1$. The centers of the two gaps are denoted $g_{1,1}(s)$ and $g_{2,1}(s)$ and the contour is taken to have two straight lines that are multiples of these complex numbers.

Figure 9

The block encoding of the Hamiltonian $H(s)$, where the target system is labeled as $|\psi ⟩$ and the ancillas are labeled $a_1$–$a_4$ and $a$ (where $a$ is the ancilla needed in the block encoding of $A$). The dashed boxes show $C{U}_{Qb}^1$ and $U_{A(f)}$, whereas the dotted boxes show $C{R}^0(s)$. The ${\sigma }^x$ on ancilla $a_4$ has been moved to the middle, so the operations $C{U}_{Qb}^0$ and $C{R}^1(s)$ are implemented via $C{U}_{Qb}^1$ and $C{R}^0(s)$.