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:2210.11281 · Physical Review A

Doubling the order of approximation via the randomized product formula

Chien‐Hung Cho, Dominic William Berry, Min-Hsiu Hsieh

Published Jun 24, 2024• 14 citations
arXivHTMLPDF

Abstract

Hamiltonian simulation is a major application of quantum computing, for example, enabling prediction of the properties of molecules. Prior work has used product formulas with randomization to improve performance, but has only yielded modest improvements over the excellent performance provided by deterministic high-order product formulas. In this work, we provide a randomized scheme that greatly increases the order of product formulas, thereby providing a large advantage over the best-performing deterministic schemes. Our scheme is based on applying randomly chosen corrections to a high-order symmetric product formula. If the original product formula is of order $2k$ (so the error is of order $2k+1$), then the corrected formula is of order $4k+1$, corresponding to a doubling of the order of the error. In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example, the Pauli strings as are commonly used in the simulation of quantum chemistry.

DOI
10.1103/physreva.109.062431

Related papers

Randomizing multi-product formulas for improved Hamiltonian simulation.

Paul K. Faehrmann, Mark Steudtner, Richard Kueng +2 more

Quantum simulation suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry and materials science. While the majority of quantum simulation algorithms is deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling and higher-order multi-product formulas as they are used in linear-combination-of-unitaries (LCU) algorithms. In doing so, we propose a framework of randomized sampling that could prove useful for programmable quantum simulators and present two new algorithms tailored to it. Our framework greatly reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by standard LCU methods, rendering it especially useful for near-term quantum computing. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We also discuss examples at hand of a Hamiltonian comprising pairwise anticommuting terms.

•Jan 19, 2021•7 citations

Randomizing multi-product formulas for Hamiltonian simulation

Paul K. Faehrmann, Mark Steudtner, Richard Kueng +2 more

Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev–Ye–Kitaev model, for which the method provides a favorable scaling in the effort.

arXiv:2101.07808•Quantum•Sep 19, 2022•40 citations

Randomized product formulas beyond optimal deterministic scaling

Leeseok Kim, Luis Pedro García-Pintos

Product formulas, also known as Trotter formulas, are among the most widely used and practical methods for simulating quantum systems on quantum computers. Here we introduce two new classes of randomized product formulas for simulating Hamiltonians with separated energy scales, $H=A+αB$, where $α$ is small. In the standard access model, where one can implement exponentials of $A$ and $B$ separately, our randomized formulas achieve $\mathcal O(α^2)$ error scaling at the cost of only doubling the gate depth of the corresponding deterministic formula. We further prove an $Ω(α)$ lower bound for deterministic product formulas. In a stronger access model, allowing exponentials of $A+αB_\ell$ for $B = \sum_{\ell}B_\ell$, our randomized formula, based on Trotter Heuristic Resource Improved Formulas for Time-dynamics (THRIFT)~[J. L. Bosse et al., Nat. Commun. 16, 2673 (2025)], achieves $\mathcal O(α^3)$ error scaling with only constant-factor expected gate overhead. We also establish an $Ω(α^2)$ lower bound for deterministic product formulas in this access model. Numerical simulations confirm gate-count reductions for simulating physically motivated systems.

quant-pharXiv:2608.07720•Aug 11, 2026•0 citations

Phase Estimation with Partially Randomized Time Evolution

Jakob Günther, Freek Witteveen, Alexander Schmidhuber +3 more

Quantum phase estimation combined with Hamiltonian simulation is the most promising algorithmic framework to computing ground-state energies on quantum computers. Its main computational overhead derives from the Hamiltonian simulation subroutine. In this paper we use randomization to speed up product formulas, one of the standard approaches to Hamiltonian simulation. We propose partially randomized Hamiltonian simulation methods in which some terms are kept deterministically and others are randomly sampled. We perform a detailed resource estimate for single-ancilla phase estimation using partially randomized product formulas for benchmark systems in quantum chemistry and obtain orders-of-magnitude improvements compared to other simulations based on product formulas. When applied to the hydrogen chain, we have numerical evidence that our methods exhibit asymptotic scaling with the system size that is competitive with the best known qubitization approaches.

arXiv:2503.05647•PRX Quantum•Mar 31, 2026•4 citations

Selection and Improvement of Product Formulae for Best Performance of Quantum Simulation

Mauro E. S. Morales, Pedro C. S. Costa, Giacomo Pantaleoni +3 more

Abstract Quantum algorithms for simulation of Hamiltonian evolution are often based on product formulae. The fractal methods give a systematic way to find arbitrarily high-order product formulae, but result in a large number of exponentials. On the other hand, product formulae with fewer exponentials can be found by numerical solution of simultaneous non-linear equations. It is also possible to reduce the cost of long-time simulations by processing, where a kernel is repeated and a processor need only be applied at the beginning and end of the simulation. In this work, we found thousands of new product formulae, and numerically tested these formulae, together with many formulae from prior literature. We provide methods to fairly compare product formulae of different lengths and different orders. For the case of 8th order, we have found new product formulae with exceptional performance, about two orders of magnitude better accuracy than prior work, both in the processed and non-processed cases. The processed product formula provides the best performance due to being shorter than the non-processed product formula. It outperforms all other tested product formulae over a range of many orders of magnitude in system parameters T (time) and ε (allowable error). That includes reasonable combinations of parameters to be used in quantum algorithms, where the size of the simulation is large enough to be classically intractable, but not so large it takes an impractically long time on a quantum computer.

arXiv:2210.15817•Quantum Information and Computation•Jan 31, 2025•16 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
Hamiltonian simulation is a major application of quantum computing, for example, enabling prediction of the properties of molecules. Prior work has used product formulas with randomization to improve performance, but has only yielded modest improvements over the excellent performance provided by deterministic high-order product formulas. In this work, we provide a randomized scheme that greatly increases the order of product formulas, thereby providing a large advantage over the best-performing deterministic schemes. Our scheme is based on applying randomly chosen corrections to a high-order symmetric product formula. If the original product formula is of order 2k2k2k (so the error is of order 2k+12k+12k+1), then the corrected formula is of order 4k+14k+14k+1, corresponding to a doubling of the order of the error. In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example, the Pauli strings as are commonly used in the simulation of quantum chemistry.
Quantum simulation suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry and materials science. While the majority of quantum simulation algorithms is deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling and higher-order multi-product formulas as they are used in linear-combination-of-unitaries (LCU) algorithms. In doing so, we propose a framework of randomized sampling that could prove useful for programmable quantum simulators and present two new algorithms tailored to it. Our framework greatly reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by standard LCU methods, rendering it especially useful for near-term quantum computing. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We also discuss examples at hand of a Hamiltonian comprising pairwise anticommuting terms.
Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev–Ye–Kitaev model, for which the method provides a favorable scaling in the effort.
Product formulas, also known as Trotter formulas, are among the most widely used and practical methods for simulating quantum systems on quantum computers. Here we introduce two new classes of randomized product formulas for simulating Hamiltonians with separated energy scales, H=A+αBH=A+αBH=A+αB, where ααα is small. In the standard access model, where one can implement exponentials of AAA and BBB separately, our randomized formulas achieve O(α2)\mathcal O(α^2)O(α2) error scaling at the cost of only doubling the gate depth of the corresponding deterministic formula. We further prove an Ω(α)Ω(α)Ω(α) lower bound for deterministic product formulas. In a stronger access model, allowing exponentials of A+αBℓA+αB_\ellA+αBℓ​ for B=∑ℓBℓB = \sum_{\ell}B_\ellB=∑ℓ​Bℓ​, our randomized formula, based on Trotter Heuristic Resource Improved Formulas for Time-dynamics (THRIFT)~[J. L. Bosse et al., Nat. Commun. 16, 2673 (2025)], achieves O(α3)\mathcal O(α^3)O(α3) error scaling with only constant-factor expected gate overhead. We also establish an Ω(α2)Ω(α^2)Ω(α2) lower bound for deterministic product formulas in this access model. Numerical simulations confirm gate-count reductions for simulating physically motivated systems.
Quantum phase estimation combined with Hamiltonian simulation is the most promising algorithmic framework to computing ground-state energies on quantum computers. Its main computational overhead derives from the Hamiltonian simulation subroutine. In this paper we use randomization to speed up product formulas, one of the standard approaches to Hamiltonian simulation. We propose partially randomized Hamiltonian simulation methods in which some terms are kept deterministically and others are randomly sampled. We perform a detailed resource estimate for single-ancilla phase estimation using partially randomized product formulas for benchmark systems in quantum chemistry and obtain orders-of-magnitude improvements compared to other simulations based on product formulas. When applied to the hydrogen chain, we have numerical evidence that our methods exhibit asymptotic scaling with the system size that is competitive with the best known qubitization approaches.
Abstract Quantum algorithms for simulation of Hamiltonian evolution are often based on product formulae. The fractal methods give a systematic way to find arbitrarily high-order product formulae, but result in a large number of exponentials. On the other hand, product formulae with fewer exponentials can be found by numerical solution of simultaneous non-linear equations. It is also possible to reduce the cost of long-time simulations by processing, where a kernel is repeated and a processor need only be applied at the beginning and end of the simulation. In this work, we found thousands of new product formulae, and numerically tested these formulae, together with many formulae from prior literature. We provide methods to fairly compare product formulae of different lengths and different orders. For the case of 8th order, we have found new product formulae with exceptional performance, about two orders of magnitude better accuracy than prior work, both in the processed and non-processed cases. The processed product formula provides the best performance due to being shorter than the non-processed product formula. It outperforms all other tested product formulae over a range of many orders of magnitude in system parameters T (time) and ε (allowable error). That includes reasonable combinations of parameters to be used in quantum algorithms, where the size of the simulation is large enough to be classically intractable, but not so large it takes an impractically long time on a quantum computer.
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.