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:2610.02939

Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon, Guang Hao Low

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 1 citation
arXivHTMLPDF

Abstract

We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $η$, evolution for time $t$ to error $ε$ uses $\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))$ queries, where $τ=η|t|$. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar g$ bounds the ratio of combined input and source norms to the final-solution norm, and $C$ is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.

AI Summary

The paper addresses whether sparse-access Hamiltonian simulation and quantum linear-equation algorithms can achieve square-root sparsity dependence without subpolynomial overheads. Its access model supplies entry values and reversible row/column locators with inverse-location access; state-preparation costs are counted separately. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $\eta$, simulation for time $t$ to error $\epsilon$ uses $O(\sqrt{s}\tau+\sqrt{s\tau L}+L)$ queries, where $\tau=\eta|t|$ and $L=\log(1/\epsilon)$. The bound extends to time-dependent Hamiltonians given coherent sampled-time access and certified discretisation. A lower bound $\Omega(\sqrt{s}\tau+\sqrt{s\tau r}+r)$, with $r=L/\log(e+L/\tau)$, rules out uniformly additive time and precision costs but leaves logarithmic gaps. Constant-error implementation of an arbitrary $N\times N$ unitary follows with $O(\sqrt N)$ entry queries. The construction uses an exact entrywise Cayley representation with bounded compressed second moment, transducers, and resolvent-based filtering. Linear-combination-of-Hamiltonian-simulations methods yield dissipative ODE solvers costing $O(\bar g[\sqrt{s}(\tau+\sqrt\tau)+1]\log(C\bar g/\epsilon))$, where $\bar g$ bounds input/source norm relative to final-solution norm. A kernel walk and Chebyshev filter solve linear systems in $O(\kappa\sqrt{s}\log(1/\epsilon))$ queries, matching a joint lower bound under $\|A\|\le1$ and $\|A^{-1}\|\le\kappa$. ODE outputs and linear-system solutions are amplitude-encoded states. Dissipative precision optimality remains unresolved. Gate-efficient implementations cover time-independent simulation and dissipative ODEs under additional arithmetic, decoding, and preparation assumptions, not all extensions.

Little sign of AI-generated textStrong assumptions

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

Comments
67 pages

Related papers

Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm

Zecheng Li, Chunhao Wang

We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $Λ$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $tΛ\ge1/2$, simulation with operator-norm error $ε$ uses \[ O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) \] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For $d>1$ and $tΛ\ge\log(2/ε)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $Λ$. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain $O(κ\sqrt d\,\mathrm{polylog}(κ/ε))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\leκ$, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most $d$ nonzero entries per row and column using $O(\sqrt d\log(2/ε))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $Θ(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].

quant-pharXiv:2610.02030•Oct 2, 2026•0 citations

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers

Dhrumil Patel

Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number $κ$, the sparsity $s$ of the input matrix, and the target precision $\varepsilon$. The dependence on $κ$ and $\varepsilon$ is already well understood through the lower bound $Ω(κ\log(1/\varepsilon))$, which matches the best known scaling in these parameters. Once the sparsity $s$ is included, however, the expected lower bound has long been conjectured to be $Ω(κ\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $Ω(κ\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $Ω(κ\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.

quant-pharXiv:2609.22445•Sep 22, 2026•5 citations

Hamiltonian simulation with nearly optimal dependence on spectral norm

Guang Hao Low

We present a quantum algorithm for approximating the real time evolution e−iHt of an arbitrary d-sparse Hamiltonian to error є, given black-box access to the positions and b-bit values of its non-zero matrix entries. The query complexity of our algorithm is O((t√d||H||1 → 2)1+o(1)/єo(1)) with respect to the largest Euclidean row norm ||H||1 → 2, which is shown to be optimal up to subpolynomial factors through a matching lower bound, and it uses a factor O(b) more gates. This provides a polynomial speedup in sparsity for the common case where the spectral norm is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem – O(d1/2+o(1)) queries suffice to approximate any d-sparse unitary in the black-box setting, which matches the quantum search lower bound of Ω(√d) queries and improves upon prior art [Berry and Childs, QIP 2010] of Õ(d2/3) queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number κ using O((κ √d)1+o(1)/єo(1)) queries, which is a quadratic improvement in sparsity.

arXiv:1807.03967•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•54 citations

Quantum simulation of slow analytic time-dependent Hamiltonians

Chenhao Zhao, Yinan Li, Dong An

We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leqα$ that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of $H(s)$, together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity $\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)$ and additional gate complexity $\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)$, assuming coherent access to $H'(s)$ and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations.

quant-pharXiv:2608.17653•Aug 19, 2026•1 citation

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

Dominic William Berry, Andrew M. Childs, Robin Kothari

We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product tau of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sub linear dependence on tau.

arXiv:1501.01715•Annual Symposium on Foundations of Computer Science•Oct 1, 2015•480 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
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an sss-sparse Hermitian matrix with row and column Euclidean norms bounded by ηηη, evolution for time ttt to error εεε uses O(sτ+sτlog⁡(1/ε)+log⁡(1/ε))\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))O(s​τ+sτlog(1/ε)​+log(1/ε)) queries, where τ=η∣t∣τ=η|t|τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ\sqrt{s}τs​τ and log⁡(1/ε)\log(1/ε)log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log⁡(Cgˉ/ε))\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))O(gˉ​[s​(τ+τ​)+1]log(Cgˉ​/ε)) queries, where τττ is the evolution time multiplied by a norm bound, gˉ\bar ggˉ​ bounds the ratio of combined input and source norms to the final-solution norm, and CCC is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog⁡(1/ε))\mathcal{O}(κ\sqrt{s}\log(1/ε))O(κs​log(1/ε)) queries when ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\leκ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
The paper addresses whether sparse-access Hamiltonian simulation and quantum linear-equation algorithms can achieve square-root sparsity dependence without subpolynomial overheads. Its access model supplies entry values and reversible row/column locators with inverse-location access; state-preparation costs are counted separately.
For an sss-sparse Hermitian matrix with row and column Euclidean norms bounded by η\etaη, simulation for time ttt to error ϵ\epsilonϵ uses O(sτ+sτL+L)O(\sqrt{s}\tau+\sqrt{s\tau L}+L)O(s​τ+sτL​+L) queries, where τ=η∣t∣\tau=\eta|t|τ=η∣t∣ and L=log⁡(1/ϵ)L=\log(1/\epsilon)L=log(1/ϵ). The bound extends to time-dependent Hamiltonians given coherent sampled-time access and certified discretisation. A lower bound Ω(sτ+sτr+r)\Omega(\sqrt{s}\tau+\sqrt{s\tau r}+r)Ω(s​τ+sτr​+r), with r=L/log⁡(e+L/τ)r=L/\log(e+L/\tau)r=L/log(e+L/τ), rules out uniformly additive time and precision costs but leaves logarithmic gaps. Constant-error implementation of an arbitrary N×NN\times NN×N unitary follows with O(N)O(\sqrt N)O(N​) entry queries.
The construction uses an exact entrywise Cayley representation with bounded compressed second moment, transducers, and resolvent-based filtering. Linear-combination-of-Hamiltonian-simulations methods yield dissipative ODE solvers costing O(gˉ[s(τ+τ)+1]log⁡(Cgˉ/ϵ))O(\bar g[\sqrt{s}(\tau+\sqrt\tau)+1]\log(C\bar g/\epsilon))O(gˉ​[s​(τ+τ​)+1]log(Cgˉ​/ϵ)), where gˉ\bar ggˉ​ bounds input/source norm relative to final-solution norm. A kernel walk and Chebyshev filter solve linear systems in O(κslog⁡(1/ϵ))O(\kappa\sqrt{s}\log(1/\epsilon))O(κs​log(1/ϵ)) queries, matching a joint lower bound under ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\le\kappa∥A−1∥≤κ.
ODE outputs and linear-system solutions are amplitude-encoded states. Dissipative precision optimality remains unresolved. Gate-efficient implementations cover time-independent simulation and dissipative ODEs under additional arithmetic, decoding, and preparation assumptions, not all extensions.
We give a quantum algorithm for simulating a ddd-sparse Hermitian Hamiltonian HHH, assuming a known upper bound ΛΛΛ on its maximum column Euclidean norm ∥H∥1→2\|H\|_{1\to2}∥H∥1→2​. For tΛ≥1/2tΛ\ge1/2tΛ≥1/2, simulation with operator-norm error εεε uses O ⁣(tΛd+dlog⁡(2/ε)) O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) O(tΛd​+d​log(2/ε)) sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1d>1d>1 and tΛ≥log⁡(2/ε)tΛ\ge\log(2/ε)tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of ΛΛΛ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain O(κd polylog(κ/ε))O(κ\sqrt d\,\mathrm{polylog}(κ/ε))O(κd​polylog(κ/ε)) queries for solving ddd-sparse quantum linear systems with ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\leκ∥A−1∥≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most ddd nonzero entries per row and column using O(dlog⁡(2/ε))O(\sqrt d\log(2/ε))O(d​log(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N)Θ(\sqrt N)Θ(N​) queries for arbitrary N×NN\times NN×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].
Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number κκκ, the sparsity sss of the input matrix, and the target precision ε\varepsilonε. The dependence on κκκ and ε\varepsilonε is already well understood through the lower bound Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity sss is included, however, the expected lower bound has long been conjectured to be Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(1/ε)). Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound Ω(κs)Ω(κ\sqrt{s})Ω(κs​) for constant error ε\varepsilonε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
We present a quantum algorithm for approximating the real time evolution e−iHt of an arbitrary d-sparse Hamiltonian to error є, given black-box access to the positions and b-bit values of its non-zero matrix entries. The query complexity of our algorithm is O((t√d||H||1 → 2)1+o(1)/єo(1)) with respect to the largest Euclidean row norm ||H||1 → 2, which is shown to be optimal up to subpolynomial factors through a matching lower bound, and it uses a factor O(b) more gates. This provides a polynomial speedup in sparsity for the common case where the spectral norm is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem – O(d1/2+o(1)) queries suffice to approximate any d-sparse unitary in the black-box setting, which matches the quantum search lower bound of Ω(√d) queries and improves upon prior art [Berry and Childs, QIP 2010] of Õ(d2/3) queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number κ using O((κ √d)1+o(1)/єo(1)) queries, which is a quadratic improvement in sparsity.
We develop a quantum algorithm for slow analytic Hamiltonians H~(t)=H(t/T)\widetilde H(t)=H(t/T)H(t)=H(t/T) with ∥H(s)∥≤α\|H(s)\|\leqα∥H(s)∥≤α that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of H(s)H(s)H(s), together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity O~ ⁣(αT+log⁡(1/ε))\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)O(αT+log(1/ε)) and additional gate complexity O~ ⁣((αT+log⁡(1/ε))2log⁡(1/ε))\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)O((αT+log(1/ε))2log(1/ε)), assuming coherent access to H′(s)H'(s)H′(s) and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations.
We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product tau of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sub linear dependence on tau.
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.