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

Pathwise Random Hamiltonian Simulation

Davide Cugini

quant-phSubmitted Aug 30, 2026• Announced Sep 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Randomized product formulas such as qDrift offer a resource-efficient alternative to deterministic Trotter--Suzuki decompositions for Hamiltonian simulation, removing their polynomial dependence on the number of Hamiltonian terms. qDrift, however, is intrinsically limited to first order in the evolution time, so its query complexity remains linear in the inverse of the target accuracy, $1/ε$. We introduce Pathwise Random Hamiltonian Simulation (PRHS), which extends qDrift to arbitrary order by subdividing each time step into $M$ correlated slices, each evolving under a term sampled from a quasi-probability distribution that we construct in closed form and prove unique, with a bias decaying factorially in $M$. Optimizing jointly over the number of slices $M$ and the number of independent blocks $N$ interpolates between the standard qDrift protocol at long times and a high-precision regime where the query cost grows slower than any power of $1/ε$, without requiring ancillary qubits. Numerical simulations of five molecular Hamiltonians confirm this advantage, with PRHS achieving accuracies two to four orders of magnitude beyond qDrift at equal query cost.

AI Summary

The paper asks whether qDrift can reach arbitrary order while retaining ancilla-free circuits, no explicit dependence on the number of Hamiltonian terms, and a closed-form sampling rule. Pathwise Random Hamiltonian Simulation (PRHS) replaces each qDrift step with $M$ correlated, equal-duration term evolutions, combined through signed quasi-probability weights. It therefore estimates evolved observables through weighted measurement outcomes rather than directly implementing an unsigned mixture of channels. A noncommutative generating-function construction gives the weights in terms of signed Stirling numbers; a separate injectivity argument establishes uniqueness under formal order-matching constraints. The stated bias bound for $N$ blocks over total time $T$ is $\delta(N,M)\le N(2\Lambda T/N)^{M+1}e^{2\Lambda T/N}/(M+1)!$, with $NM$ queries per circuit. The sampling overhead is $\|q_M\|_1^{2N}$, and the paper proves $\|q_M\|_1\le\binom{2M-1}{M}$. Using an empirically motivated exponential-overhead model, optimizing $M,N$ recovers qDrift at long times; at fixed $\Lambda T$ and high precision, $N=1$ and $M\sim\ln(1/\epsilon)/\ln\ln(1/\epsilon)$ give subpolynomial growth in inverse bias tolerance, including overhead relative to fixed statistical precision. Classical simulations of five molecular Hamiltonians on two or four qubits report two-to-four-order reductions in trace-distance bias versus qDrift at equal per-circuit query count, not equal total sampling cost. Stated limitations include signed-sampling variance, comparison restricted to product-formula-type methods, and a query model treating all term evolutions as equally expensive. Block-encoding/QSVT approaches retain better asymptotic time and accuracy scaling.

Little sign of AI-generated textOverclaimsMissing comparisonPossible error

Central claim may not hold: The operational rules omit coefficient signs and incorrectly prescribe sampling from signed q_M/||q_M||_1 rather than absolute weights with signed outcome reweighting, although both errors have straightforward local repairs. The supplied proofs do not establish the central factorial diamond-norm remainder bound or its asserted linear accumulation across blocks, since formal order matching alone supplies neither guarantee and the signed block map need not be contractive. The uniqueness result applies to universal formal-word matching, whereas fixed Hamiltonians can admit many different path distributions with the same approximation order. The subpolynomial cost is a bias-reduction and relative sampling-overhead result at fixed statistical precision, not a subpolynomial full cost for estimating observables to accuracy epsilon or directly implementing a physical simulation channel. The molecular benchmarks demonstrate improved systematic error at equal circuit length, not at equal total query expenditure including the additional sampling.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
5+9 pages, 1 figure

Related papers

High-Order Randomized Compiler for Hamiltonian Simulation

Kouhei Nakaji, Mohsen Bagherimehrab, Alán Aspuru‐Guzik

Hamiltonian simulation is known to be one of the fundamental building blocks of a variety of quantum algorithms such as its most immediate application, that of simulating many-body systems to extract their physical properties. In this work, we present qSWIFT, a high-order randomized algorithm for Hamiltonian simulation. In qSWIFT, the required number of gates for a given precision is independent of the number of terms in the Hamiltonian, while the systematic error is exponentially reduced with regard to the order parameter. In this respect, our qSWIFT is a higher-order counterpart of the previously proposed quantum stochastic drift protocol (qDRIFT), the number of gates in which scales linearly with the inverse of the precision required. We construct the qSWIFT channel and establish a rigorous bound for the systematic error quantified by the diamond norm. qSWIFT provides an algorithm to estimate given physical quantities by using a system with one ancilla qubit, which is as simple as other product-formula-based approaches such as regular Trotter-Suzuki decompositions and qDRIFT. Our numerical experiment reveals that the required number of gates in qSWIFT is significantly reduced compared to qDRIFT. In particular, the advantage is significant for problems where high precision is required; e.g., to achieve a systematic relative propagation error of 10−6 , the required number of gates in third-order qSWIFT is 1000 times smaller than that of qDRIFT. Published by the American Physical Society 2024

arXiv:2302.14811•PRX Quantum•May 8, 2024•27 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

Fast Random Compilers for Time-Dependent and Time-Independent Lindbladian Simulation

Youngjin Seo, Dhrumil Patel, Hyukjoon Kwon +1 more

Randomized product formulas provide simple and flexible methods for quantum simulation. While qDRIFT-type randomized simulation has been extended to Lindbladian dynamics, higher-order randomized compilers have primarily been developed for Hamiltonian simulation. In this work, we develop first- and second-order randomized sampling algorithms for Lindbladian simulation in both the time-independent and time-dependent settings. Building on first-order qDRIFT-type Lindbladian simulation, we introduce a qSWIFT-type second-order correction for time-independent Lindbladians with a finite local decomposition. For $λt \geq 1$, where $λ$ is the sum of the Hamiltonian coefficients and dissipative rates, the resulting approximation achieves normalized diamond-norm error at most $\varepsilon$ using $r=O(λ^2 t^2/\sqrt{\varepsilon})$ time slices, improving the $\varepsilon^{-1}$ precision dependence of the first-order qDRIFT-type approximation. We then develop first- and second-order continuous-time sampling algorithms for general time-dependent Lindbladians, with the second-order construction likewise achieving an $\varepsilon^{-1/2}$ dependence on the target precision in the number of time slices. We further extend the time-dependent construction to a linear-combination input model over local Hamiltonian and dissipative generators, allowing the randomized sampler to be formulated in terms of local evolutions rather than the full time-dependent Lindbladian. Because the second-order corrected maps need not be CPTP, we use them to estimate observable expectation values rather than to deterministically prepare output states.

quant-pharXiv:2610.05288•Oct 6, 2026•0 citations

Optimal Lower Bounds for Hamiltonian Simulation

Alexander Zlokapa, Richard R. Allen, Aram W. Harrow

For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

quant-pharXiv:2607.19852•Jul 23, 2026•0 citations

Importance sampling for stochastic quantum simulations

Oriel Kiss, Michele Grossi, Alessandro Roggero

Simulating many-body quantum systems is a promising task for quantum computers. However, the depth of most algorithms, such as product formulas, scales with the number of terms in the Hamiltonian, and can therefore be challenging to implement on near-term, as well as early fault-tolerant quantum devices. An efficient solution is given by the stochastic compilation protocol known as qDrift, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. In this work, we unify the qDrift protocol with importance sampling, allowing us to sample from arbitrary probability distributions, while controlling both the bias, as well as the statistical fluctuations. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Moreover, we incorporate recent work on composite channel and compute rigorous bounds on the bias and variance, showing how to choose the number of samples, experiments, and time steps for a given target accuracy. These results lead to a more efficient implementation of the qDrift protocol, both with and without the use of composite channels. Theoretical results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.

arXiv:2212.05952•Quantum•Apr 13, 2023•17 citations

Optimized Randomized Hamiltonian Simulation via Average-Error Analysis

Hayata Morisaki, Keisuke Fujii

Hamiltonian simulation is a central application of quantum computing. Randomized Hamiltonian simulation approximates the target dynamics by sampling quantum circuits and often allows simpler circuit implementations. We develop a framework for randomized Hamiltonian simulation in which Hamiltonian terms are sampled with arbitrary probabilities and the corresponding short-time evolutions are implemented sequentially. The leading channel error relative to ideal time evolution is governed by the variance of the sampled generators. Minimizing the variance-based upper bound on the worst-case error recovers qDRIFT, a leading randomized Hamiltonian simulation algorithm that samples terms in proportion to their operator norms. For typical input states, however, this sampling distribution need not be optimal. Minimizing Haar-averaged error bounds instead yields sampling probabilities proportional to the Hilbert-Schmidt norms of the terms. This choice can provide smaller average-error bounds than conventional qDRIFT. For Hamiltonians expressed as sums of Pauli strings, we combine this framework with commuting Pauli grouping to obtain smaller error bounds than conventional qDRIFT at fixed $R_z$ depth. Numerical benchmarks for the Sachdev-Ye-Kitaev model show error-bound improvement factors consistent with linear scaling in the number of qubits. For the 108-qubit FeMoco Hamiltonian, the error bounds are reduced by a factor of about 5.65. These results establish average-error optimization as a practical design principle for randomized Hamiltonian simulation.

quant-pharXiv:2609.36694•Sep 30, 2026•0 citations
Randomized product formulas such as qDrift offer a resource-efficient alternative to deterministic Trotter--Suzuki decompositions for Hamiltonian simulation, removing their polynomial dependence on the number of Hamiltonian terms. qDrift, however, is intrinsically limited to first order in the evolution time, so its query complexity remains linear in the inverse of the target accuracy, 1/ε1/ε1/ε. We introduce Pathwise Random Hamiltonian Simulation (PRHS), which extends qDrift to arbitrary order by subdividing each time step into MMM correlated slices, each evolving under a term sampled from a quasi-probability distribution that we construct in closed form and prove unique, with a bias decaying factorially in MMM. Optimizing jointly over the number of slices MMM and the number of independent blocks NNN interpolates between the standard qDrift protocol at long times and a high-precision regime where the query cost grows slower than any power of 1/ε1/ε1/ε, without requiring ancillary qubits. Numerical simulations of five molecular Hamiltonians confirm this advantage, with PRHS achieving accuracies two to four orders of magnitude beyond qDrift at equal query cost.
The paper asks whether qDrift can reach arbitrary order while retaining ancilla-free circuits, no explicit dependence on the number of Hamiltonian terms, and a closed-form sampling rule. Pathwise Random Hamiltonian Simulation (PRHS) replaces each qDrift step with MMM correlated, equal-duration term evolutions, combined through signed quasi-probability weights. It therefore estimates evolved observables through weighted measurement outcomes rather than directly implementing an unsigned mixture of channels.
A noncommutative generating-function construction gives the weights in terms of signed Stirling numbers; a separate injectivity argument establishes uniqueness under formal order-matching constraints. The stated bias bound for NNN blocks over total time TTT is δ(N,M)≤N(2ΛT/N)M+1e2ΛT/N/(M+1)!\delta(N,M)\le N(2\Lambda T/N)^{M+1}e^{2\Lambda T/N}/(M+1)!δ(N,M)≤N(2ΛT/N)M+1e2ΛT/N/(M+1)!, with NMNMNM queries per circuit. The sampling overhead is ∥qM∥12N\|q_M\|_1^{2N}∥qM​∥12N​, and the paper proves ∥qM∥1≤(2M−1M)\|q_M\|_1\le\binom{2M-1}{M}∥qM​∥1​≤(M2M−1​). Using an empirically motivated exponential-overhead model, optimizing M,NM,NM,N recovers qDrift at long times; at fixed ΛT\Lambda TΛT and high precision, N=1N=1N=1 and M∼ln⁡(1/ϵ)/ln⁡ln⁡(1/ϵ)M\sim\ln(1/\epsilon)/\ln\ln(1/\epsilon)M∼ln(1/ϵ)/lnln(1/ϵ) give subpolynomial growth in inverse bias tolerance, including overhead relative to fixed statistical precision.
Classical simulations of five molecular Hamiltonians on two or four qubits report two-to-four-order reductions in trace-distance bias versus qDrift at equal per-circuit query count, not equal total sampling cost. Stated limitations include signed-sampling variance, comparison restricted to product-formula-type methods, and a query model treating all term evolutions as equally expensive. Block-encoding/QSVT approaches retain better asymptotic time and accuracy scaling.
Hamiltonian simulation is known to be one of the fundamental building blocks of a variety of quantum algorithms such as its most immediate application, that of simulating many-body systems to extract their physical properties. In this work, we present qSWIFT, a high-order randomized algorithm for Hamiltonian simulation. In qSWIFT, the required number of gates for a given precision is independent of the number of terms in the Hamiltonian, while the systematic error is exponentially reduced with regard to the order parameter. In this respect, our qSWIFT is a higher-order counterpart of the previously proposed quantum stochastic drift protocol (qDRIFT), the number of gates in which scales linearly with the inverse of the precision required. We construct the qSWIFT channel and establish a rigorous bound for the systematic error quantified by the diamond norm. qSWIFT provides an algorithm to estimate given physical quantities by using a system with one ancilla qubit, which is as simple as other product-formula-based approaches such as regular Trotter-Suzuki decompositions and qDRIFT. Our numerical experiment reveals that the required number of gates in qSWIFT is significantly reduced compared to qDRIFT. In particular, the advantage is significant for problems where high precision is required; e.g., to achieve a systematic relative propagation error of 10−6 , the required number of gates in third-order qSWIFT is 1000 times smaller than that of qDRIFT. Published by the American Physical Society 2024
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.
Randomized product formulas provide simple and flexible methods for quantum simulation. While qDRIFT-type randomized simulation has been extended to Lindbladian dynamics, higher-order randomized compilers have primarily been developed for Hamiltonian simulation. In this work, we develop first- and second-order randomized sampling algorithms for Lindbladian simulation in both the time-independent and time-dependent settings. Building on first-order qDRIFT-type Lindbladian simulation, we introduce a qSWIFT-type second-order correction for time-independent Lindbladians with a finite local decomposition. For λt≥1λt \geq 1λt≥1, where λλλ is the sum of the Hamiltonian coefficients and dissipative rates, the resulting approximation achieves normalized diamond-norm error at most ε\varepsilonε using r=O(λ2t2/ε)r=O(λ^2 t^2/\sqrt{\varepsilon})r=O(λ2t2/ε​) time slices, improving the ε−1\varepsilon^{-1}ε−1 precision dependence of the first-order qDRIFT-type approximation. We then develop first- and second-order continuous-time sampling algorithms for general time-dependent Lindbladians, with the second-order construction likewise achieving an ε−1/2\varepsilon^{-1/2}ε−1/2 dependence on the target precision in the number of time slices. We further extend the time-dependent construction to a linear-combination input model over local Hamiltonian and dissipative generators, allowing the randomized sampler to be formulated in terms of local evolutions rather than the full time-dependent Lindbladian. Because the second-order corrected maps need not be CPTP, we use them to estimate observable expectation values rather than to deterministically prepare output states.
For Hamiltonian H=∑jhjH = \sum_j h_jH=∑j​hj​, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥\|h_j\|∥hj​∥, time ttt, and trace-distance error εεε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥\|h_j\|∥hj​∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε1/ε1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
Simulating many-body quantum systems is a promising task for quantum computers. However, the depth of most algorithms, such as product formulas, scales with the number of terms in the Hamiltonian, and can therefore be challenging to implement on near-term, as well as early fault-tolerant quantum devices. An efficient solution is given by the stochastic compilation protocol known as qDrift, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. In this work, we unify the qDrift protocol with importance sampling, allowing us to sample from arbitrary probability distributions, while controlling both the bias, as well as the statistical fluctuations. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Moreover, we incorporate recent work on composite channel and compute rigorous bounds on the bias and variance, showing how to choose the number of samples, experiments, and time steps for a given target accuracy. These results lead to a more efficient implementation of the qDrift protocol, both with and without the use of composite channels. Theoretical results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
Hamiltonian simulation is a central application of quantum computing. Randomized Hamiltonian simulation approximates the target dynamics by sampling quantum circuits and often allows simpler circuit implementations. We develop a framework for randomized Hamiltonian simulation in which Hamiltonian terms are sampled with arbitrary probabilities and the corresponding short-time evolutions are implemented sequentially. The leading channel error relative to ideal time evolution is governed by the variance of the sampled generators. Minimizing the variance-based upper bound on the worst-case error recovers qDRIFT, a leading randomized Hamiltonian simulation algorithm that samples terms in proportion to their operator norms. For typical input states, however, this sampling distribution need not be optimal. Minimizing Haar-averaged error bounds instead yields sampling probabilities proportional to the Hilbert-Schmidt norms of the terms. This choice can provide smaller average-error bounds than conventional qDRIFT. For Hamiltonians expressed as sums of Pauli strings, we combine this framework with commuting Pauli grouping to obtain smaller error bounds than conventional qDRIFT at fixed RzR_zRz​ depth. Numerical benchmarks for the Sachdev-Ye-Kitaev model show error-bound improvement factors consistent with linear scaling in the number of qubits. For the 108-qubit FeMoco Hamiltonian, the error bounds are reduced by a factor of about 5.65. These results establish average-error optimization as a practical design principle for randomized Hamiltonian simulation.