Zero-Overhead Cancellation of the Leading Trotter Error via Commutator-Graph Scheduling

Abstract

A quantum computer is a stochastic device: the Born rule returns one bitstring per run, so every quantity a simulation reports is a statistical estimate whose structure is governed by the algebra of the operators being evolved. We introduce commutator-graph scheduling (CGS), which doubles the convergence order of first-order Trotterization at zero gate, qubit, or depth overhead by making the leading error an explicit, estimable operator on that algebra. We recast the leading Trotter error as an exact, matrix-free operator—the commutator error form $E_\pi=\sum_{aschedule: a step-alternating antithetic schedule cancels $E_\pi$ and converges at $O(t^3/r^2)$ with the identical $L\!\cdot\!r$ rotations. Across 144 structured Hamiltonians against exact statevector references, CGS lifts the empirical rate from 1.96 to 4.07, reaches fidelity $0.99$ with 1.40× fewer rotations, and attains $0.999$ where first-order Trotter cannot. A matrix-free Krylov reference extends the exact benchmark to 14 qubits, where the order doubling is size-independent and the matched-cost speedup reaches 2.06×. An interpretable scheduler over ten graph features selects the gate-optimal schedule per instance with 93% leave-one-out accuracy.

Background and Motivation

The free parameter in first-order Trotterization is not the ordering but the schedule; the commutator graph tells us why ordering fails and how to schedule instead.

Simulating the time evolution $e^{-\mathrm{i}Ht}$ of a quantum many-body Hamiltonian is the founding application of quantum computers (Feynman 1982; Lloyd 1996), and the product formula remains its dominant primitive. Given a Hamiltonian in Pauli form $H=\sum_{j=1}^{L} c_j P_j$, the first-order (Lie–Trotter) approximant with $r$ steps and term ordering $\pi$ is $U_{\mathrm{Trot}}(\pi)=\big(\prod_{j\in\pi} e^{-\mathrm{i}\,c_j P_j\, t/r}\big)^{r}$. Its deviation from the exact propagator is governed by the commutators of the summands, made tight and explicit by the modern commutator-scaling analysis (Childs et al., Theory of Trotter Error with Commutator Scaling, 2021), the theoretical anchor of this work.

The cost of a first-order schedule is exactly one rotation $e^{-\mathrm{i}c_j P_j t/r}$ per term per step, so the gate count $L\!\cdot\!r$ is independent of the ordering $\pi$, and indeed of whether that ordering varies between steps. A substantial empirical literature has asked how much reordering buys (Tranter 2019; Poulin 2015; Hastings 2015), repeatedly finding the effect modest. This work explains that ceiling and then circumvents it: we show that the ceiling is a theorem about orderings, and that the larger free object—the per-step schedule—escapes it at no additional gate cost.

The natural structure for this question is the commutator graph (or anticommutation graph): one node per term, with an edge between every pair of terms that anticommute. This is the same graph used in measurement grouping for variational algorithms, where a clique cover into mutually commuting sets reduces the number of measurement settings (Verteletskyi 2020; Gokhale 2020; Crawford 2021). Despite this rich structure, the empirical verdict on ordering has been consistently underwhelming, with reordering gains widely regarded as “within noise”; why a free parameter should be so impotent had not previously been explained. Our resolution is to enlarge the free degree of freedom from a single ordering to a per-step schedule $\sigma=(\pi_1,\dots,\pi_r)$, realized at the identical $L\!\cdot\!r$ rotation count. The antithetic schedule—alternating a term order with its reverse on successive steps—makes each adjacent step-pair a palindromic, symmetric product formula whose leading commutator error vanishes. The underlying mechanism is the classical symmetrization of Suzuki (Suzuki 1991; Hatano 2005); its reading as a zero-overhead scheduling choice that a single fixed ordering can never realize is, to our knowledge, new.

The Ordering–Scheduling Dichotomy

A single ordering only re-signs the leading error; a step-alternating schedule cancels it. The commutator graph certifies both halves.

Reordering re-signs — impotence

The leading first-order error operator is the commutator error form $E_\pi=\sum_{a

$$E_\pi=\sum_{\{j,k\}\in E(\mathcal{G})}\varepsilon_{jk}(\pi)\,2c_jc_k\,(P_jP_k),$$

$\varepsilon_{jk}=\pm1$ according to which term precedes the other. Reordering only flips these signs. When the edge products $P_jP_k$ are distinct, the Hilbert–Schmidt norm of $E_\pi$ is identical for every ordering; reordering cannot reduce the error.

Alternating cancels — the free upgrade

Let the schedule apply $\pi$ on even steps and its reverse $\pi^{R}$ on odd steps. Each step-pair $S_{\pi^R}(\Delta)\,S_\pi(\Delta)$ is a palindrome, hence a symmetric formula whose generator has only odd powers of $\Delta=t/r$:

$$S_{\pi^R}(\Delta)\,S_\pi(\Delta)=\exp\!\big(-2\mathrm{i}\Delta H+O(\Delta^3)\big).$$

The leading $O(\Delta^2)$ commutator error cancels exactly, lifting the convergence from $O(t^2/r)$ to $O(t^3/r^2)$ at exactly the same $L\!\cdot\!r$ rotations the first-order schedule uses.

Principal Contributions

The commutator error form, matrix-free and certified. The exact leading-order error operator $E_\pi=\sum_{a
An ordering-impotence theorem. Reordering only re-signs $E_\pi$; its Hilbert–Schmidt norm is exactly ordering-invariant when the edge commutators are distinct, and only a small colliding fraction is ordering-reducible otherwise. Across the 144 instances a median ordering sits within a factor 1.097 of the exact floor. No fixed ordering escapes the first-order rate—the precise form of the “ordering is within noise” folklore.
A free second-order schedule. The antithetic schedule cancels $E_\pi$ and converges at second order at the identical gate budget; combined with the commuting-clique compression of the graph it reaches fidelity $0.99$ at 1.40× fewer rotations and reaches $0.999$ where first-order Trotter does not.
A quantitative theory of the residual. A self-contained Baker–Campbell–Hausdorff / Magnus remainder bounds the post-cancellation error in operator norm; leading-cancellation is proved strictly more accurate than every fixed ordering at fine step size; residual minimization is placed in an NP-hard landscape with a spectral relaxation; and an unbiased shot-based estimator with a finite-sample confidence interval makes the accuracy claim empirically certifiable, not merely asymptotic.
Size-independent verification. A matrix-free Krylov reference extends the exact benchmark from the dense-exponential ceiling to 14 qubits; the order doubling (first-order rate $\approx2$, antithetic rate $\approx4$) and the matched-cost speedup (2.06× at $n=14$) are size-independent.
A learned schedule router. An interpretable logistic-regression router over ten listing-order-invariant commutator-graph features selects the gate-optimal schedule per instance with 93% leave-one-instance-out accuracy, recovering near-oracle gate efficiency by folding only the instances that need it.

Theoretical Guarantees

Each statement is proved in full in the Methods; every proof is matrix-free and exact.

Proposition — Rotation-count invariance

A first-order schedule with any ordering $\pi$, and the antithetic schedule that alternates $\pi$ with its reverse, each apply exactly $L\!\cdot\!r$ single-Pauli rotations.

The antithetic schedule is genuinely free: it spends not a single extra gate over the first-order schedule, so any accuracy it recovers is pure profit.

Theorem 1 — Ordering impotence

Reordering acts on $E_\pi$ only by flipping the signs $\varepsilon_{jk}$. Grouping by Pauli string, $\lVert E_\pi\rVert_{\mathrm{HS}}^2=2^n\sum_R(\sum_{\{j,k\}:R_{jk}=R}\varepsilon_{jk}\,2c_jc_k\widehat\omega_{jk})^2$; if every edge maps to a distinct Pauli string then $\lVert E_\pi\rVert_{\mathrm{HS}}$ is independent of $\pi$, and in general only the colliding fraction is ordering-reducible.

On the transverse-field Ising and Heisenberg families the leading error is fully ordering-invariant; reordering cannot move it, which is why ordering heuristics are statistically indistinguishable.

Theorem 2 — Antithetic cancellation and the free order upgrade

The antithetic step-pair $M(\Delta)=S_{\pi^R}(\Delta)S_\pi(\Delta)$ is symmetric, $M(-\Delta)=M(\Delta)^{-1}$, so its generator contains only odd powers of $\Delta$ and the leading $O(\Delta^2)$ error cancels: $M(\Delta)=\exp(-2\mathrm{i}\Delta H+O(\Delta^3))$. The antithetic schedule therefore approximates $e^{-\mathrm{i}tH}$ with additive error $O(t^3/r^2)$ at exactly $L\!\cdot\!r$ rotations.

A per-step ordering choice that a single fixed ordering cannot realize upgrades the convergence order for free.

Proposition — Clique exactness

A proper colouring of $\mathcal{G}(H)$ partitions the terms into commuting cliques; laying a clique contiguously, its rotations factor exactly, $\prod_{j\in C}e^{-\mathrm{i}\Delta h_j}=\exp(-\mathrm{i}\Delta\sum_{j\in C}h_j)$, so the schedule error depends only on inter-clique commutators.

Low-chromatic (fast-forwardable) Hamiltonians such as Heisenberg are near-exact already at first order, so folding only adds overhead there—the decision the learned router makes.

Empirical Validation

Across 144 structured instances (transverse-field Ising, Heisenberg, random molecular-like; $n\in\{4,6,8,10,12,14\}$ qubits; eight seeded draws each) against exact statevector references. Every value is generated by the package and transcribed from results/summary.json.

Matched-cost snapshot at a reference budget

At $r=6$ Trotter steps ($t=1.0$), a mean of 118 rotations. The first-order schedules share this identical budget; the antithetic fold matches it and still reaches higher fidelity. “rate $p$” is the fitted convergence exponent (mean per-instance log–log slope of infidelity vs. $r$).

schedule	order	fidelity	rotations	rate $p$
best first-order ordering	1st	0.9403	118	1.96
antithetic (2nd, free)	2nd	0.9589	118	4.07
symmetric (2nd, Strang)	2nd	—	—	4.03

At the identical 118-rotation budget the antithetic schedule reaches mean fidelity 0.9589 against 0.9403 for the best first-order ordering—a reduction of mean infidelity from 0.0597 to 0.0411 (a factor 1.5), for free. The rate column shows the same effect as a convergence exponent: $\approx2$ for every first-order schedule and $\approx4$ for both folds—a clean doubling of the convergence order.

Rotations to a target fidelity matched-cost efficiency

Realised rotation count at which the mean fidelity over the 144 instances first reaches each target; “—” marks a target not reached within the swept step grid.

schedule	$F\!\ge\!0.99$	$F\!\ge\!0.999$
best first-order ordering	315	—
antithetic (2nd, free)	236	315
symmetric (2nd, Strang)	225	300

To reach fidelity 0.99 the best first-order ordering needs 315 rotations, the antithetic schedule 236 and the symmetric schedule 225—a 1.40× reduction. To reach 0.999, no first-order schedule succeeds within the swept budget, while the antithetic and symmetric schedules reach it at 315 and 300 rotations. Because the convergence rates differ, the matched-cost gap widens with budget.

Size independence via a matrix-free Krylov reference

A dense matrix exponential is tractable only to modest $n$. A matrix-free Krylov reference, cross-checked against dense expm to $10^{-9}$, extends the exact benchmark to $n=14$ qubits. Across $n\in\{4,\dots,14\}$ the fitted rates stay at $\approx1.94$ (first-order) and $\approx4.06$ (antithetic), so the order doubling is size-independent, and the matched-cost speedup reaches 2.06× at $n=14$.

Ordering is impotent; folding is learnable

Sampling orderings per instance and forming the exact leading-error spectral norm, a median ordering sits within a factor 1.097 of the per-instance minimum and the coefficient ordering within 1.074; the fully matrix-free Hilbert–Schmidt surrogate moves within 1.004, and the worst single instance reaches only 1.92. On the transverse-field Ising and Heisenberg families every anticommuting edge maps to a distinct Pauli string, so the leading error is exactly ordering-invariant; only the dense molecular-like family has any ordering-reducible part (0.98 invariant). The interpretable router exploits exactly this structure: trained leave-one-instance-out it attains 93% accuracy against the per-instance oracle and recovers near-oracle gate efficiency—on the 92 instances where every fixed schedule reaches the target it needs 114.0 rotations on average against the oracle's 112.4—routing fast-forwardable instances to the cheap first-order schedule and hard instances to a fold.

Interactive Convergence Demonstration

A self-contained, client-side statevector simulation that reproduces the paper's central figure in real time: first-order schedules collapse onto a single $\propto r^{-2}$ line (the visual proof of impotence), while the antithetic schedule—at the identical rotation count—follows $\propto r^{-4}$. It illustrates the proven behaviour on single instances; it is not a re-run of the 144-instance benchmark.

Hamiltonian family

Qubits $n$ 5 Evolution time $t$ 1.0 Schedule highlighted

—first-order rate $p$ ($\to 2$)

—antithetic rate $p$ ($\to 4$)

—rotations to $F\!\ge\!0.99$, first-order

—rotations to $F\!\ge\!0.99$, antithetic

Infidelity $1-\mathcal{F}$ (log) against Trotter steps $r$ (log), computed in-browser from the exact rotation $e^{-\mathrm{i}\theta P}=\cos\theta\,I-\mathrm{i}\sin\theta\,P$ against a converged symmetric reference. The three first-order schedules (cool, dashed) lie on top of one another at slope $\approx 2$—reordering does not move the curve—while the antithetic fold (vermillion), using the identical rotation count at each $r$, and the symmetric fold (green) follow slope $\approx 4$. Guides $\propto r^{-2}$ and $\propto r^{-4}$ are shown.

Significance and Boundaries

Why a matched-cost schedule matters, with the study's limits held in full view.

For first-order formulas the schedule is genuinely free—it changes no gate, qubit, or depth count—so the difference between an $O(t^2/r)$ and an $O(t^3/r^2)$ method at fixed cost is the difference between reaching and not reaching a target, as the unreachable $0.999$ column above shows. The commutator graph supplies both halves of the recommendation at no extra cost: it certifies when ordering cannot help, and its clique colouring tells the learned router which instances to fold and which to leave alone. The mechanism, palindromic symmetrization, is classical (Suzuki 1991); the contribution is the framing—that the lever is the schedule, that a fixed ordering provably cannot realize it—together with the matched-cost quantification and the learned selector.

The boundaries are stated, not omitted. (i) The second-order advantage is a small-step-size effect with an honest crossover: at coarse steps the antithetic fold can be worse than a good first-order ordering. (ii) Systems are bounded ($n\le 14$) because an exact statevector or Krylov reference must be formed; the convergence-rate argument is, however, size-independent. (iii) Families are synthetic/structured proxies, not production-mapped molecular Hamiltonians. (iv) Cost is the realised rotation count, ignoring rotation synthesis and connectivity. (v) All results are classical CPU statevector simulations with no hardware validation, single-author. What is offered is a clean, reproducible characterization of a free, second-order schedule and a proof that a single ordering cannot match it—not a claim of hardware advantage.

Reproducibility

A pip-installable artifact and an audited path from a clean checkout to the identical numbers.

The package (pip distribution specops-cgs, import name topoham; CPU-only; numpy / scipy / networkx / scikit-learn / matplotlib) lives at submission/code behind a single end-to-end entry point. Every reported number flows from one authoritative artifact, results/summary.json, and is generated into LaTeX macros and table fragments that the manuscript inputs directly. Three integrity gates enforce the discipline before any number is emitted: the fast Pauli-rotation kernel is cross-checked against dense scipy.linalg.expm to $10^{-9}$; the matrix-free commutator error form is cross-checked against the dense pair-commutator sum to $10^{-9}$; and the matrix-free Krylov reference is cross-checked against dense expm to $10^{-9}$.

# From submission/code
pip install specops-cgs   # or: pip install .  (CPU-only)
make test                 # Pauli kernel (1e-9), error-form (1e-9), antithetic 2nd-order, clique exactness
export KMP_DUPLICATE_LIB_OK=TRUE
cgs-reproduce --config configs/full.yaml   # summary.json, macros, tables, figures
make audit                # readiness gate: traceable numbers, integrity flags, no forbidden claims

The run is fully determined by seeded draws; the reported scale (configs/full.yaml) is 144 instances across three families and six sizes $n\in\{4,6,8,10,12,14\}$ with eight seeds each, time $t=1.0$, step grid $\{1,2,4,6,8,12,16,24\}$, using the matrix-free Krylov reference backend. Runtime and memory are logged per benchmark, and all experiments run on commodity CPU hardware. The interactive demonstration above re-implements the same exact single-Pauli rotation in vanilla JavaScript, so the math on this page matches the math in the package.

Cite this work

If you use this software or its results, please cite the manuscript.

% BibTeX
@article{huynh2026topoham,
  title   = {Zero-Overhead Cancellation of the Leading Trotter Error via Commutator-Graph Scheduling},
  author  = {Huynh, Molena},
  year    = {2026},
  note    = {Part of the spectral-truncation operators (SpecOps) program},
}

Related Work and References

The theoretical anchor of this work is the commutator-scaling analysis of Trotter error by Childs, Su, Tran, Wiebe, and Zhu (Theory of Trotter Error with Commutator Scaling, 2021); the antithetic upgrade is the classical Suzuki–Hatano product-formula symmetrization (Suzuki 1991; Hatano and Suzuki 2005) reframed as a free per-step schedule. The empirical ceiling we explain is documented in the ordering literature for electronic-structure simulation (Tranter, Love, Mintert, and Wiebe 2019; Poulin et al. 2015; Hastings et al. 2015), and the commutator graph itself is borrowed from measurement grouping in variational algorithms (Verteletskyi, Yen, and Izmaylov 2020; Gokhale et al. 2020). The full bibliography of the manuscript follows.

R. P. Feynman. “Simulating physics with computers.” International Journal of Theoretical Physics 1982. doi:10.1007/BF02650179
S. Lloyd. “Universal quantum simulators.” Science 1996. doi:10.1126/science.273.5278.1073
H. F. Trotter. “On the product of semi-groups of operators.” Proceedings of the American Mathematical Society 1959. doi:10.1090/S0002-9939-1959-0108732-6
M. Suzuki. “General theory of fractal path integrals with applications to many-body theories and statistical physics.” Journal of Mathematical Physics 1991. doi:10.1063/1.529425
A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. “Theory of Trotter error with commutator scaling.” Physical Review X 2021. doi:10.1103/PhysRevX.11.011020
A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. “Toward the first quantum simulation with quantum speedup.” Proceedings of the National Academy of Sciences 2018. doi:10.1073/pnas.1801723115
N. Hatano and M. Suzuki. “Finding exponential product formulas of higher orders.” Lecture Notes in Physics 2005. doi:10.1007/11526216_2
A. M. Childs, A. Ostrander, and Y. Su. “Faster quantum simulation by randomization.” Quantum 2019. doi:10.22331/q-2019-09-02-182
E. Campbell. “Random compiler for fast Hamiltonian simulation.” Physical Review Letters 2019. doi:10.1103/PhysRevLett.123.070503
D. Poulin, M. B. Hastings, D. Wecker, N. Wiebe, A. C. Doherty, and M. Troyer. “The Trotter step size required for accurate quantum simulation of quantum chemistry.” Quantum Information & Computation 2015.
M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer. “Improving quantum algorithms for quantum chemistry.” Quantum Information & Computation 2015.
V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov. “Measurement optimization in the variational quantum eigensolver using a minimum clique cover.” The Journal of Chemical Physics 2020. doi:10.1063/1.5141458
P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, and F. T. Chong. “$O(N^3)$ measurement cost for variational quantum eigensolver on molecular Hamiltonians.” IEEE Transactions on Quantum Engineering 2020. doi:10.1109/TQE.2020.3035814
O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley. “Efficient quantum measurement of Pauli operators in the presence of finite sampling error.” Quantum 2021. doi:10.22331/q-2021-01-20-385
A. Tranter, P. J. Love, F. Mintert, and N. Wiebe. “Ordering of Trotterization: Impact on errors in quantum simulation of electronic structure.” Entropy 2019. doi:10.3390/e21121218
F. Pedregosa, G. Varoquaux, A. Gramfort, et al. “Scikit-learn: Machine learning in Python.” Journal of Machine Learning Research 2011.
S. B. Bravyi and A. Yu. Kitaev. “Fermionic quantum computation.” Annals of Physics 2002. doi:10.1006/aphy.2002.6254
J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik. “Simulation of electronic structure Hamiltonians using quantum computers.” Molecular Physics 2011. doi:10.1080/00268976.2011.552441
C. R. Harris, K. J. Millman, S. J. van der Walt, et al. “Array programming with NumPy.” Nature 2020. doi:10.1038/s41586-020-2649-2
P. Virtanen, R. Gommers, T. E. Oliphant, et al. “SciPy 1.0: fundamental algorithms for scientific computing in Python.” Nature Methods 2020. doi:10.1038/s41592-019-0686-2
A. A. Hagberg, D. A. Schult, and P. J. Swart. “Exploring network structure, dynamics, and function using NetworkX.” Proceedings of the 7th Python in Science Conference 2008.