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

Composite QDrift-Product Formulas for Quantum and Classical Simulations in Real and Imaginary Time

Matthew Pocrnic, Hagan, Matthew, Juan Carrasquilla, Dvira Segal, Nathan Wiebe

Published Jun 28, 2023• 0 citations
arXivHTMLPDF

Abstract

Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian $H$ for a given simulation problem into subsets $A$ and $B$ such that $H=A+B$, where the terms in $A$ are simulated with a Trotter-Suzuki channel and the $B$ terms are randomly sampled via the QDrift algorithm. Here we show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations. We upper-bound the induced Schatten-$1 \to 1$ norm on both imaginary-time QDrift and Composite channels. Another recent result demonstrated that simulations of Hamiltonians containing geometrically-local interactions for systems defined on finite lattices can be improved by decomposing $H$ into subsets that contain only terms supported on that subset of the lattice using a Lieb-Robinson argument. Here, we provide a quantum algorithm by unifying this result with the composite approach into ``local composite channels" and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form $e^{-iH_j t}$ and $e^{-H_j β}$ to meet a certain error tolerance $ε$. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a $\approx 20$ fold speedup that occurs for a simulation of Jellium.

DOI
10.48550/arxiv.2306.16572

Related papers

Composite Qdrift-product formulas for quantum and classical simulations in real and imaginary time

Matthew Pocrnic, Matthew Hagan, Juan Carrasquilla +2 more

Recent study has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian H for a given simulation problem into subsets A and B such that H=A+B , where the terms in A are simulated with a Trotter-Suzuki channel and the B terms are randomly sampled via the Qdrift algorithm. Here we extend Qdrift and composite product formulas to imaginary time, formulating candidate classical algorithms for quantum Monte Carlo calculations. We upper bound the induced Schatten- 1→1 norm on both imaginary-time Qdrift and composite channels. Another recent result demonstrated that simulations of lattice Hamiltonians containing geometrically local interactions can be improved using a Lieb-Robinson argument to decompose H into subsets that contain only terms supported on that subset of the lattice. Here, we provide a quantum algorithm by unifying this result with the composite approach into “local composite channels” and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e−iHjt and e−Hjβ to meet a certain error tolerance ε . In doing so, we optimize the partitioning into sets A and B using gradient boosted tree models from machine learning. These numerical studies are important given that product formulas have been historically known to outperform analytic upper bounds. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈20 -fold speedup that occurs in the simulation of Jellium. Published by the American Physical Society 2024

Physical Review Research•Mar 1, 2024•9 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

Composite Quantum Simulations

Matthew Hagan, Nathan Wiebe

In this paper we provide a framework for combining multiple quantum simulation methods, such as Trotter-Suzuki formulas and QDrift into a single Composite channel that builds upon older coalescing ideas for reducing gate counts. The central idea behind our approach is to use a partitioning scheme that allocates a Hamiltonian term to the Trotter or QDrift part of a channel within the simulation. This allows us to simulate small but numerous terms using QDrift while simulating the larger terms using a high-order Trotter-Suzuki formula. We prove rigorous bounds on the diamond distance between the Composite channel and the ideal simulation channel and show under what conditions the cost of implementing the Composite channel is asymptotically upper bounded by the methods that comprise it for both probabilistic partitioning of terms and deterministic partitioning. Finally, we discuss strategies for determining partitioning schemes as well as methods for incorporating different simulation methods within the same framework.

arXiv:2206.06409•Quantum•Nov 14, 2023•21 citations

Concentration for Random Product Formulas

Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng +1 more

Quantum simulation has wide applications in quantum chemistry and physics.Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation.Among them, a simple and powerful technique, called QDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution.QDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas.This work aims to understand the origin of this speedup by comprehensively analyzing a single realization of the random product formula produced by QDRIFT.The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error.The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian.Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state.In contrast, in deterministic settings, such an improvement usually requires initial state knowledge.The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas.Our bounds are saturated by certain commuting Hamiltonians.

arXiv:2008.11751•PRX Quantum•Oct 7, 2021•68 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

Pathwise Random Hamiltonian Simulation

Davide Cugini

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.

quant-pharXiv:2608.29756•Sep 1, 2026•0 citations
Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian HHH for a given simulation problem into subsets AAA and BBB such that H=A+BH=A+BH=A+B, where the terms in AAA are simulated with a Trotter-Suzuki channel and the BBB terms are randomly sampled via the QDrift algorithm. Here we show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations. We upper-bound the induced Schatten-1→11 \to 11→1 norm on both imaginary-time QDrift and Composite channels. Another recent result demonstrated that simulations of Hamiltonians containing geometrically-local interactions for systems defined on finite lattices can be improved by decomposing HHH into subsets that contain only terms supported on that subset of the lattice using a Lieb-Robinson argument. Here, we provide a quantum algorithm by unifying this result with the composite approach into ``local composite channels" and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e−iHjte^{-iH_j t}e−iHj​t and e−Hjβe^{-H_j β}e−Hj​β to meet a certain error tolerance εεε. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈20\approx 20≈20 fold speedup that occurs for a simulation of Jellium.
Recent study has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian H for a given simulation problem into subsets A and B such that H=A+B , where the terms in A are simulated with a Trotter-Suzuki channel and the B terms are randomly sampled via the Qdrift algorithm. Here we extend Qdrift and composite product formulas to imaginary time, formulating candidate classical algorithms for quantum Monte Carlo calculations. We upper bound the induced Schatten- 1→1 norm on both imaginary-time Qdrift and composite channels. Another recent result demonstrated that simulations of lattice Hamiltonians containing geometrically local interactions can be improved using a Lieb-Robinson argument to decompose H into subsets that contain only terms supported on that subset of the lattice. Here, we provide a quantum algorithm by unifying this result with the composite approach into “local composite channels” and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e−iHjt and e−Hjβ to meet a certain error tolerance ε . In doing so, we optimize the partitioning into sets A and B using gradient boosted tree models from machine learning. These numerical studies are important given that product formulas have been historically known to outperform analytic upper bounds. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈20 -fold speedup that occurs in the simulation of Jellium. Published by the American Physical Society 2024
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.
In this paper we provide a framework for combining multiple quantum simulation methods, such as Trotter-Suzuki formulas and QDrift into a single Composite channel that builds upon older coalescing ideas for reducing gate counts. The central idea behind our approach is to use a partitioning scheme that allocates a Hamiltonian term to the Trotter or QDrift part of a channel within the simulation. This allows us to simulate small but numerous terms using QDrift while simulating the larger terms using a high-order Trotter-Suzuki formula. We prove rigorous bounds on the diamond distance between the Composite channel and the ideal simulation channel and show under what conditions the cost of implementing the Composite channel is asymptotically upper bounded by the methods that comprise it for both probabilistic partitioning of terms and deterministic partitioning. Finally, we discuss strategies for determining partitioning schemes as well as methods for incorporating different simulation methods within the same framework.
Quantum simulation has wide applications in quantum chemistry and physics.Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation.Among them, a simple and powerful technique, called QDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution.QDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas.This work aims to understand the origin of this speedup by comprehensively analyzing a single realization of the random product formula produced by QDRIFT.The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error.The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian.Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state.In contrast, in deterministic settings, such an improvement usually requires initial state knowledge.The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas.Our bounds are saturated by certain commuting Hamiltonians.
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 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.