01347nas a2200145 4500008004100000245012000041210006900161260001500230520084500245100002401090700001301114700001801127700001901145856003701164 2023 eng d00aThe discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver0 adiscrete adiabatic quantum linear system solver has lower consta c12/12/20233 a
The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number κ and the allowable error ϵ [PRX Quantum \textbf{3}, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.
1 aCosta, Pedro, C. S.1 aAn, Dong1 aBabbush, Ryan1 aBerry, Dominic uhttps://arxiv.org/abs/2312.0769001759nas a2200169 4500008004100000245008100041210006900122260001500191520123200206100002401438700001301462700002301475700001301498700001801511700002301529856003701552 2021 eng d00aOptimal scaling quantum linear systems solver via discrete adiabatic theorem0 aOptimal scaling quantum linear systems solver via discrete adiab c11/15/20213 aRecently, 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 enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of log(κ). 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. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity. Our O(κlog(1/ε)) complexity is also optimal in terms of the combined scaling in κ 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.
1 aCosta, Pedro, C. S.1 aAn, Dong1 aSanders, Yuval, R.1 aSu, Yuan1 aBabbush, Ryan1 aBerry, Dominic, W. uhttps://arxiv.org/abs/2111.08152