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].
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→2. For tΛ≥1/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Λ≥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(κdpolylog(κ/ε)) queries for solving d-sparse quantum linear systems with ∥A∥≤1 and ∥A−1∥≤κ, 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(dlog(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N) queries for arbitrary N×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].
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 O(sτ+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 sτ and log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log(Cgˉ/ε)) queries, where τ is the evolution time multiplied by a norm bound, 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 O(κslog(1/ε)) queries when ∥A∥≤1 and ∥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.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UA and the right-hand side through a state-preparation oracle Ub. The optimal query complexities of these two oracles are known separately: O(κlog(1/ε)) queries to UA and O(κ/s) queries to Ub, where 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 s, we give a quantum linear-system algorithm that prepares the normalized solution to error ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UA and O(κ/s) queries to Ub. 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/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
T-efficient unitary synthesis via block-sparse Hamiltonian simulation
We construct Clifford+T circuits implementing arbitrary n-qubit unitaries with worst-case T-count O(N8/7) at constant operator-norm error, where N=2n, improving the previous exponent 5/4. The construction uses O(N6/7) clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error ε∈(0,1/2), let L=log2(N/ε), the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using O(N8/7L3/7+NL)T gates and O(N) clean ancillas whenever L≤N. We also prove that, at constant precision, the exponent 8/7 is optimal within a sequential block-SELECT model.
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 ε. The dependence on κ and ε is already well understood through the lower bound Ω(κlog(1/ε)), 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 Ω(κslog(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) for constant error ε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian H and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗Lk, with normalization factors αH and αB, respectively. For evolution time t, set τ=(αH+αB2)t. The algorithm approximates the evolution channel to diamond-norm error ε using O(τ+log(e+log(1/ε)/τ)log(1/ε)) oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.