Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
Optimal Scal- ing Quantum Linear-Systems Solver via Discrete Adiabatic Theorem
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
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 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 sub-optimal 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. 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 $\kappa$, matching a known lower bound on the complexity. Our $\mathcal{O}(\kappa\log(1/\epsilon))$ complexity is also optimal in terms of the combined scaling in $\kappa$ and the precision $\epsilon$. 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.
fields
quant-ph 3representative citing papers
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
citing papers explorer
-
Faster quantum linear system solver beyond the condition number
Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
-
Explicit Quantum Circuit Simulation of Nonlinear 1-Dimensional Fluid with Carleman-linearized Boltzmann Method
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).