Given a linear system of equations Ax = b, quantum linear system solvers (QLSSs) approximately prepare a quantum state |x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κ log(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection—a straightforward extension of the eigenstate filtering (EF) technique of previous work—and the query complexity of the QLSS is (1 + O(ε))κ ln(2√2/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(log log(κ)) applications of kernel projection—a direct generalization of EF—yielding a straightforward QLSS with near-optimal O(κ log log(κ) log log log(κ) + κ log(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ) complexity can be achieved for estimating the norm up to a constant factor, yielding an optimal QLSS with O(κ log(1/ε)) complexity while still avoiding the need to analyze the adiabatic theorem. Finally, we give explicit upper bounds on the constant prefactors of the complexity statements: we show that the query complexity of our optimal QLSS is at most 56κ + 1.05κ ln(1/ε) + o(κ), saving more than an order of magnitude compared to existing QLSS complexity guarantees.
Research areas
