Loading Papermog
Preparing the latest research view.
Frontier Research Intelligence
Preparing the latest research view.
Research Paper
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution of linear system to accuracy with complexity independent of the condition number . We focus on the standard input model where is accessed through a block encoding and is prepared by a unitary. But we also introduce an affine dilation model that encodes and jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to and queries to . We prove a family of upper bounds on the effective condition number, including for positive even integer and for positive odd , overcoming the -barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.
In-App Reader
This document should be treated with critical skepticism. It contains unverified scientific claims or was self-published.