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:2302.14811 · PRX Quantum

High-Order Randomized Compiler for Hamiltonian Simulation

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

Published May 8, 2024• 27 citations
arXivHTMLPDF

Abstract

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

DOI
10.1103/prxquantum.5.020330

Related papers

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

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

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

qSHIFT: An Adaptive Sampling Protocol for Higher-Order Quantum Simulation

Sangjin Lee, Sangkook Choi

Early fault-tolerant quantum computers are expected to support reliable but depth-limited quantum circuits, while classical computational resources remain available. These conditions have motivated hybrid coherent algorithms which use quantum simulation as a central algorithmic primitive. This trend calls for quantum-simulation methods that operate with shallow circuits and admit systematic improvements in gate-complexity scaling. Here, we introduce qSHIFT, an adaptive sampling protocol for simulating a Hamiltonian $H=\sum_{i=1}^{L}h_iH_i$. qSHIFT achieves gate complexity $\mathcal{O}_r\left((λt)^{1+1/r}/\varepsilon^{1/r}\right)$, where $r$ is an algorithmic parameter, $λ=\sum_i |h_i|$ and $\varepsilon$ denotes the target precision. Relative to qDRIFT, increasing $r$ systematically improves the gate complexity for a given target precision without incurring extra quantum cost. Unlike Trotterization, the number of sampled gates is nominally independent of $L$. qSHIFT retains the elementary gate set of qDRIFT and, unlike qSWIFT, requires neither ancillary qubits nor controlled operations. The improved gate complexity scaling is obtained at the cost of a classical calculation involving $L^r$ coefficients at each adaptive sampling round.

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

Randomly Compiled Quantum Simulation with Exponentially Reduced Circuit Depths

James D. Watson

The quantum stochastic drift protocol, also known as qDRIFT, has become a popular algorithm for implementing time-evolution of quantum systems using randomised compiling. In this work we develop qFLO, a higher order randomised algorithm for time-evolution. To estimate an observable expectation value at time $T$ to precision $ε$, we show it is sufficient to use circuit depths of $O(T^2\log(1/ε))$ -- an exponential improvement over standard qDRIFT requirements with respect to $ε$. The protocol achieves this using $O(1/ε^2)$ repeated runs of the standard qDRIFT protocol combined with classical post-processing in the form of Richardson extrapolation. Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices. Furthermore, it is well-conditioned and inherits many desirable properties of randomly compiled simulation methods, including circuit depths that do not explicitly depend on the number of terms in the Hamiltonian.

arXiv:2411.04240•Nov 6, 2024•1 citation

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
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
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.
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.
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.
Early fault-tolerant quantum computers are expected to support reliable but depth-limited quantum circuits, while classical computational resources remain available. These conditions have motivated hybrid coherent algorithms which use quantum simulation as a central algorithmic primitive. This trend calls for quantum-simulation methods that operate with shallow circuits and admit systematic improvements in gate-complexity scaling. Here, we introduce qSHIFT, an adaptive sampling protocol for simulating a Hamiltonian H=∑i=1LhiHiH=\sum_{i=1}^{L}h_iH_iH=∑i=1L​hi​Hi​. qSHIFT achieves gate complexity Or((λt)1+1/r/ε1/r)\mathcal{O}_r\left((λt)^{1+1/r}/\varepsilon^{1/r}\right)Or​((λt)1+1/r/ε1/r), where rrr is an algorithmic parameter, λ=∑i∣hi∣λ=\sum_i |h_i|λ=∑i​∣hi​∣ and ε\varepsilonε denotes the target precision. Relative to qDRIFT, increasing rrr systematically improves the gate complexity for a given target precision without incurring extra quantum cost. Unlike Trotterization, the number of sampled gates is nominally independent of LLL. qSHIFT retains the elementary gate set of qDRIFT and, unlike qSWIFT, requires neither ancillary qubits nor controlled operations. The improved gate complexity scaling is obtained at the cost of a classical calculation involving LrL^rLr coefficients at each adaptive sampling round.
The quantum stochastic drift protocol, also known as qDRIFT, has become a popular algorithm for implementing time-evolution of quantum systems using randomised compiling. In this work we develop qFLO, a higher order randomised algorithm for time-evolution. To estimate an observable expectation value at time TTT to precision εεε, we show it is sufficient to use circuit depths of O(T2log⁡(1/ε))O(T^2\log(1/ε))O(T2log(1/ε)) -- an exponential improvement over standard qDRIFT requirements with respect to εεε. The protocol achieves this using O(1/ε2)O(1/ε^2)O(1/ε2) repeated runs of the standard qDRIFT protocol combined with classical post-processing in the form of Richardson extrapolation. Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices. Furthermore, it is well-conditioned and inherits many desirable properties of randomly compiled simulation methods, including circuit depths that do not explicitly depend on the number of terms in the Hamiltonian.
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.