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:2606.23544

Structure-Aware Variance Reduction for Unbiased Randomized Hamiltonian Simulation

Joshua W. Dai, Fredrik Hasselgren, Chusei Kiumi

quant-phSubmitted Jun 22, 2026• Announced Jun 23, 2026• 0 citations• Revised Sep 17, 2026 (v2)
v1 · Jun 22, 2026v2 · Sep 17, 2026
arXivHTMLPDF

Abstract

Randomized Hamiltonian simulation methods are often governed by a trade-off between systematic bias and sampling overhead. We study how classical variance-reduction techniques can be applied to such methods without changing their mean channel, and therefore without introducing additional bias. As a motivating unbiased estimator, we formulate continuous time-evolution probabilistic angle interpolation (continuous TE-PAI), a quasiprobabilistic random-circuit protocol whose remaining Monte Carlo error is purely statistical. Continuous TE-PAI removes Trotter discretization error with finite-depth random circuits, whereas deterministic Trotterization does so only in the infinite-depth limit. Further, in tensor-network simulations, we demonstrate that discretization error can cause an unphysical exponential growth in the bond dimension required for Trotterized simulations, whereas comparable-depth continuous TE-PAI circuits avoid this growth. We then show that the variance of randomized product-formula-based estimators admits a canonical decomposition into a classical counting component and a quantum ordering component such that the dominant simulation overhead results from the non-commutative parts of the Hamiltonian dynamics. Motivated by this decomposition, we achieve an $\approx70\%$ error-reduction using the counting-component for small systems whereas our tensor-network simulations of $n=30$ spin-chain dynamics use coarser statistics tailored to the observable and estimator attaining a negligible bias and a reduction of $\approx 80\%$ leading to $\approx91\%$ and $\approx96\%$ sampling-cost reductions, respectively.

Comments
31 pages, 6 pages

Related papers

Quantum-inspired classical simulation through randomized time evolution

Fredrik Hasselgren, Bálint Koczor

Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to $10^3$ relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.

quant-pharXiv:2604.13144•Apr 15, 2026•0 citations

Unbiased Hamiltonian Simulation by Reversing Trotter Error Dynamics

Keisuke Murota, Yuta Kikuchi, Enrico Rinaldi +2 more

Owing to their simplicity and low overhead, Suzuki-Trotter formulas remain the de facto Hamiltonian simulation methods on current quantum computing platforms. Systematic Trotter errors, however, will quickly become limiting when scaling to larger problems and aiming for higher accuracy. We present a mechanism that removes the systematic error of any $k$-th order Suzuki-Trotter simulation, at the cost of a constant sampling overhead. The key insight is that the Trotter error is itself a coherent dynamics to be reversed, rather than a deviation to be bounded. By identifying the structure of this error in closed form, we carry out that reversal through quasi-probabilistic decompositions. The resulting algorithm, called Probabilistic Trotter Error Reversal (PTER), is unbiased and still improves the gate-count scaling of Suzuki-Trotter formulas while retaining their simplicity. Numerical simulations of a Heisenberg spin chain support the predicted resource advantage already at modest system sizes.

quant-pharXiv:2606.29741•Jun 30, 2026•0 citations

MLMC-qDRIFT: Multilevel Variance Reduction for Randomized Quantum Hamiltonian Simulation

Pegah Mohammadipour, Xiantao Li

Simulating quantum dynamics is one of the central applications of quantum computing. For Hamiltonians written as a sum of many terms, deterministic Trotter--Suzuki product formulas can require applying a large number of term-wise evolutions at each time step, leading to high circuit costs for large or dense systems. Randomized methods such as qDRIFT offer an alternative: each step samples only one Hamiltonian term, giving a circuit depth with no explicit dependence on the number of terms. However, when qDRIFT is used for observable estimation, high precision requires many independent random circuit realizations, resulting in a total gate complexity that scales as $\mathcal{O}(\varepsilon^{-3})$. We introduce a multilevel Monte Carlo framework for qDRIFT that reduces this sampling overhead. The method constructs a hierarchy of qDRIFT estimators with increasing circuit depths and couples adjacent levels by sharing their random Hamiltonian-term samples. This coupling makes the variance of the level differences decay with depth, allowing most samples to be taken on cheaper, coarse circuits and only a few on expensive, fine circuits. We prove that the resulting MLMC-qDRIFT estimator reduces the total gate complexity for fixed-precision observable estimation from the standard qDRIFT scaling $\mathcal{O}(\varepsilon^{-3})$ to $\mathcal{O}(\varepsilon^{-2}\log^2(1/\varepsilon))$, while preserving qDRIFT's lack of explicit dependence on the number of Hamiltonian terms. Numerical experiments for spin-chain dynamics confirm the predicted variance decay and demonstrate the practical gate-count savings of the multilevel construction.

quant-pharXiv:2604.26865•Apr 30, 2026•0 citations

Problem-aware sampling for bias and variance reduction in randomised Hamiltonian simulation

Brian Coyle, Jonathan H. Fetherolf, Antonio Márquez Romero +3 more

Randomised quantum simulation algorithms such as qDRIFT reduce circuit depth by replacing deterministic product formulas with stochastic compilations, but achieving high accuracy can require many steps. In vanilla qDRIFT, Hamiltonian terms are sampled with probabilities proportional to their coefficient magnitudes. We propose StateDRIFT, a variant of qDRIFT which optimises its sampling distribution to estimate time-evolved quantities using knowledge of the initial state and target observable, with a provable truncation bound that keeps qDRIFT's guarantees. The distribution at each depth is chosen by solving an optimisation problem targeting bias and/or variance. StateDRIFT can significantly reduce the bias and variance of estimators, and hence circuit depth, which we test on short-time dynamics of lattice models and molecules under Jordan-Wigner up to 18 qubits. For example, with BeH2 StateDRIFT can reduce the number of two-qubit gates required to achieve a given accuracy from 11,201 to 983. StateDRIFT involves measuring observables and commutators on the initial state, so we propose two practical ways to estimate these: classical surrogates such as tensor networks, and classical shadows, which recover most or all of the saving from exact oracles in the systems tested.

quant-pharXiv:2610.31515•Oct 23, 2026•0 citations

Resource-Optimal Importance Sampling for Randomized Quantum Algorithms

Davide Cugini, Touheed Anwar Atif, Yigit Subasi

Randomized protocols are procedures that incorporate probabilistic choices during their execution and they play a central role in quantum algorithms, spanning Hamiltonian simulation, noise mitigation, and measurement tasks. In practical implementations, the dominant cost of such protocols typically arises from circuit execution and measurement, and depends on hardware-specific resources such as gate counts, circuit depth, runtime, or dissipated energy. We introduce a general framework for applying classical importance sampling to randomized quantum protocols. Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit that jointly captures the computational expense per circuit and the estimator variance. We further extend the framework to scenarios where the quantum computation is subject to errors arising either from algorithmic approximations or from physical noise, proving that importance sampling preserves estimator bias despite altering the sampling distribution, and to settings with error-detection schemes, where we characterize the resulting changes in the optimal sampling strategy and achievable net-cost reduction. Representative applications include the Qdrift protocol, dephasing channels, mixed-states simulation, composite observables estimation, classical shadows, and probabilistic error cancellation. Overall, our results establish a principled approach for reducing the computational resources required by randomized quantum protocols through classical sampling optimization.

quant-pharXiv:2603.13495•Mar 17, 2026•0 citations

Stratified Sampling for Quasi-Probability Decompositions

Joshua W. Dai, Bálint Koczor

Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols -- one replaces a ``difficult'' quantum circuit with an ensemble of ``easier'' circuit variants whose weighted outcomes reproduce any target observable. This, however, inevitably yields an increased configuration variance beyond Born-rule shot noise. We develop a broad framework for accounting for and reducing this variance and prove that stratified sampling -- under ideal proportional allocation -- results in an unbiased estimator with a variance that is never worse than naïve sampling (with equality only in degenerate cases). Furthermore, we provide a classical dynamic programme to enable stratification on arbitrary product-form QPDs. Numerical simulations of typical QPDs, such as Probabilistic Error Cancellation (PEC) and Probabilistic Angle Interpolation (PAI), demonstrate constant-factor reductions in overall variance (up to $\sim 60$--$80\%$ in an oracle model) and robust $\sim 10\%$ savings in the pessimistic single-shot regime. Our results can be applied immediately to reduce the net sampling cost of practically relevant QPDs that are commonly used in near term and early fault-tolerant algorithms without requiring additional quantum resources.

quant-pharXiv:2602.11245•Feb 12, 2026•0 citations
Randomized Hamiltonian simulation methods are often governed by a trade-off between systematic bias and sampling overhead. We study how classical variance-reduction techniques can be applied to such methods without changing their mean channel, and therefore without introducing additional bias. As a motivating unbiased estimator, we formulate continuous time-evolution probabilistic angle interpolation (continuous TE-PAI), a quasiprobabilistic random-circuit protocol whose remaining Monte Carlo error is purely statistical. Continuous TE-PAI removes Trotter discretization error with finite-depth random circuits, whereas deterministic Trotterization does so only in the infinite-depth limit. Further, in tensor-network simulations, we demonstrate that discretization error can cause an unphysical exponential growth in the bond dimension required for Trotterized simulations, whereas comparable-depth continuous TE-PAI circuits avoid this growth. We then show that the variance of randomized product-formula-based estimators admits a canonical decomposition into a classical counting component and a quantum ordering component such that the dominant simulation overhead results from the non-commutative parts of the Hamiltonian dynamics. Motivated by this decomposition, we achieve an ≈70%\approx70\%≈70% error-reduction using the counting-component for small systems whereas our tensor-network simulations of n=30n=30n=30 spin-chain dynamics use coarser statistics tailored to the observable and estimator attaining a negligible bias and a reduction of ≈80%\approx 80\%≈80% leading to ≈91%\approx91\%≈91% and ≈96%\approx96\%≈96% sampling-cost reductions, respectively.
Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to 10310^3103 relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.
Owing to their simplicity and low overhead, Suzuki-Trotter formulas remain the de facto Hamiltonian simulation methods on current quantum computing platforms. Systematic Trotter errors, however, will quickly become limiting when scaling to larger problems and aiming for higher accuracy. We present a mechanism that removes the systematic error of any kkk-th order Suzuki-Trotter simulation, at the cost of a constant sampling overhead. The key insight is that the Trotter error is itself a coherent dynamics to be reversed, rather than a deviation to be bounded. By identifying the structure of this error in closed form, we carry out that reversal through quasi-probabilistic decompositions. The resulting algorithm, called Probabilistic Trotter Error Reversal (PTER), is unbiased and still improves the gate-count scaling of Suzuki-Trotter formulas while retaining their simplicity. Numerical simulations of a Heisenberg spin chain support the predicted resource advantage already at modest system sizes.
Simulating quantum dynamics is one of the central applications of quantum computing. For Hamiltonians written as a sum of many terms, deterministic Trotter--Suzuki product formulas can require applying a large number of term-wise evolutions at each time step, leading to high circuit costs for large or dense systems. Randomized methods such as qDRIFT offer an alternative: each step samples only one Hamiltonian term, giving a circuit depth with no explicit dependence on the number of terms. However, when qDRIFT is used for observable estimation, high precision requires many independent random circuit realizations, resulting in a total gate complexity that scales as O(ε−3)\mathcal{O}(\varepsilon^{-3})O(ε−3). We introduce a multilevel Monte Carlo framework for qDRIFT that reduces this sampling overhead. The method constructs a hierarchy of qDRIFT estimators with increasing circuit depths and couples adjacent levels by sharing their random Hamiltonian-term samples. This coupling makes the variance of the level differences decay with depth, allowing most samples to be taken on cheaper, coarse circuits and only a few on expensive, fine circuits. We prove that the resulting MLMC-qDRIFT estimator reduces the total gate complexity for fixed-precision observable estimation from the standard qDRIFT scaling O(ε−3)\mathcal{O}(\varepsilon^{-3})O(ε−3) to O(ε−2log⁡2(1/ε))\mathcal{O}(\varepsilon^{-2}\log^2(1/\varepsilon))O(ε−2log2(1/ε)), while preserving qDRIFT's lack of explicit dependence on the number of Hamiltonian terms. Numerical experiments for spin-chain dynamics confirm the predicted variance decay and demonstrate the practical gate-count savings of the multilevel construction.
Randomised quantum simulation algorithms such as qDRIFT reduce circuit depth by replacing deterministic product formulas with stochastic compilations, but achieving high accuracy can require many steps. In vanilla qDRIFT, Hamiltonian terms are sampled with probabilities proportional to their coefficient magnitudes. We propose StateDRIFT, a variant of qDRIFT which optimises its sampling distribution to estimate time-evolved quantities using knowledge of the initial state and target observable, with a provable truncation bound that keeps qDRIFT's guarantees. The distribution at each depth is chosen by solving an optimisation problem targeting bias and/or variance. StateDRIFT can significantly reduce the bias and variance of estimators, and hence circuit depth, which we test on short-time dynamics of lattice models and molecules under Jordan-Wigner up to 18 qubits. For example, with BeH2 StateDRIFT can reduce the number of two-qubit gates required to achieve a given accuracy from 11,201 to 983. StateDRIFT involves measuring observables and commutators on the initial state, so we propose two practical ways to estimate these: classical surrogates such as tensor networks, and classical shadows, which recover most or all of the saving from exact oracles in the systems tested.
Randomized protocols are procedures that incorporate probabilistic choices during their execution and they play a central role in quantum algorithms, spanning Hamiltonian simulation, noise mitigation, and measurement tasks. In practical implementations, the dominant cost of such protocols typically arises from circuit execution and measurement, and depends on hardware-specific resources such as gate counts, circuit depth, runtime, or dissipated energy. We introduce a general framework for applying classical importance sampling to randomized quantum protocols. Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit that jointly captures the computational expense per circuit and the estimator variance. We further extend the framework to scenarios where the quantum computation is subject to errors arising either from algorithmic approximations or from physical noise, proving that importance sampling preserves estimator bias despite altering the sampling distribution, and to settings with error-detection schemes, where we characterize the resulting changes in the optimal sampling strategy and achievable net-cost reduction. Representative applications include the Qdrift protocol, dephasing channels, mixed-states simulation, composite observables estimation, classical shadows, and probabilistic error cancellation. Overall, our results establish a principled approach for reducing the computational resources required by randomized quantum protocols through classical sampling optimization.
Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols -- one replaces a ``difficult'' quantum circuit with an ensemble of ``easier'' circuit variants whose weighted outcomes reproduce any target observable. This, however, inevitably yields an increased configuration variance beyond Born-rule shot noise. We develop a broad framework for accounting for and reducing this variance and prove that stratified sampling -- under ideal proportional allocation -- results in an unbiased estimator with a variance that is never worse than naïve sampling (with equality only in degenerate cases). Furthermore, we provide a classical dynamic programme to enable stratification on arbitrary product-form QPDs. Numerical simulations of typical QPDs, such as Probabilistic Error Cancellation (PEC) and Probabilistic Angle Interpolation (PAI), demonstrate constant-factor reductions in overall variance (up to ∼60\sim 60∼60--80%80\%80% in an oracle model) and robust ∼10%\sim 10\%∼10% savings in the pessimistic single-shot regime. Our results can be applied immediately to reduce the net sampling cost of practically relevant QPDs that are commonly used in near term and early fault-tolerant algorithms without requiring additional quantum resources.