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

Term Grouping and Travelling Salesperson for Digital Quantum Simulation

Kaiwen Gui, Teague Tomesh, Pranav Gokhale, Yunong Shi, Frederic T. Chong, Margaret Martonosi, Martin Suchara

Published Jan 16, 2020• 20 citations
arXivHTMLPDF

Abstract

Digital simulation of quantum dynamics by evaluating the time evolution of a Hamiltonian is the initially proposed application of quantum computing. The large number of quantum gates required for emulating the complete second quantization form of the Hamiltonian, however, makes such an approach unsuitable for near-term devices with limited gate fidelities that cause high physical errors. In addition, Trotter error caused by noncommuting terms can accumulate and harm the overall circuit fidelity, thus causing algorithmic errors. In this paper, we propose a new term ordering strategy, max-commute-tsp (MCTSP), that simultaneously mitigates both algorithmic and physical errors. First, we improve the Trotter fidelity compared with previously proposed optimization by reordering Pauli terms and partitioning them into commuting families. We demonstrate the practicality of this method by constructing and evaluating quantum circuits that simulate different molecular Hamiltonians, together with theoretical explanations for the fidelity improvements from our term grouping method. Second, we describe a new gate cancellation technique that reduces the high gate counts by formulating the gate cancellation problem as a travelling salesperson problem, together with benchmarking experiments. Finally, we also provide benchmarking results that demonstrate the combined advantage of max-commute-tsp to mitigate both physical and algorithmic errors via quantum circuit simulation under realistic noise models.

DOI
10.48550/arxiv.2001.05983

Related papers

Constant-Depth Multi-Product Formula for Trotter Error Mitigation in Near-Term Digital Quantum Simulation

Chan Bin Bark, Sangjin Lee, Kwang Jun Ahn +3 more

Digital quantum simulation of many-body dynamics faces a tension between algorithmic Trotter error and physical noise that accumulates with circuit depth. Typical higher-order product formulas mitigate the algorithmic error at the cost of deeper circuits. Our benchmark shows that, within the limited physical error budget, the feasible advantage is confined to absolute errors well below the $10^{-2}$ scale, which vanishes under noise levels of current quantum hardware. In sharp contrast to the previous Trotter error mitigation methods, we introduce a constant-depth multi-product formula (cd-MPF) that suppresses the Trotter error by combining multiple circuits at fixed circuit depth. We identify an auxiliary parameter $α$, which reshapes the Trotter error terms while leaving the target evolution invariant. The classical linear combination of the measured expectation values cancels the leading $(Δt)^{2}$ algorithmic contribution and steepens the Trotter-error scaling with the two-qubit circuit depth $d$ from $d^{-2}$ to $d^{-4}$. Combined with physical-noise mitigation, our method can serve as a key ingredient for realizing long-time quantum dynamics simulation on near-term hardware.

quant-pharXiv:2607.12225•Jul 15, 2026•0 citations

Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems

Teague Tomesh, Kaiwen Gui, Pranav Gokhale +4 more

Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. These optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling in both basic and applied sciences.

arXiv:2203.12713•IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2021•3 citations

Trotter error mitigation by error profiling with shallow quantum circuit

Sangjin Lee, Young‐Seok Kim, Seungwoo Lee

Understanding the dynamics of quantum systems is crucial in many areas of physics, but simulating many-body systems presents significant challenges due to the large Hilbert space to navigate and the exponential growth of computational overhead. Quantum computers offer a promising platform to overcome these challenges, particularly for simulating the time evolution with Hamiltonians. Trotterization is a widely used approach among available algorithms in this regard, and well suited for near-term quantum devices. However, it introduces algorithmic Trotter errors due to the non-commutativity of Hamiltonian components. Several techniques such as multi-product formulas have been developed to mitigate Trotter errors, but often require deep quantum circuits, which can introduce additional physical errors. In this work, we propose a resource-efficient scheme to reduce the algorithmic Trotter error with relatively shallow circuit depth. We develop a profiling method by introducing an auxiliary parameter to estimate the error effects in expectation values, enabling significant error suppression with a fixed number of Trotter steps. Our approach offers an efficient way of quantum simulation on near-term quantum processors with shallow circuits.

arXiv:2503.09710•Mar 12, 2025•0 citations

Joint Mitigation of Algorithmic and Physical Errors in Noisy Hamiltonian Simulation

Shuo Zhou, Xinzhao Wang, Ruiqi Zhang +4 more

Product-formula Hamiltonian simulation is naturally suited to near-term quantum processors, but its accuracy is set by two competing errors: finite-step Trotter bias and physical hardware noise. We introduce a joint extrapolation strategy that ties the tunable per-layer noise strength to the Trotter step size, $λ(s)=c(sT)^{p+1}$ for a $p$-th order product formula. Along this one-dimensional path, the leading physical-noise and Trotter corrections over the full evolution both enter at order $s^p$ and can be canceled by a single Richardson extrapolation. Building on a previously established finite-order Baker--Campbell--Hausdorff truncation bound, we derive a provably commutator-scaling resource guarantee for the joint extrapolation. For local Hamiltonians with local Lindbladian noise, the protocol mitigates physical noise together with Trotter error with only a constant asymptotic overhead relative to noiseless Trotter extrapolation, provided the required noise strengths lie above the intrinsic device-noise floor. We experimentally demonstrate the protocol for Ising dynamics on a superconducting quantum computer using learned noise amplification. Complementary 100-qubit Sparse Pauli Dynamics (SPD) simulations achieve comparable accuracy to two-dimensional Richardson extrapolation with fewer circuit settings.

quant-pharXiv:2609.11508•Sep 11, 2026•0 citations

Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling

Qunsheng Huang, David Winderl, Arianne Meijer-van de Griend +1 more

In quantum computing, the efficient optimization of Pauli string decompositions is a crucial aspect for the compilation of quantum circuits for many applications, such as chemistry simulations and quantum machine learning. In this paper, we propose a novel algorithm for the synthesis of trotterized time-evolution operators that results in circuits with significantly fewer gates than previous solutions. Our synthesis procedure takes the qubit connectivity of a target quantum computer into account. As a result, the generated quantum circuit does not require routing, and no additional CNOT gates are needed to run the resulting circuit on a target device. We compare our algorithm against Paulihedral and TKET, and show a significant improvement for randomized circuits and different molecular ansatzes. We also investigate the Trotter error introduced by our ordering of the terms in the Hamiltonian versus default ordering and the ordering from the baseline methods and conclude that our method on average does not increase the Trotter error.

arXiv:2408.00354•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Mitigating algorithmic errors in a Hamiltonian simulation

Suguru Endo, Qi Zhao, Ying Li +2 more

Quantum computers can efficiently simulate many-body systems. As a widely used Hamiltonian simulation tool, the Trotter-Suzuki scheme splits the evolution into the number of Trotter steps $N$ and approximates the evolution of each step by a product of exponentials of each individual term of the total Hamiltonian. The algorithmic error due to the approximation can be reduced by increasing $N$, which however requires a longer circuit and hence inevitably introduces more physical errors. In this work, we first study such a trade-off and numerically find the optimal number of Trotter steps ${N}_{\mathrm{opt}}$ given a physical error model in a near-term quantum hardware. Practically, physical errors can be suppressed using recently proposed error mitigation methods. We then extend physical error mitigation methods to suppress the algorithmic error in Hamiltonian simulation. By exploiting the simulation results with different numbers of Trotter steps $N\ensuremath{\le}{N}_{\mathrm{opt}}$, we can infer the exact simulation result within a higher accuracy and hence mitigate algorithmic errors. We numerically test our scheme with a five-qubit system and show significant improvements in the simulation accuracy by applying both physical and algorithmic error mitigations.

arXiv:1808.03623•Physical Review A•Jan 18, 2019•72 citations
Digital simulation of quantum dynamics by evaluating the time evolution of a Hamiltonian is the initially proposed application of quantum computing. The large number of quantum gates required for emulating the complete second quantization form of the Hamiltonian, however, makes such an approach unsuitable for near-term devices with limited gate fidelities that cause high physical errors. In addition, Trotter error caused by noncommuting terms can accumulate and harm the overall circuit fidelity, thus causing algorithmic errors. In this paper, we propose a new term ordering strategy, max-commute-tsp (MCTSP), that simultaneously mitigates both algorithmic and physical errors. First, we improve the Trotter fidelity compared with previously proposed optimization by reordering Pauli terms and partitioning them into commuting families. We demonstrate the practicality of this method by constructing and evaluating quantum circuits that simulate different molecular Hamiltonians, together with theoretical explanations for the fidelity improvements from our term grouping method. Second, we describe a new gate cancellation technique that reduces the high gate counts by formulating the gate cancellation problem as a travelling salesperson problem, together with benchmarking experiments. Finally, we also provide benchmarking results that demonstrate the combined advantage of max-commute-tsp to mitigate both physical and algorithmic errors via quantum circuit simulation under realistic noise models.
Digital quantum simulation of many-body dynamics faces a tension between algorithmic Trotter error and physical noise that accumulates with circuit depth. Typical higher-order product formulas mitigate the algorithmic error at the cost of deeper circuits. Our benchmark shows that, within the limited physical error budget, the feasible advantage is confined to absolute errors well below the 10−210^{-2}10−2 scale, which vanishes under noise levels of current quantum hardware. In sharp contrast to the previous Trotter error mitigation methods, we introduce a constant-depth multi-product formula (cd-MPF) that suppresses the Trotter error by combining multiple circuits at fixed circuit depth. We identify an auxiliary parameter ααα, which reshapes the Trotter error terms while leaving the target evolution invariant. The classical linear combination of the measured expectation values cancels the leading (Δt)2(Δt)^{2}(Δt)2 algorithmic contribution and steepens the Trotter-error scaling with the two-qubit circuit depth ddd from d−2d^{-2}d−2 to d−4d^{-4}d−4. Combined with physical-noise mitigation, our method can serve as a key ingredient for realizing long-time quantum dynamics simulation on near-term hardware.
Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. These optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling in both basic and applied sciences.
Understanding the dynamics of quantum systems is crucial in many areas of physics, but simulating many-body systems presents significant challenges due to the large Hilbert space to navigate and the exponential growth of computational overhead. Quantum computers offer a promising platform to overcome these challenges, particularly for simulating the time evolution with Hamiltonians. Trotterization is a widely used approach among available algorithms in this regard, and well suited for near-term quantum devices. However, it introduces algorithmic Trotter errors due to the non-commutativity of Hamiltonian components. Several techniques such as multi-product formulas have been developed to mitigate Trotter errors, but often require deep quantum circuits, which can introduce additional physical errors. In this work, we propose a resource-efficient scheme to reduce the algorithmic Trotter error with relatively shallow circuit depth. We develop a profiling method by introducing an auxiliary parameter to estimate the error effects in expectation values, enabling significant error suppression with a fixed number of Trotter steps. Our approach offers an efficient way of quantum simulation on near-term quantum processors with shallow circuits.
Product-formula Hamiltonian simulation is naturally suited to near-term quantum processors, but its accuracy is set by two competing errors: finite-step Trotter bias and physical hardware noise. We introduce a joint extrapolation strategy that ties the tunable per-layer noise strength to the Trotter step size, λ(s)=c(sT)p+1λ(s)=c(sT)^{p+1}λ(s)=c(sT)p+1 for a ppp-th order product formula. Along this one-dimensional path, the leading physical-noise and Trotter corrections over the full evolution both enter at order sps^psp and can be canceled by a single Richardson extrapolation. Building on a previously established finite-order Baker--Campbell--Hausdorff truncation bound, we derive a provably commutator-scaling resource guarantee for the joint extrapolation. For local Hamiltonians with local Lindbladian noise, the protocol mitigates physical noise together with Trotter error with only a constant asymptotic overhead relative to noiseless Trotter extrapolation, provided the required noise strengths lie above the intrinsic device-noise floor. We experimentally demonstrate the protocol for Ising dynamics on a superconducting quantum computer using learned noise amplification. Complementary 100-qubit Sparse Pauli Dynamics (SPD) simulations achieve comparable accuracy to two-dimensional Richardson extrapolation with fewer circuit settings.
In quantum computing, the efficient optimization of Pauli string decompositions is a crucial aspect for the compilation of quantum circuits for many applications, such as chemistry simulations and quantum machine learning. In this paper, we propose a novel algorithm for the synthesis of trotterized time-evolution operators that results in circuits with significantly fewer gates than previous solutions. Our synthesis procedure takes the qubit connectivity of a target quantum computer into account. As a result, the generated quantum circuit does not require routing, and no additional CNOT gates are needed to run the resulting circuit on a target device. We compare our algorithm against Paulihedral and TKET, and show a significant improvement for randomized circuits and different molecular ansatzes. We also investigate the Trotter error introduced by our ordering of the terms in the Hamiltonian versus default ordering and the ordering from the baseline methods and conclude that our method on average does not increase the Trotter error.
Quantum computers can efficiently simulate many-body systems. As a widely used Hamiltonian simulation tool, the Trotter-Suzuki scheme splits the evolution into the number of Trotter steps NNN and approximates the evolution of each step by a product of exponentials of each individual term of the total Hamiltonian. The algorithmic error due to the approximation can be reduced by increasing NNN, which however requires a longer circuit and hence inevitably introduces more physical errors. In this work, we first study such a trade-off and numerically find the optimal number of Trotter steps Nopt{N}_{\mathrm{opt}}Nopt​ given a physical error model in a near-term quantum hardware. Practically, physical errors can be suppressed using recently proposed error mitigation methods. We then extend physical error mitigation methods to suppress the algorithmic error in Hamiltonian simulation. By exploiting the simulation results with different numbers of Trotter steps $N\ensuremath{\le}{N}_{\mathrm{opt}}$, we can infer the exact simulation result within a higher accuracy and hence mitigate algorithmic errors. We numerically test our scheme with a five-qubit system and show significant improvements in the simulation accuracy by applying both physical and algorithmic error mitigations.