arXiv:2609.19676
Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
Yin Yang, Yue Yu, Long Zhang
Abstract
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ 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 $\bb{x}$ 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 $\mathcal{O}(κ_A\log\frac1\varepsilon)$ without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
AI Summary
The paper asks whether an ODE-inspired quantum linear systems algorithm can attain optimal matrix-query complexity without variable-time amplitude amplification. It develops “LC-Schrödingerization,” representing $A^{-1}b$ as a time integral of solutions to auxiliary convection equations, whose Fourier modes evolve unitarily under Hamiltonians proportional to $A$. Non-Hermitian systems are handled through Hermitian dilation. The construction initializes the auxiliary coordinate with the derivative of a Gaussian-smoothed hat function. Shrinking the smoothing width with target error permits truncation at $T=3\alpha_{A^{-1}}$, independent of accuracy. Recovering the solution over a fixed auxiliary interval, rather than at one grid point, cancels grid-dependent normalization losses. Explicit Fourier coefficients bound projection error; composite Gaussian quadrature discretizes time. Two LCU layers implement time marching and integration, with entire select operators simulated directly as block-diagonal Hamiltonian evolutions. Before preconditioning, the matrix-query bound is $\mathcal{O}(\kappa_A^2/(\alpha_A\xi)\log[\kappa_A/(\alpha_A\xi\varepsilon)])$, where $\xi=\|A^{-1}|b\rangle\|$ and $\kappa_A=\alpha_A\alpha_{A^{-1}}$. Applying an existing block preconditioner yields $\mathcal{O}(\kappa_A\log(1/\varepsilon))$ queries to both the matrix block-encoding and right-hand-side preparation oracle, matching the known optimal worst-case matrix-query scaling. The output has $\mathcal{O}(\varepsilon)$ trace-distance error and constant success probability. These bounds assume exact block-encoding access, auxiliary-state preparation oracles, supplied normalization bounds, and a constant-factor solution-norm estimate; acquiring that estimate and auxiliary preparation gate costs are excluded. Simulations use a $2\times2$ system with condition number two and illustrate kernel accuracy and interval recovery, but omit Hamiltonian-simulation approximation, amplitude amplification, and preconditioning. A complete gate-level resource analysis remains open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.