pipette
ESEspañol

Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling

Byeongyong Park, Keunhong Jeong, Doyeol Ahn

Preprint

In the authors' words

To solve linear systems , we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian , we measure quantum Krylov states generated by the original Hermitian operator in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of 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 lower bound on the solution probability weight of each of target basis states, and failure probability , signed-time sampling achieves 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.

Main resultLimitation the authors admit

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 19 pages, including appendices