arXiv:2610.23138
Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling
Byeongyong Park, Keunhong Jeong, Doyeol Ahn
Abstract
To solve linear systems $Ax=b$, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian $H_b(A)=A^\dagger(I-|b\rangle\langle b|)A$, we measure quantum Krylov states $e^{-iAT}|b\rangle$ generated by the original Hermitian operator $A$ in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of $A^{-1}|b\rangle$ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound $κ$ on $A$, a lower bound $β_L$ on the solution probability weight of each of $L$ target basis states, and failure probability $δ$, signed-time sampling achieves $O(κ^2β_L^{-1}\log(L/δ))$ shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.
AI Summary
The paper asks whether computational-basis measurements of individual time-evolved states $e^{-iAT}|b\rangle$ can identify important coordinates of the normalized linear-system solution without coherently preparing $A^{-1}|b\rangle$. It proposes sampling these states, collecting observed basis strings, and classically diagonalizing $H_b(A)=A^\dagger(I-|b\rangle\langle b|)A$ projected onto their span. The output is a sparse classical approximation. For Hermitian invertible $A$ with spectrum in $[-B,-a]\cup[a,B]$ and $\kappa=B/a$, inverse representations with controlled coefficient norms yield coordinate-probability bounds through Cauchy–Schwarz. A continuous signed-time distribution gives $q(z)\geq |x_z|^2/O(\kappa^2)$, implying $O(\kappa^2\beta_L^{-1}\log(L/\delta))$ shots to discover $L$ target coordinates, each with solution weight at least $\beta_L$. Diagonal instances establish matching worst-case lower bounds within a model restricted to evolution followed by computational-basis measurement and observed-coordinate outputs. A finite nonnegative-time grid incurs an additional $\log^2(1/\beta_L)$ factor but bounds maximum evolution time by $O((1+\log(1/\beta_L))/a)$. The analysis also covers qDRIFT compilation, distinguishes independent circuit draws from repeated measurements of reused circuits, and bounds retained solution weight without minimum-coordinate assumptions. If the selected subspace misses solution weight $m$, exact variational reconstruction has infidelity at most $\min\{1,\kappa^2m\}$. Applicability requires concentrated solution amplitudes and suitable classical access to selected columns and input amplitudes. Signed-time sampling has unbounded evolution times unless truncated; compilation adds depth costs. Classical matrix construction and diagonalization can dominate, the final-reconstruction bound does not match the retained-mass lower bound, and no problem class with demonstrated quantum advantage is identified.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 19 pages, including appendices