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 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 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 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 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 the problem of approximating the time-evolution operator e−iH^t to error ϵ , where the Hamiltonian H^=(⟨G|⊗I^)U^(|G⟩⊗I^) is the projection of a unitary oracle U^ onto the state |G⟩ created by another unitary oracle. Our algorithm solves this with a query complexity O(t+log(1/ϵ)) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H^ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any H^ in an invariant SU(2) subspace. A large class of operator functions of H^ can then be computed with optimal query complexity, of which e−iH^t is a special case.
We provide a quantum method for simulating Hamiltonian evolution with complexity polynomial in the logarithm of the inverse error. This is an exponential improvement over existing methods for Hamiltonian simulation. In addition, its scaling with respect to time is close to linear, and its scaling with respect to the time derivative of the Hamiltonian is logarithmic. These scalings improve upon most existing methods. Our method is to use a compressed Lie-Trotter formula, based on recent ideas for efficient discrete-time simulations of continuous-time quantum query algorithms.
We give a query-optimal algorithm for simulating a general n-qubit time-dependent Hamiltonian H(t) on [0,T], assuming that H is Lipschitz continuous and ∥H(t)∥≤α. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator UH(T) to error ε using O(αT+log(e+log(1/ε)/(αT))log(1/ε)) $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead.
Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to UH(T) and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.