Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling
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 Hb(A)=A†(I−|b⟩⟨ b|)A, we measure quantum Krylov states e−iAT|b⟩ 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⟩ 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−1log(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.
Related
- A scalable sample-based quantum diagonalization solver for general Pauli-sum Hamiltonians
- Green's Functions from Sample-based Krylov Quantum Diagonalization: An Impurity Solver for Dynamical Mean-Field Theory
- A Simple Quantum Linear-System Solver via Dissipation
- PyQLAS: A Quantum-Classical Hybrid Solver Library for Linear Systems
- Finite-Element Electromagnetic Analysis and Evaluation of Antenna Performance Metrics Using a Quantum Linear System Solver
BibTeX
@misc{park2026samplebased,
title = {{Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling}},
author = {Byeongyong Park and Keunhong Jeong and Doyeol Ahn},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23138},
eprint = {2610.23138},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23138},
}
RIS
TY - UNPB
TI - Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling
AU - Byeongyong Park
AU - Keunhong Jeong
AU - Doyeol Ahn
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23138
UR - https://arxiv.org/abs/2610.23138
AB - 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^†(I−|b⟩⟨ b|)A, we measure quantum Krylov states e^−iAT|b⟩ 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⟩ 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^−1log(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.
ER -