pith. sign in

arxiv: 2604.26865 · v2 · pith:Q45ZBIXTnew · submitted 2026-04-29 · 🪐 quant-ph · cs.NA· math.NA

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

Pegah Mohammadipour , Xiantao Li This is my paper

Pith reviewed 2026-05-21 00:09 UTC · model grok-4.3

classification 🪐 quant-ph cs.NAmath.NA
keywords quantum simulationmultilevel Monte CarloqDRIFTvariance reductionHamiltonian dynamicsobservable estimationrandomized algorithms
0
0 comments X

The pith

Multilevel Monte Carlo qDRIFT reduces gate complexity for observable estimation from O(ε^{-3}) to O(ε^{-2} log²(1/ε)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a multilevel Monte Carlo version of the qDRIFT algorithm for quantum Hamiltonian simulation. It builds a hierarchy of estimators at increasing circuit depths and links neighboring levels by sharing the same random choices of which Hamiltonian term to evolve. This sharing causes the variance between level differences to decay rapidly with depth, so the algorithm can draw most of its samples from short, low-cost circuits and only a few from expensive long circuits. The construction preserves qDRIFT's independence from the number of terms in the Hamiltonian while improving the overall scaling for fixed-precision observable estimation.

Core claim

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}) to O(ε^{-2} log²(1/ε)), while preserving qDRIFT's lack of explicit dependence on the sum.

What carries the argument

The MLMC-qDRIFT hierarchy that couples adjacent levels by sharing random Hamiltonian-term samples, making the variance of their differences decay with increasing depth.

If this is right

  • Most sampling effort moves to short-depth circuits while the bias correction remains accurate.
  • The method stays efficient for Hamiltonians containing many individual terms.
  • Numerical tests on spin-chain dynamics confirm the predicted variance decay between levels.
  • Overall gate counts drop enough to make higher-precision observable estimates feasible.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same coupling idea could be tried on other randomized circuit-sampling schemes beyond qDRIFT.
  • Hardware runs might show extra savings because shallower circuits suffer less from noise.
  • The approach could be combined with existing error-mitigation techniques for near-term devices.

Load-bearing premise

The variance between the coupled estimators at neighboring depths decays fast enough as depth grows because the same random term samples are reused across levels.

What would settle it

Measure the total gate count required to reach a sequence of target precisions ε and check whether the observed scaling is closer to O(ε^{-2} log²(1/ε)) than to O(ε^{-3}).

Figures

Figures reproduced from arXiv: 2604.26865 by Pegah Mohammadipour, Xiantao Li.

Figure 1
Figure 1. Figure 1: Index-sharing coupling. The full index sequence of length view at source ↗
Figure 2
Figure 2. Figure 2: MLMC variance (left) and absolute mean (right) for the qDRIFT estimator on the 6-qubit view at source ↗
Figure 3
Figure 3. Figure 3: Mean conditional shot-noise variance of the augmented estimator, view at source ↗
Figure 4
Figure 4. Figure 4: Total gate complexity as a function of target RMSE view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript introduces MLMC-qDRIFT, a multilevel Monte Carlo framework applied to qDRIFT for observable estimation in quantum Hamiltonian simulation. Adjacent levels are coupled by reusing the same sequence of randomly sampled Hamiltonian terms, which induces variance decay in the level differences. The central claim is a rigorous proof that this construction reduces the total gate complexity for fixed-precision estimation from the standard qDRIFT scaling O(ε^{-3}) to O(ε^{-2} log²(1/ε)) while retaining the lack of explicit dependence on the number of Hamiltonian terms M. Numerical experiments on spin-chain dynamics are reported to confirm the predicted variance decay and practical gate-count savings.

Significance. If the variance-decay analysis holds, the result provides a concrete improvement in sampling efficiency for randomized quantum simulation methods, which is relevant for near-term observable estimation tasks. The explicit complexity bound and the preservation of M-independence are strengths; the numerical confirmation of variance decay on concrete models adds supporting evidence. The approach builds on established MLMC ideas but adapts them to the specific structure of qDRIFT estimators.

major comments (1)
  1. [§4.3, Theorem 4.1] §4.3, Theorem 4.1 and the subsequent complexity analysis: the proof that Var(estimator_l - estimator_{l-1}) decays sufficiently fast (at least as 2^{-αl} with α > 1 relative to the per-sample cost growth) relies on the coupling via shared random samples canceling leading O(Δt) discretization contributions. The provided bound on the difference operator does not explicitly quantify the residual variance from unsampled terms across levels; if this residual decays only polynomially in the level index, the optimal sample allocation would yield a total cost closer to O(ε^{-2.5}) or worse, undermining the headline O(ε^{-2} log²(1/ε)) claim.
minor comments (2)
  1. [Figure 2, §5.2] Figure 2 caption and §5.2: the plotted variance decay is shown for a single spin-chain instance; it would be helpful to include error bars or multiple random Hamiltonian realizations to illustrate robustness of the observed decay rate.
  2. [§3.1] Notation in §3.1: the definition of the coupled estimator pair (X_l, X_{l-1}) uses the same symbol for the shared random sequence at different levels; a brief remark clarifying that the sequence length is fixed by the finer level would avoid potential confusion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying a point in the variance analysis that merits clarification. We address the major comment below.

read point-by-point responses

  1. Referee: [§4.3, Theorem 4.1] §4.3, Theorem 4.1 and the subsequent complexity analysis: the proof that Var(estimator_l - estimator_{l-1}) decays sufficiently fast (at least as 2^{-αl} with α > 1 relative to the per-sample cost growth) relies on the coupling via shared random samples canceling leading O(Δt) discretization contributions. The provided bound on the difference operator does not explicitly quantify the residual variance from unsampled terms across levels; if this residual decays only polynomially in the level index, the optimal sample allocation would yield a total cost closer to O(ε^{-2.5}) or worse, undermining the headline O(ε^{-2} log²(1/ε)) claim.

    Authors: We appreciate the referee drawing attention to the need for an explicit treatment of the residual. In the proof of Theorem 4.1 the shared random sequence ensures exact cancellation of the leading O(Δt) bias terms between adjacent levels. The remaining contribution to the difference estimator arises from second-order discretization effects together with the variance induced by Hamiltonian terms that are not sampled in a given realization. Because both levels draw from the identical distribution, the cross terms involving unsampled operators are controlled by the same second-order remainder; after taking the expectation over the shared samples this yields the bound Var(estimator_l − estimator_{l−1}) ≤ C ⋅ 4^{−l}. With level cost scaling linearly in 2^l, the standard MLMC sample-allocation argument then recovers the stated O(ε^{−2} log²(1/ε)) gate complexity. We will add a short paragraph immediately after the statement of Theorem 4.1 that isolates this residual bound and confirms the decay rate α = 2. revision: partial

Circularity Check

0 steps flagged

No circularity: variance decay proved from coupling construction

full rationale

The MLMC-qDRIFT construction couples adjacent-level estimators by reusing the same sequence of sampled Hamiltonian terms. The claimed O(ε^{-2} log²(1/ε)) gate complexity follows from a variance bound on the coupled differences that is derived directly from the shared-sample definition and the underlying qDRIFT error analysis. No step reduces a prediction to a fitted parameter, self-citation, or definitional identity; the improvement is obtained by standard multilevel Monte Carlo sample allocation once the decay rate is established. The derivation is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard bounded-norm assumptions for Hamiltonian terms and on the existence of a variance-decay property induced by sample sharing; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The Hamiltonian is a sum of terms whose individual norms are bounded by known constants.
    Required to control the error and variance bounds in both qDRIFT and the multilevel extension.

pith-pipeline@v0.9.0 · 5812 in / 1202 out tokens · 49151 ms · 2026-05-21T00:09:33.534198+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Dutoi, Peter J

    Al´ an Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies.Science, 309:1704–1707, 2005

    work page 2005

  2. [2]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simu- lating Hamiltonian dynamics with a truncated Taylor series.Physical Review Letters, 114(9):090502, 2015. 18

    work page 2015

  3. [3]

    Time-dependent hamiltonian simulation withl1-norm scaling.Quantum, 4:254, 2020

    Dominic W Berry, Andrew M Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent hamiltonian simulation withl1-norm scaling.Quantum, 4:254, 2020

    work page 2020

  4. [4]

    Random compiler for fast hamiltonian simulation.Phys

    Earl Campbell. Random compiler for fast hamiltonian simulation.Phys. Rev. Lett., 123:070503, Aug 2019

    work page 2019

  5. [5]

    Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers.Quantum, 8:1496, October 2024

    Shantanav Chakraborty. Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers.Quantum, 8:1496, October 2024

    work page 2024

  6. [6]

    Concentration for random product formulas.PRX Quantum, 2(4):040305, 2021

    Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A Tropp. Concentration for random product formulas.PRX Quantum, 2(4):040305, 2021

    work page 2021

  7. [7]

    A randomized method for simulating lindblad equations and thermal state preparation.Quantum, 9:1917, 2025

    Hongrui Chen, Bowen Li, Jianfeng Lu, and Lexing Ying. A randomized method for simulating lindblad equations and thermal state preparation.Quantum, 9:1917, 2025

    work page 1917

  8. [8]

    Childs, Aaron Ostrander, and Yuan Su

    Andrew M. Childs, Aaron Ostrander, and Yuan Su. Faster quantum simulation by randomization. Quantum, 3:182, September 2019

    work page 2019

  9. [9]

    Childs, Yuan Su, Minh C

    Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling.Phys. Rev. X, 11:011020, Feb 2021

    work page 2021

  10. [10]

    Childs and Nathan Wiebe

    Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations.Quantum Info. Comput., 12(11–12):901–924, November 2012

    work page 2012

  11. [11]

    Tighter error bounds for the qdrift algorithm.arXiv preprint arXiv:2506.17199, 2025

    IJ David, I Sinayskiy, and F Petruccione. Tighter error bounds for the qdrift algorithm.arXiv preprint arXiv:2506.17199, 2025

    work page arXiv 2025

  12. [12]

    Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert

    Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert. Randomizing multi-product formulas for Hamiltonian simulation.Quantum, 6:806, September 2022

    work page 2022

  13. [13]

    Simulating physics with computers.International journal of theoretical physics, 21(6):467–488, 1982

    Richard P Feynman. Simulating physics with computers.International journal of theoretical physics, 21(6):467–488, 1982

    work page 1982

  14. [14]

    I. M. Georgescu, S. Ashhab, and Franco Nori. Quantum simulation.Rev. Mod. Phys., 86:153–185, Mar 2014

    work page 2014

  15. [15]

    Michael B. Giles. Multilevel monte carlo path simulation.Operations Research, 56(3):607–617, 2008

    work page 2008

  16. [16]

    Multilevel Monte Carlo methods.Acta numerica, 24:259–328, 2015

    Michael B Giles. Multilevel Monte Carlo methods.Acta numerica, 24:259–328, 2015

    work page 2015

  17. [17]

    Hamiltonian dynamics on digital quantum computers without discretization error.npj Quantum Information, 10(1):82, 2024

    Etienne Granet and Henrik Dreyer. Hamiltonian dynamics on digital quantum computers without discretization error.npj Quantum Information, 10(1):82, 2024

    work page 2024

  18. [18]

    Phase estimation with partially randomized time evolution, 2025

    Jakob G¨ unther, Freek Witteveen, Alexander Schmidhuber, Marek Miller, Matthias Christandl, and Aram Harrow. Phase estimation with partially randomized time evolution, 2025

    work page 2025

  19. [19]

    Composite quantum simulations.Quantum, 7:1181, 2023

    Matthew Hagan and Nathan Wiebe. Composite quantum simulations.Quantum, 7:1181, 2023

    work page 2023

  20. [20]

    Sornborger, and Yi˘ git Suba¸ sı

    David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, and Yi˘ git Suba¸ sı. Random- ized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs.PRX Quantum, 6(4):040373, 2025

    work page 2025

  21. [21]

    A partially random trotter algorithm for quantum hamiltonian simulations

    Shi Jin and Xiantao Li. A partially random trotter algorithm for quantum hamiltonian simulations. Communications on Applied Mathematics and Computation, 7(2):442–469, 2025

    work page 2025

  22. [22]

    Importance sampling for stochastic quantum simulations.Quantum, 7:977, 2023

    Oriel Kiss, Michele Grossi, and Alessandro Roggero. Importance sampling for stochastic quantum simulations.Quantum, 7:977, 2023

    work page 2023

  23. [23]

    Kivlichan, Christopher E

    Ian D. Kivlichan, Christopher E. Granade, and Nathan Wiebe. Phase estimation with randomized Hamiltonians, 2019

    work page 2019

  24. [24]

    Multilevel Richardson–Romberg extrapolation.Bernoulli, 23(4A):2643–2692, 2017

    Vincent Lemaire and Gilles Pag` es. Multilevel Richardson–Romberg extrapolation.Bernoulli, 23(4A):2643–2692, 2017

    work page 2017

  25. [25]

    From linear differential equations to unitaries: A moment-matching dilation framework with near-optimal quantum algorithms, 2025

    Xiantao Li. From linear differential equations to unitaries: A moment-matching dilation framework with near-optimal quantum algorithms, 2025. 19

    work page 2025

  26. [26]

    Probabilistic nonunitary gate in imaginary time evolution

    Tong Liu, Jin-Guo Liu, and Heng Fan. Probabilistic nonunitary gate in imaginary time evolution. Quantum Information Processing, 20(6):204, 2021

    work page 2021

  27. [27]

    Universal quantum simulators.Science, 273(5278):1073–1078, 1996

    Seth Lloyd. Universal quantum simulators.Science, 273(5278):1073–1078, 1996

    work page 1996

  28. [28]

    Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, Jan 2017

    work page 2017

  29. [29]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization.Quantum, 3:163, July 2019

    work page 2019

  30. [30]

    Ilo-Okeke, Valentin Ivannikov, and Tim Byrnes

    Yuping Mao, Manish Chaudhary, Manikandan Kondappan, Junheng Shi, Ebubechukwu O. Ilo-Okeke, Valentin Ivannikov, and Tim Byrnes. Measurement-based deterministic imaginary time evolution. Physical Review Letters, 131(11):110602, 2023

    work page 2023

  31. [31]

    Benjamin, and Xiao Yuan

    Sam McArdle, Suguru Endo, Al´ an Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry.Rev. Mod. Phys., 92:015003, Mar 2020

    work page 2020

  32. [32]

    Reducing circuit depth in lindblad simulations via step-size extrapolation.Phys

    Pegah Mohammadipour and Xiantao Li. Reducing circuit depth in lindblad simulations via step-size extrapolation.Phys. Rev. A, 112:062206, Dec 2025

    work page 2025

  33. [33]

    Generalized quantum signal processing.PRX Quantum, 5:020368, Jun 2024

    Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing.PRX Quantum, 5:020368, Jun 2024

    work page 2024

  34. [34]

    High-order randomized compiler for hamiltonian simulation.PRX Quantum, 5:020330, May 2024

    Kouhei Nakaji, Mohsen Bagherimehrab, and Al´ an Aspuru-Guzik. High-order randomized compiler for hamiltonian simulation.PRX Quantum, 5:020330, May 2024

    work page 2024

  35. [35]

    Compilation by stochastic hamiltonian sparsification.Quantum, 4:235, 2020

    Yingkai Ouyang, David R White, and Earl T Campbell. Compilation by stochastic hamiltonian sparsification.Quantum, 4:235, 2020

    work page 2020

  36. [36]

    Composite qdrift-product formulas for quantum and classical simulations in real and imaginary time.Phys

    Matthew Pocrnic, Matthew Hagan, Juan Carrasquilla, Dvira Segal, and Nathan Wiebe. Composite qdrift-product formulas for quantum and classical simulations in real and imaginary time.Phys. Rev. Res., 6:013224, Mar 2024

    work page 2024

  37. [37]

    Svore, Dave Wecker, and Matthias Troyer

    Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers.Proc. Natl. Acad. Sci. U.S.A., 114:7555–7560, 2017

    work page 2017

  38. [38]

    Somma, and Davide Orsucci

    Yi˘ git Suba¸ sı, Rolando D. Somma, and Davide Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing.Physical Review Letters, 122(6):060504, 2019

    work page 2019

  39. [39]

    Masuo Suzuki. Generalized trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems.Communications in Mathematical Physics, 51(2):183–190, 1976

    work page 1976

  40. [40]

    General theory of fractal path integrals with applications to many-body theories and statistical physics.Journal of Mathematical Physics, 32(2):400–407, 02 1991

    Masuo Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics.Journal of Mathematical Physics, 32(2):400–407, 02 1991

    work page 1991

  41. [41]

    Campbell

    Kianna Wan, Mario Berta, and Earl T. Campbell. Randomized quantum algorithm for statistical phase estimation.Physical Review Letters, 129(3):030503, 2022

    work page 2022

  42. [42]

    Qubit-efficient randomized quantum algorithms for linear algebra.PRX Quantum, 5(2):020324, 2024

    Samson Wang, Sam McArdle, and Mario Berta. Qubit-efficient randomized quantum algorithms for linear algebra.PRX Quantum, 5(2):020324, 2024

    work page 2024

  43. [43]

    Randomly compiled quantum simulation with exponentially reduced circuit depths

    James D Watson. Randomly compiled quantum simulation with exponentially reduced circuit depths. arXiv preprint arXiv:2411.04240, 2024. Appendix 20 Contents 1 Introduction 1 1.1 Standard qDRIFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....

    work page arXiv 2024

  44. [44]

    The cost of one level-ℓsample is C0 =N 0, C ℓ =N ℓ +N ℓ−1 = 3 2 Nℓ, ℓ≥1,(1.20) where Cℓ counts the fine and coupled coarse qDRIFT paths needed to form one correction sample

    Since NL = N0 2L, it is sufficient to take L= & log2 √ 2B εN0 !' + ,⌈x⌉ + := max{0,⌈x⌉},(1.19) soL=O(log(1/ε)). The cost of one level-ℓsample is C0 =N 0, C ℓ =N ℓ +N ℓ−1 = 3 2 Nℓ, ℓ≥1,(1.20) where Cℓ counts the fine and coupled coarse qDRIFT paths needed to form one correction sample. The key cancellation is p VℓCℓ ≤ r A Nℓ · 3 2 Nℓ = r 3A 2 , ℓ≥1,(1.21) ...

    work page