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.
Quantum Linear System Solver Based on Time-Optimal Adiabatic Quan- tum Computing and Quantum Approximate Op- timization Algorithm
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with $\mathcal{O}(\kappa~\text{poly}(\log(\kappa/\epsilon)))$ runtime, where $\kappa$ is the condition number, and $\epsilon$ is the target accuracy. This is near optimal with respect to both $\kappa$ and $\epsilon$. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding normalization under uniform or moment-based spectral models.
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/ε).
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Chebyshev-iteration solvers in numerical benchmarks.
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.
-
Constrained Optimal Polynomials for Quantum Linear System Solvers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding normalization under uniform or moment-based spectral models.
-
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/ε).
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Chebyshev-iteration solvers in numerical benchmarks.