Description
Quantum computers offer the prospect of exponential speedups for solving large linear systems. Quantum linear systems algorithms (QLSAs) prepare a quantum state encoding the solution of a linear system $Ax = b$, but many practical applications also require the norm of the solution. For example, when modelling fluid flow by discretising the governing equations, the solution vector encodes the velocity field at each grid point, and its norm captures the overall magnitude of the flow, a physically meaningful quantity that is not recoverable from the normalised quantum state alone.
Recently, an optimally scaling QLSA called the shortcut method has been discovered (Dalzell, 2024, arXiv:2406.12086). It entails solving a linear system in which approximate norm estimation arises as a natural intermediate step, rather than being treated as a separate post-processing task. We present a norm-estimation protocol that expands on this work. Our method produces an estimate of the norm to any desired accuracy with high-probability guarantees, with complexity scaling as $\mathcal{O}(\kappa \log(1/\epsilon)/\epsilon)$, which is optimal in both condition number $\kappa$ and the desired precision $\epsilon$ up to logarithmic factors.
The protocol proceeds in two stages. First, an adaptive amplitude estimation procedure is used to obtain a coarse estimate of the norm at low query cost, guided by an information-theoretic criterion: at each round, circuit parameters are chosen to maximise the expected information gain given prior measurements. This coarse estimate is then used to encode the true norm in an amplitude that is highly sensitive to the remaining uncertainty. In the second stage, amplitude estimation with a discrete prolate spheroidal sequence (DPSS) window function is applied to this well-conditioned amplitude, yielding a precise estimate with high-probability guarantees.
| I am the presenting author | Yes |
|---|