We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H}\,\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.
We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H},\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, N is the dimension of the system, and ϵ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.
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 study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence polyloglog(1/ϵ) on the simulation precision ϵ . This presents an exponential improvement over the dependence polylog(1/ϵ) of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs' quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound Ω(loglog(1/ϵ)) is established, showing that the ϵ -dependence of the gate depth achieved in this work cannot be significantly improved.Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a polyloglog(1/ϵ) dependence in the parallel setting.
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.
Scalable Program Implementation and Simulation of the Large-Scale Quantum Algorithm: 1024×1024 Quantum Linear Solver and Beyond
Program implementation and simulation are essential for research in the field of quantum algorithms. However, complex and large-scale quantum algorithms can pose challenges for existing quantum programming languages and simulators. Here, we present a scalable program implementation of the quantum walk on a sparse matrix and the quantum linear solver based on the quantum walk. Our implementation is based on a practical scenario in which the sparse matrix is stored in the compressed-sparse-column format in quantum random access memory. All necessary modules are implemented unitarily and are ensured to be decomposed at the quantum gate level, including implementing a quantum binary search and a modification of the original algorithm. The program is validated using a highly efficient quantum circuit simulator which is based on the register level and sparse state representation. With only a single core, we simulate the quantum walk on a 16384-dimensional matrix with 582 qubits in 1.1 minutes per step, as well as a quantum linear solver up to 1024 dimensions and 212245 steps in 70 hours. Our work narrows the gap between the simulation of a quantum algorithm and its classical counterparts, where the asymptotic complexity of our quantum linear solver simulation approximates a classical linear solver. These program implementation and simulation techniques have the potential to expand the boundary of numerical research for large-scale quantum algorithms, with implications for the development of error-correction-era quantum computing solutions.
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.
Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms.
We develop an algorithm for general kernels assuming that M<1, where M characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when M≥1, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when M≥1 by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.