Efficient quantum linear solver algorithm with detailed running costs
share
As we progress towards physical implementation of quantum algorithms it is vital to determine the explicit resource costs needed to run them. Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Here we introduce a quantum linear solver algorithm combining ideas from adiabatic quantum computing with filtering techniques based on quantum signal processing. We give a closed formula for the non-asymptotic query complexity Q – the exact number of calls to a block-encoding of the linear system matrix – as a function of condition number κ, error tolerance ϵ and block-encoding scaling factor α. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations. The asymptotic scaling is O(κlog(κ/ϵ)), slightly looser than the O(κlog(1/ϵ)) scaling of the asymptotically optimal algorithm of Costa et al. However, our algorithm outperforms the latter for all condition numbers up to κ≈ 10^32, at which point Q is comparably large, and both algorithms are anyway practically unfeasible. The present optimized analysis is both problem-agnostic and architecture-agnostic, and hence can be deployed in any quantum algorithm that uses linear solvers as a subroutine.
READ FULL TEXT