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:2507.22341 · Physical Review A

Reducing circuit depth in Lindblad simulations via step-size extrapolation

Pegah Mohammadipour, Xiantao Li

Published Oct 29, 2025• 0 citations
arXivHTMLPDF

Abstract

We study algorithmic error mitigation via Richardson-style extrapolation for quantum simulations of open quantum systems modelled by the Lindblad equation. Focusing on two specific first-order quantum algorithms, we perform a backward-error analysis to obtain a step-size expansion of the density operator with explicit coefficient bounds. These bounds supply the necessary smoothness for analyzing Richardson extrapolation, allowing us to bound both the deterministic bias and the shot-noise variance that arise in postprocessing. For a Lindblad evolution with generator bounded by $\ensuremath{\ell}$, our main theorem shows that an $n=\mathrm{\ensuremath{\Omega}}({log}_{10}(1/\ensuremath{\varepsilon}))$-point extrapolator reduces the maximum circuit depth needed for accuracy $\ensuremath{\varepsilon}$ from polynomial $O({(\ensuremath{\ell}T)}^{2}/\ensuremath{\varepsilon})$ to polylogarithmic $O({(\ensuremath{\ell}T)}^{2}({log}_{10}(\ensuremath{\ell}T)){log}^{2}(1/\ensuremath{\varepsilon}))$ scaling, an exponential improvement in $1/\ensuremath{\varepsilon}$, while keeping sampling complexity to the standard $1/{\ensuremath{\varepsilon}}^{2}$ level, thus extending such results for Hamiltonian simulations to Lindblad simulations. Several numerical experiments illustrate the practical viability of the method.

DOI
10.1103/dzpc-m1p4

Related papers

Enhancing the Quantum Linear Systems Algorithm Using Richardson Extrapolation

Almudena Carrera Vazquez, Ralf Hiptmair, Stefan Woerner

We present a quantum algorithm to solve systems of linear equations of the form Ax = b , where A is a tridiagonal Toeplitz matrix and b results from discretizing an analytic function, with a circuit complexity of O (1/√ε, poly (log κ, log N )), where N denotes the number of equations, ε is the accuracy, and κ the condition number. The repeat-until-success algorithm has to be run O (κ/(1-ε)) times to succeed, leveraging amplitude amplification, and needs to be sampled O (1/ε 2 ) times. Thus, the algorithm achieves an exponential improvement with respect to N over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation, and a set of observables together with the corresponding error and complexity analyses. As the main result of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with 1/√ε circuits that can be run in parallel each with circuit complexity 1/√ ε instead of 1/ε. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although our theoretical results would need to be extended accordingly. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.

arXiv:2009.04484•ACM Transactions on Quantum Computing•Jan 14, 2022•46 citations

Joint Mitigation of Algorithmic and Physical Errors in Noisy Hamiltonian Simulation

Shuo Zhou, Xinzhao Wang, Ruiqi Zhang +4 more

Product-formula Hamiltonian simulation is naturally suited to near-term quantum processors, but its accuracy is set by two competing errors: finite-step Trotter bias and physical hardware noise. We introduce a joint extrapolation strategy that ties the tunable per-layer noise strength to the Trotter step size, $λ(s)=c(sT)^{p+1}$ for a $p$-th order product formula. Along this one-dimensional path, the leading physical-noise and Trotter corrections over the full evolution both enter at order $s^p$ and can be canceled by a single Richardson extrapolation. Building on a previously established finite-order Baker--Campbell--Hausdorff truncation bound, we derive a provably commutator-scaling resource guarantee for the joint extrapolation. For local Hamiltonians with local Lindbladian noise, the protocol mitigates physical noise together with Trotter error with only a constant asymptotic overhead relative to noiseless Trotter extrapolation, provided the required noise strengths lie above the intrinsic device-noise floor. We experimentally demonstrate the protocol for Ising dynamics on a superconducting quantum computer using learned noise amplification. Complementary 100-qubit Sparse Pauli Dynamics (SPD) simulations achieve comparable accuracy to two-dimensional Richardson extrapolation with fewer circuit settings.

quant-pharXiv:2609.11508•Sep 11, 2026•0 citations

Exponentially Reduced Circuit Depths Using Trotter Error Mitigation

James D. Watson, Jacob Watkins

Product formulas are a popular class of digital quantum simulation algorithms due to their conceptual simplicity, low overhead, and performance, which often exceeds theoretical expectations. Recently, Richardson extrapolation and polynomial interpolation have been proposed to mitigate the Trotter error incurred by the use of these formulas. This work provides a rigorous, general analysis of these techniques for computing time-evolved observables, simplifying the interpolation algorithm in the process, and shows that extrapolation generically improves the performance of product formulas for this task. We demonstrate that, to achieve error ϵ in a simulation of time T using a p th -order product formula with extrapolation, circuit depths of O ( T 1 + 1 / p polylog  ( 1 / ϵ ) ) are sufficient—an exponential improvement in the precision over product formulas alone. Furthermore, we prove that these algorithms achieve commutator scaling, and improve the T complexity for the interpolation algorithm. By relaxing the requirement of performing exact Chebyshev interpolation, our simplified algorithm eliminates the need for fractional implementations of Trotter steps, reducing computational overhead. Finally, we show these techniques can be combined with the classical shadows method to estimate many time-evolved local observables. Taken together, our findings provide the strongest evidence yet for the utility of Trotter error-mitigation techniques in algorithmic applications.

arXiv:2408.14385•PRX Quantum•Jul 2, 2025•12 citations

Circuit Depth Reduction of One-Ancilla Quantum Differential Equation Solver via Extrapolation

Di Fang, Justin Park

Solving linear differential equations is a fundamental task in scientific computing and an important primitive for quantum computing. A recent one-ancilla quantum differential equation solver provides a hardware-friendly and locality-preserving approach with provable performance guarantees, making it highly suitable for the early fault-tolerant and near-term regimes. Its simple circuit structure comes with a natural trade-off: the maximum single-run circuit depth scales as $O (1/ε)$ in the target accuracy $ε$. In this work, we reduce this depth by combining the solver with classical step-size postprocessing. By running the one-ancilla solver at a logarithmic number of finite time step sizes and using classical post-processing to cancel leading discretization errors, we reduce the maximum single-run circuit depth to $O(\mathrm{polylog}(1/ε))$ without adding quantum ancillae or sacrificing locality. Technically, extending extrapolation ideas beyond Hamiltonian and Lindbladian dynamics requires regularity estimates for observable maps under nonunitary evolution, which we obtain through a holomorphic extension of the adjoint evolution. Numerical experiments on the Hatano-Nelson model (ODE) and the convection-diffusion equation (PDE) demonstrate the effectiveness of the approach.

quant-pharXiv:2607.07389•Jul 9, 2026•0 citations

Direct Analysis of Zero-Noise Extrapolation: Polynomial Methods, Error Bounds, and Simultaneous Physical-Algorithmic Error Mitigation

Pegah Mohammadipour, Xiantao Li

Zero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, efficient implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, presenting bias and variance bounds that quantify approximation errors. Additionally, for any precision ε , our results offer an estimate of the necessary sample complexity. We further extend the analysis to polynomial least squares-based extrapolation, which mitigates measurement noise and avoids overfitting. Finally, we propose a strategy for simultaneously mitigating circuit and algorithmic errors in the Trotter-Suzuki algorithm by jointly scaling the time step size and the noise level. This strategy provides a practical tool to enhance the reliability of near-term quantum computations. We support our theoretical findings with numerical experiments.

arXiv:2502.20673•Quantum•Nov 14, 2025•4 citations

Classically Augmented Zero-Noise Extrapolation

Timon Scheiber

We investigate a hybrid quantum-classical approach to quantum error mitigation. We propose Classically Augmented Zero-Noise Extrapolation, a hybrid error-mitigation method in which high-noise Richardson extrapolation nodes are replaced by classically simulated estimates. These classical nodes have negligible sampling variance but introduce deterministic simulation bias. We derive the resulting variance reduction under optimal shot allocation and show that, for linear node spacings and fixed index cutoff, the coefficient-level reduction can be exponential. We validate the prediction numerically using Pauli-propagation simulations and demonstrate a reduction in mean-squared error when the truncation bias is sufficiently small.

quant-pharXiv:2607.25746•Jul 29, 2026•0 citations
We study algorithmic error mitigation via Richardson-style extrapolation for quantum simulations of open quantum systems modelled by the Lindblad equation. Focusing on two specific first-order quantum algorithms, we perform a backward-error analysis to obtain a step-size expansion of the density operator with explicit coefficient bounds. These bounds supply the necessary smoothness for analyzing Richardson extrapolation, allowing us to bound both the deterministic bias and the shot-noise variance that arise in postprocessing. For a Lindblad evolution with generator bounded by \ensuremathℓ\ensuremath{\ell}\ensuremathℓ, our main theorem shows that an n=\ensuremathΩ(log10(1/\ensuremathε))n=\mathrm{\ensuremath{\Omega}}({log}_{10}(1/\ensuremath{\varepsilon}))n=\ensuremathΩ(log10​(1/\ensuremathε))-point extrapolator reduces the maximum circuit depth needed for accuracy \ensuremathε\ensuremath{\varepsilon}\ensuremathε from polynomial O((\ensuremathℓT)2/\ensuremathε)O({(\ensuremath{\ell}T)}^{2}/\ensuremath{\varepsilon})O((\ensuremathℓT)2/\ensuremathε) to polylogarithmic O((\ensuremathℓT)2(log10(\ensuremathℓT))log2(1/\ensuremathε))O({(\ensuremath{\ell}T)}^{2}({log}_{10}(\ensuremath{\ell}T)){log}^{2}(1/\ensuremath{\varepsilon}))O((\ensuremathℓT)2(log10​(\ensuremathℓT))log2(1/\ensuremathε)) scaling, an exponential improvement in 1/\ensuremathε1/\ensuremath{\varepsilon}1/\ensuremathε, while keeping sampling complexity to the standard 1/\ensuremathε21/{\ensuremath{\varepsilon}}^{2}1/\ensuremathε2 level, thus extending such results for Hamiltonian simulations to Lindblad simulations. Several numerical experiments illustrate the practical viability of the method.
We present a quantum algorithm to solve systems of linear equations of the form Ax = b , where A is a tridiagonal Toeplitz matrix and b results from discretizing an analytic function, with a circuit complexity of O (1/√ε, poly (log κ, log N )), where N denotes the number of equations, ε is the accuracy, and κ the condition number. The repeat-until-success algorithm has to be run O (κ/(1-ε)) times to succeed, leveraging amplitude amplification, and needs to be sampled O (1/ε 2 ) times. Thus, the algorithm achieves an exponential improvement with respect to N over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation, and a set of observables together with the corresponding error and complexity analyses. As the main result of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with 1/√ε circuits that can be run in parallel each with circuit complexity 1/√ ε instead of 1/ε. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although our theoretical results would need to be extended accordingly. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.
Product-formula Hamiltonian simulation is naturally suited to near-term quantum processors, but its accuracy is set by two competing errors: finite-step Trotter bias and physical hardware noise. We introduce a joint extrapolation strategy that ties the tunable per-layer noise strength to the Trotter step size, λ(s)=c(sT)p+1λ(s)=c(sT)^{p+1}λ(s)=c(sT)p+1 for a ppp-th order product formula. Along this one-dimensional path, the leading physical-noise and Trotter corrections over the full evolution both enter at order sps^psp and can be canceled by a single Richardson extrapolation. Building on a previously established finite-order Baker--Campbell--Hausdorff truncation bound, we derive a provably commutator-scaling resource guarantee for the joint extrapolation. For local Hamiltonians with local Lindbladian noise, the protocol mitigates physical noise together with Trotter error with only a constant asymptotic overhead relative to noiseless Trotter extrapolation, provided the required noise strengths lie above the intrinsic device-noise floor. We experimentally demonstrate the protocol for Ising dynamics on a superconducting quantum computer using learned noise amplification. Complementary 100-qubit Sparse Pauli Dynamics (SPD) simulations achieve comparable accuracy to two-dimensional Richardson extrapolation with fewer circuit settings.
Product formulas are a popular class of digital quantum simulation algorithms due to their conceptual simplicity, low overhead, and performance, which often exceeds theoretical expectations. Recently, Richardson extrapolation and polynomial interpolation have been proposed to mitigate the Trotter error incurred by the use of these formulas. This work provides a rigorous, general analysis of these techniques for computing time-evolved observables, simplifying the interpolation algorithm in the process, and shows that extrapolation generically improves the performance of product formulas for this task. We demonstrate that, to achieve error ϵ in a simulation of time T using a p th -order product formula with extrapolation, circuit depths of O ( T 1 + 1 / p polylog  ( 1 / ϵ ) ) are sufficient—an exponential improvement in the precision over product formulas alone. Furthermore, we prove that these algorithms achieve commutator scaling, and improve the T complexity for the interpolation algorithm. By relaxing the requirement of performing exact Chebyshev interpolation, our simplified algorithm eliminates the need for fractional implementations of Trotter steps, reducing computational overhead. Finally, we show these techniques can be combined with the classical shadows method to estimate many time-evolved local observables. Taken together, our findings provide the strongest evidence yet for the utility of Trotter error-mitigation techniques in algorithmic applications.
Solving linear differential equations is a fundamental task in scientific computing and an important primitive for quantum computing. A recent one-ancilla quantum differential equation solver provides a hardware-friendly and locality-preserving approach with provable performance guarantees, making it highly suitable for the early fault-tolerant and near-term regimes. Its simple circuit structure comes with a natural trade-off: the maximum single-run circuit depth scales as O(1/ε)O (1/ε)O(1/ε) in the target accuracy εεε. In this work, we reduce this depth by combining the solver with classical step-size postprocessing. By running the one-ancilla solver at a logarithmic number of finite time step sizes and using classical post-processing to cancel leading discretization errors, we reduce the maximum single-run circuit depth to O(polylog(1/ε))O(\mathrm{polylog}(1/ε))O(polylog(1/ε)) without adding quantum ancillae or sacrificing locality. Technically, extending extrapolation ideas beyond Hamiltonian and Lindbladian dynamics requires regularity estimates for observable maps under nonunitary evolution, which we obtain through a holomorphic extension of the adjoint evolution. Numerical experiments on the Hatano-Nelson model (ODE) and the convection-diffusion equation (PDE) demonstrate the effectiveness of the approach.
Zero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, efficient implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, presenting bias and variance bounds that quantify approximation errors. Additionally, for any precision ε , our results offer an estimate of the necessary sample complexity. We further extend the analysis to polynomial least squares-based extrapolation, which mitigates measurement noise and avoids overfitting. Finally, we propose a strategy for simultaneously mitigating circuit and algorithmic errors in the Trotter-Suzuki algorithm by jointly scaling the time step size and the noise level. This strategy provides a practical tool to enhance the reliability of near-term quantum computations. We support our theoretical findings with numerical experiments.
We investigate a hybrid quantum-classical approach to quantum error mitigation. We propose Classically Augmented Zero-Noise Extrapolation, a hybrid error-mitigation method in which high-noise Richardson extrapolation nodes are replaced by classically simulated estimates. These classical nodes have negligible sampling variance but introduce deterministic simulation bias. We derive the resulting variance reduction under optimal shot allocation and show that, for linear node spacings and fixed index cutoff, the coefficient-level reduction can be exponential. We validate the prediction numerically using Pauli-propagation simulations and demonstrate a reduction in mean-squared error when the truncation bias is sufficiently small.