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:2308.03694 · npj Quantum Information

Hamiltonian dynamics on digital quantum computers without discretization error

Etienne Granet, Henrik Dreyer

Published Sep 7, 2024• 15 citations
arXivHTMLPDF

Abstract

We introduce an algorithm to compute expectation values of time-evolved observables on digital quantum computers that requires only bounded average circuit depth to reach arbitrary precision, i.e. produces an unbiased estimator with finite average depth. This finite depth comes with an attenuation of the measured expectation value by a known amplitude, requiring more shots per circuit. The average gate count per circuit for simulation time t is $${\mathcal{O}}({t}^{2}{\mu }^{2})$$ with μ the sum of the Hamiltonian coefficients, without dependence on precision, providing a significant improvement over previous algorithms. With shot noise, the average runtime is $${\mathcal{O}}({t}^{2}{\mu }^{2}{\epsilon }^{-2})$$ to reach precision ϵ. The only dependence in the sum of the coefficients makes it particularly adapted to non-sparse Hamiltonians. The algorithm generalizes to time-dependent Hamiltonians, appearing for example in adiabatic state preparation. These properties make it particularly suitable for present-day relatively noisy hardware that supports only circuits with moderate depth.

DOI
10.1038/s41534-024-00877-y

Related papers

Simulating Quantum Circuits with Arbitrary Local Noise Using Pauli Propagation

Armando Angrisani, Antonio Anna Mele, Manuel S. Rudolph +2 more

We present a polynomial-time classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise, including non-unital or dephasing. Although previous research demonstrated that some carefully designed quantum circuits affected by non-unital noise cannot be efficiently simulated, we show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods. Specifically, we prove that, with high probability over the circuit gates’ choice, Pauli propagation algorithms with tailored truncation strategies achieve an inversely polynomially small simulation error. This result holds for arbitrary circuit topologies and for any local noise, under the assumption that the distribution of each circuit layer is invariant under single-qubit random gates. Under the same minimal assumptions, we also prove that most noisy circuits can be truncated to an effective logarithmic depth for the task of estimating expectation values of observables, thus generalizing prior results to a significantly broader class of circuit ensembles. We further numerically validate our algorithm with simulations on a 6 × 6 lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an 11 × 11 lattice of qubits affected by amplitude damping.

arXiv:2501.13101•PRX Quantum•Mar 17, 2026•8 citations

A quantum algorithm for simulating non-sparse Hamiltonians

Chunhao Wang, Leonard Wossnig

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.

arXiv:1803.08273•Quantum Information and Computation•Jun 1, 2020•21 citations

Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation

Zheyu Shen, Yusen Wu, Penghui Yao +2 more

Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

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

Measurements of Quantum Hamiltonians with Locally-Biased Classical Shadows

Charles F. Hadfield, Sergey B. Bravyi, Rudy Raymond +1 more

Abstract Obtaining precise estimates of quantum observables is a crucial step of variational quantum algorithms. We consider the problem of estimating expectation values of quantum Hamiltonians, obtained on states prepared on a quantum computer. We propose a novel estimator for this task, which is locally optimised with knowledge of the Hamiltonian and a classical approximation to the underlying quantum state. Our estimator is based on the concept of classical shadows of a quantum state, and has the important property of not adding to the circuit depth for the state preparation. We test its performance numerically for molecular Hamiltonians of increasing size, finding a sizable reduction in variance with respect to current measurement protocols that do not increase circuit depths.

arXiv:2006.15788•Communications in Mathematical Physics•Mar 30, 2022•129 citations

Randomly Compiled Quantum Simulation with Exponentially Reduced Circuit Depths

James D. Watson

The quantum stochastic drift protocol, also known as qDRIFT, has become a popular algorithm for implementing time-evolution of quantum systems using randomised compiling. In this work we develop qFLO, a higher order randomised algorithm for time-evolution. To estimate an observable expectation value at time $T$ to precision $ε$, we show it is sufficient to use circuit depths of $O(T^2\log(1/ε))$ -- an exponential improvement over standard qDRIFT requirements with respect to $ε$. The protocol achieves this using $O(1/ε^2)$ repeated runs of the standard qDRIFT protocol combined with classical post-processing in the form of Richardson extrapolation. Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices. Furthermore, it is well-conditioned and inherits many desirable properties of randomly compiled simulation methods, including circuit depths that do not explicitly depend on the number of terms in the Hamiltonian.

arXiv:2411.04240•Nov 6, 2024•1 citation

Less precise but less noisy: local circuits for momentum-space state preparation and measurement

Etienne Granet, Henrik Dreyer

Quantum algorithms are usually optimized for gate count or circuit depth. We find on Quantinuum System Model H2 quantum computer that for a tight-binding chain ground state preparation, there is a system size $N$ beyond which the adiabatic evolution reaches significantly lower energies than the Fermionic Fourier Transform (FFT), with the same number of gates, and with the same circuit depth. We attribute this high noise sensitivity of the FFT to its high precision, being able to distinguish momenta by $1/N$. This high resolution in momentum space requires long-range couplings in real space, which propagates errors faster. In contrast, although local and physical circuits such as the adiabatic evolution have a coarser momentum resolution, they also propagate errors more slowly. For physical applications, high momentum resolution is rarely required and is often worth trading for low noise sensitivity. We also introduce a momentum measurement scheme that although less precise than FFT, is less costly and less noisy. We show that it achieves better performance than FFT for spectral function measurement on Quantinuum System Model H2 quantum computer. Our work emphasizes the importance of reducing the noise sensitivity of quantum algorithms, beyond the number of gates or circuit depth.

quant-pharXiv:2610.01704•Oct 2, 2026•0 citations
We introduce an algorithm to compute expectation values of time-evolved observables on digital quantum computers that requires only bounded average circuit depth to reach arbitrary precision, i.e. produces an unbiased estimator with finite average depth. This finite depth comes with an attenuation of the measured expectation value by a known amplitude, requiring more shots per circuit. The average gate count per circuit for simulation time t is O(t2μ2){\mathcal{O}}({t}^{2}{\mu }^{2})O(t2μ2) with μ the sum of the Hamiltonian coefficients, without dependence on precision, providing a significant improvement over previous algorithms. With shot noise, the average runtime is O(t2μ2ϵ−2){\mathcal{O}}({t}^{2}{\mu }^{2}{\epsilon }^{-2})O(t2μ2ϵ−2) to reach precision ϵ. The only dependence in the sum of the coefficients makes it particularly adapted to non-sparse Hamiltonians. The algorithm generalizes to time-dependent Hamiltonians, appearing for example in adiabatic state preparation. These properties make it particularly suitable for present-day relatively noisy hardware that supports only circuits with moderate depth.
We present a polynomial-time classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise, including non-unital or dephasing. Although previous research demonstrated that some carefully designed quantum circuits affected by non-unital noise cannot be efficiently simulated, we show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods. Specifically, we prove that, with high probability over the circuit gates’ choice, Pauli propagation algorithms with tailored truncation strategies achieve an inversely polynomially small simulation error. This result holds for arbitrary circuit topologies and for any local noise, under the assumption that the distribution of each circuit layer is invariant under single-qubit random gates. Under the same minimal assumptions, we also prove that most noisy circuits can be truncated to an effective logarithmic depth for the task of estimating expectation values of observables, thus generalizing prior results to a significantly broader class of circuit ensembles. We further numerically validate our algorithm with simulations on a 6 × 6 lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an 11 × 11 lattice of qubits affected by amplitude damping.
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, NNN 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.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy εεε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an nnn-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1T\ge1T≥1, with circuit depth O(Tlog⁡(nT/ε))O(T\log(nT/ε))O(Tlog(nT/ε)) and gate count O(nTlog⁡(nT/ε))O(nT\log(nT/ε))O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time TTT in the stated regime and sufficiently small fixed error εεε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). This matches our O(log⁡n)O(\log n)O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
Abstract Obtaining precise estimates of quantum observables is a crucial step of variational quantum algorithms. We consider the problem of estimating expectation values of quantum Hamiltonians, obtained on states prepared on a quantum computer. We propose a novel estimator for this task, which is locally optimised with knowledge of the Hamiltonian and a classical approximation to the underlying quantum state. Our estimator is based on the concept of classical shadows of a quantum state, and has the important property of not adding to the circuit depth for the state preparation. We test its performance numerically for molecular Hamiltonians of increasing size, finding a sizable reduction in variance with respect to current measurement protocols that do not increase circuit depths.
The quantum stochastic drift protocol, also known as qDRIFT, has become a popular algorithm for implementing time-evolution of quantum systems using randomised compiling. In this work we develop qFLO, a higher order randomised algorithm for time-evolution. To estimate an observable expectation value at time TTT to precision εεε, we show it is sufficient to use circuit depths of O(T2log⁡(1/ε))O(T^2\log(1/ε))O(T2log(1/ε)) -- an exponential improvement over standard qDRIFT requirements with respect to εεε. The protocol achieves this using O(1/ε2)O(1/ε^2)O(1/ε2) repeated runs of the standard qDRIFT protocol combined with classical post-processing in the form of Richardson extrapolation. Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices. Furthermore, it is well-conditioned and inherits many desirable properties of randomly compiled simulation methods, including circuit depths that do not explicitly depend on the number of terms in the Hamiltonian.
Quantum algorithms are usually optimized for gate count or circuit depth. We find on Quantinuum System Model H2 quantum computer that for a tight-binding chain ground state preparation, there is a system size NNN beyond which the adiabatic evolution reaches significantly lower energies than the Fermionic Fourier Transform (FFT), with the same number of gates, and with the same circuit depth. We attribute this high noise sensitivity of the FFT to its high precision, being able to distinguish momenta by 1/N1/N1/N. This high resolution in momentum space requires long-range couplings in real space, which propagates errors faster. In contrast, although local and physical circuits such as the adiabatic evolution have a coarser momentum resolution, they also propagate errors more slowly. For physical applications, high momentum resolution is rarely required and is often worth trading for low noise sensitivity. We also introduce a momentum measurement scheme that although less precise than FFT, is less costly and less noisy. We show that it achieves better performance than FFT for spectral function measurement on Quantinuum System Model H2 quantum computer. Our work emphasizes the importance of reducing the noise sensitivity of quantum algorithms, beyond the number of gates or circuit depth.