Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
Abstract
Quantum linear systems algorithms (QLSAs) aim to solve linear systems Abbx=bbb exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution bbx as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity 𝒪(κAlog1/ε) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
Related
- Schrödingerization for quantum linear systems problems
- Quantum simulation of classical RCL circuits via complexification and Schrödingerization
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- Optimal query complexity for fractional quantum evolution
BibTeX
@misc{yang2026linear,
title = {{Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity}},
author = {Yin Yang and Yue Yu and Long Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19676},
eprint = {2609.19676},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19676},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
AU - Yin Yang
AU - Yue Yu
AU - Long Zhang
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19676
UR - https://arxiv.org/abs/2609.19676
AB - Quantum linear systems algorithms (QLSAs) aim to solve linear systems Abbx=bbb exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution bbx as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity 𝒪(κ_Alog1/ε) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
ER -