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 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 provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
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.
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d -sparse Hamiltonian H acting on n qubits can be simulated for time t with precision $\unicode[STIX]{x1D716}$ using $O(\unicode[STIX]{x1D70F}(\log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})))$ queries and $O(\unicode[STIX]{x1D70F}(\log ^{2}(\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716}))n)$ additional 2-qubit gates, where $\unicode[STIX]{x1D70F}=d^{2}\Vert H\Vert _{\max }t$ . Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault-correction procedure. Our simplification relies on a new form of ‘oblivious amplitude amplification’ that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
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(tΛd+dlog(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>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 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.
The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the L 1 norm ∫ 0 t d τ ‖ H ( τ ) ‖ max , whereas the best previous results scale with t max τ ∈ [ 0 , t ] ‖ H ( τ ) ‖ max . We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry.