Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.19676

Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity

Yin Yang, Yue Yu, Long Zhang

quant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 2 citations
arXivHTMLPDF

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.

Little sign of AI-generated textIncrementalStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Schrödingerization for quantum linear systems problems

Yin Yang, Yue Yu, Long Zhang

We develop a Schrödingerization algorithm for quantum linear systems problems in two higher dimensions. The earlier LC-Schrödingerization approach represents the solution as a time integral of a homogeneous convection response and implements this integral by a linear combination of unitaries (LCU) over evolution times. We instead use Duhamel's principle to incorporate the integral into an inhomogeneous convection equation with zero initial data. Fourier projection in the convection variable and Schrödingerization in a second auxiliary variable then realize the solution without the separate LCU step. A joint choice of the kernel and recovery procedure gives an evolution time independent of the target accuracy, a uniformly bounded $L^2$ kernel normalization, and accurate recovery on a fixed interval. We establish the periodization and discretization bounds and analyze the interval recovery probability. With block preconditioning, we retain a single logarithmic precision factor and obtain linear condition-number dependence without variable-time amplitude amplification. Under exact oracle access and given a valid constant-factor solution-norm estimate, the algorithm uses $\mathcal O(κ_A\log(1/\varepsilon))$ queries to each original input oracle, with constant success probability and $\ell^2$ state error at most $\varepsilon$. The matrix-query bound matches the standard worst-case scaling when the supplied norm bounds are tight. UnitaryLab simulations on positive-definite and indefinite systems demonstrate the solution accuracy and probability gain from interval recovery.

quant-pharXiv:2609.25660•Sep 23, 2026•1 citation

Schrödingerization for quantum linear systems problems with near-optimal dependence on matrix queries

Yin Ping Yang, Yue Yu, Long Zhang

We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.

arXiv:2508.13510•Aug 19, 2025•3 citations

Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

Sophia Simon, Dominic W. Berry, Rolando D. Somma

We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity $\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)$, where the constant $ν$ depends on the problem parameters, $\mathcal{L}$ involves a time integral of upper bounds on the norms of evolution operators, and $ε$ is the error. In particular, $ν\mathcal{L}$ is linear in $t$ for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of $Ω(ν\mathcal{L} t/ε)$ for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.

quant-pharXiv:2605.16195•May 18, 2026•2 citations

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686•Sep 29, 2026•1 citation

Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schrödingerization

Shi Jin, Nana Liu, Chuwen Ma +1 more

We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix $A_S = S^\top A S$, where $A$ is the stiffness matrix and $S$ encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of $A_S$ with normalization $\mathcal{O}(d^2(L+1))$, where $d$ is the spatial dimension and $L$ is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of $\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)$ for estimating linear functionals of the solution to a given tolerance $\varepsilon$.

arXiv:2505.06866•May 11, 2025•16 citations

Quantum Algorithm for Linear Non-unitary Dynamics with Near-Optimal Dependence on All Parameters

Dong An, Andrew M. Childs, Lin Lin

Abstract We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

arXiv:2312.03916•Communications in Mathematical Physics•Dec 8, 2025•117 citations
Quantum linear systems algorithms (QLSAs) aim to solve linear systems A\bbx=\bbbA\bb{x}=\bb{b}A\bbx=\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\bb{x}\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 O(κAlog⁡1ε)\mathcal{O}(κ_A\log\frac1\varepsilon)O(κA​logε1​) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
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−1bA^{-1}bA−1b as a time integral of solutions to auxiliary convection equations, whose Fourier modes evolve unitarily under Hamiltonians proportional to AAA. 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αA−1T=3\alpha_{A^{-1}}T=3α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 O(κA2/(αAξ)log⁡[κA/(αAξε)])\mathcal{O}(\kappa_A^2/(\alpha_A\xi)\log[\kappa_A/(\alpha_A\xi\varepsilon)])O(κA2​/(αA​ξ)log[κA​/(αA​ξε)]), where ξ=∥A−1∣b⟩∥\xi=\|A^{-1}|b\rangle\|ξ=∥A−1∣b⟩∥ and κA=αAαA−1\kappa_A=\alpha_A\alpha_{A^{-1}}κA​=αA​αA−1​. Applying an existing block preconditioner yields O(κAlog⁡(1/ε))\mathcal{O}(\kappa_A\log(1/\varepsilon))O(κA​log(1/ε)) 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 O(ε)\mathcal{O}(\varepsilon)O(ε) 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×22\times22×2 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.
We develop a Schrödingerization algorithm for quantum linear systems problems in two higher dimensions. The earlier LC-Schrödingerization approach represents the solution as a time integral of a homogeneous convection response and implements this integral by a linear combination of unitaries (LCU) over evolution times. We instead use Duhamel's principle to incorporate the integral into an inhomogeneous convection equation with zero initial data. Fourier projection in the convection variable and Schrödingerization in a second auxiliary variable then realize the solution without the separate LCU step. A joint choice of the kernel and recovery procedure gives an evolution time independent of the target accuracy, a uniformly bounded L2L^2L2 kernel normalization, and accurate recovery on a fixed interval. We establish the periodization and discretization bounds and analyze the interval recovery probability. With block preconditioning, we retain a single logarithmic precision factor and obtain linear condition-number dependence without variable-time amplitude amplification. Under exact oracle access and given a valid constant-factor solution-norm estimate, the algorithm uses O(κAlog⁡(1/ε))\mathcal O(κ_A\log(1/\varepsilon))O(κA​log(1/ε)) queries to each original input oracle, with constant success probability and ℓ2\ell^2ℓ2 state error at most ε\varepsilonε. The matrix-query bound matches the standard worst-case scaling when the supplied norm bounds are tight. UnitaryLab simulations on positive-definite and indefinite systems demonstrate the solution accuracy and probability gain from interval recovery.
We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.
We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity O~(νLt/ε)\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)O(νLt/ε), where the constant ννν depends on the problem parameters, L\mathcal{L}L involves a time integral of upper bounds on the norms of evolution operators, and εεε is the error. In particular, νLν\mathcal{L}νL is linear in ttt for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of Ω(νLt/ε)Ω(ν\mathcal{L} t/ε)Ω(νLt/ε) for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UAU_AUA​ and the right-hand side through a state-preparation oracle UbU_bUb​. The optimal query complexities of these two oracles are known separately: O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) queries to UAU_AUA​ and O(κ/s)O(κ/s)O(κ/s) queries to UbU_bUb​, where s=α∥A−1b∥s=α\|A^{-1}b\|s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of sss, we give a quantum linear-system algorithm that prepares the normalized solution to error ε\varepsilonε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UAU_AUA​ and O(κ/s)O\left(κ/{s}\right)O(κ/s) queries to UbU_bUb​. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)) matrix queries and Ω(κ/s)Ω(κ/s)Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix AS=S⊤ASA_S = S^\top A SAS​=S⊤AS, where AAA is the stiffness matrix and SSS encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of ASA_SAS​ with normalization O(d2(L+1))\mathcal{O}(d^2(L+1))O(d2(L+1)), where ddd is the spatial dimension and LLL is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of O(poly(d)ε−1polylog(ε−1))\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)O(poly(d)ε−1polylog(ε−1)) for estimating linear functionals of the solution to a given tolerance ε\varepsilonε.
Abstract We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.