Toward the first quantum simulation with quantum speedup

• The work develops explicit circuits and concrete resource estimates for practical quantum computations that could outperform classical computers.This is intended to identify applications for small quantum computers and motivate investment in scalable, fault-tolerant machines.Source: §1 · p. 1
• Unlike quantum computational supremacy, the goal is to identify minimal, practical examples of super-classical quantum computation rather than merely accomplish a super-classical task.The authors distinguish their aim from prior circuit-compilation studies, which generally reported high resource counts.Source: §1 · pp. 1–2
• The study focuses on digital simulation of quantum spin systems with local interactions because these systems likely have lower overhead while retaining flexibility and prospects for fault tolerance.Quantum simulation is presented as a natural application, alongside possible applications to fermionic lattice models [77], quantum chemistry [76], and quantum field theories [40].Source: §1 · p. 2
• The authors test whether recently improved quantum-dynamics algorithms [11, 12, 14, 51, 52] can benefit relatively small systems and help establish a first practical quantum-computing application.Efficient quantum-dynamics simulation algorithms have been known for over two decades, with newer work improving asymptotic performance in evolution time and allowed simulation error.Source: §1 · p. 2

Target system

• The target system is a one-dimensional nearest-neighbor Heisenberg model with a uniformly random magnetic field in the z direction.Periodic boundary conditions apply, and h controls the disorder strength.Source: §2 · p. 2

Motivation

• The model’s thermal-to-localized transition remains poorly understood, while classical numerical studies have reached at most 22 spins [54].The Hamiltonian has been studied in connection with self-thermalization and many-body localization.Source: §2 · p. 2

Simulation task

• The study focuses on simulation cost because simple state preparations and measurements suffice for proposed self-thermalization experiments [67, 68, 70].Evolution times comparable to the number of spins are required for self-thermalization or information propagation under the Lieb-Robinson bound.Source: §2 · p. 2

Benchmark parameters

• Gate counts use h = 1, evolution time t = n, and overall accuracy ϵ = 10^-3 to emphasize system-size dependence.These choices address a key practical consideration that has been deemphasized in sparse Hamiltonian simulation literature.Source: §2 · p. 2

3 Implementations

• The implementations target high-order product formulas [11], Taylor series [14], and quantum signal processing [51], using Quipper, manual tightening, and automated circuit optimization.The circuits are publicly available, and quantum-walk approaches are expected to incur greater overhead.Source: §3 · p. 3

3.1 Product formula algorithm

• For one-dimensional nearest-neighbor systems with t = n, commutator bounds reduce (2k)th-order product-formula complexity from O(n3+1/k) to O(n3+2/(2k+1)) with a smaller leading constant.The bound exploits Hamiltonian commutation relations, while empirical error estimates can reduce practical costs by several orders of magnitude without rigorous guarantees.Source: §3.1 · pp. 3–4

3.2 Taylor series algorithm

• An optimized binary-tree implementation of select(V) saves about log2 Γ in gate count, reducing cnot and T counts by factors of 5–9 for 10–100 spins.The implementation also meets a previously established asymptotic lower bound [56] and retains rigorous, non-asymptotic simulation-error analysis.Source: §3.2 · p. 4

3.3 Quantum signal processing algorithm

• QSP parameter synthesis requires high-precision roots of a degree-2M polynomial, so complete circuits were feasible only for small instances; segmentation enables implementation but increases asymptotic complexity.The full version uses an empirical Jacobi–Anger error bound, whereas the segmented version uses an analytic bound to remain rigorous.Source: §3.3 · pp. 4–5

Resource requirements

• TS requires significantly more qubits and gates than QSP, while QSP requires only slightly more qubits than PF.These comparisons are summarized by the gate-count and qubit-count figures.Source: §4 · p. 5, Figure 2 · p. 6

Algorithm comparison

• About an order of magnitude fewer CNOTs and almost two orders fewer T gates make segmented QSP the best rigorously analyzed approach.Empirical PF improves by two to three orders of magnitude and is preferred when rigorous guarantees are unnecessary, especially because it uses fewer qubits.Source: §4 · pp. 5–6

Product formulas

• Fourth- and sixth-order PF formulas perform best for systems with tens to hundreds of qubits, with empirical sixth-order PF overtaking fourth-order PF at about 30 qubits.The fourth-order commutator-bound formula is the best rigorous PF method; higher-order formulas may also benefit quantum-chemistry simulations [62] [64].Source: §4 · p. 6, Figure 3 · p. 6

50-qubit benchmark

• 1.8 × 10^8 CNOTs and 2.4 × 10^9 T gates make segmented QSP the rigorous 50-qubit winner, whereas empirical PF uses about 3 × 10^6 CNOTs and 1.8 × 10^8 T gates.At 50 qubits, TS uses 171 qubits, QSP 67, and PF 50.Source: §4 · p. 6

Comparison with other applications

• Spin-system simulation uses far fewer resources than estimated classically hard instances of factoring and FeMoco quantum chemistry, including 5.7 × 10^9 T gates for 1024-bit factoring and 1.0 × 10^14 T gates for FeMoco.The factoring estimate uses 3132 qubits [47], while FeMoco uses 111 qubits [64].Source: §4 · p. 7

• The study establishes concrete benchmarks for superclassical quantum simulation, but these remain upper bounds that future algorithms and implementations may improve.Further optimization or an alternative algorithm or computational task could yield better performance.Source: §5 · p. 7
• Higher-order product formulas are useful even for small quantum simulations, motivating near-term experiments to test their empirical error bounds.Prior digital demonstrations mainly used first-order formulas, with only limited second-order applications [6] [19] [48].Source: §5 · p. 7
• Stronger rigorous product-formula error bounds and more efficient classical procedures for computing QSP angles are key algorithmic improvement targets.The newly developed commutator bound still produces very loose rigorous bounds, while QSP angle computation limits practical performance.Source: §5 · p. 7
• Millions of CNOT gates are currently estimated for a superclassical simulation, making fault-tolerance-free execution out of reach, though further reductions could change this.Highly accurate gates might eventually enable an early demonstration without error correction.Source: §5 · p. 7
• Future work must incorporate architectural constraints, alternative basic operations, gate parallelization, and likely fault tolerance to approach a practical quantum computation.The present analysis considers an idealized system and aims to provide a blueprint for the first practical quantum computation.Source: §5 · p. 7

A Related work

• Quantum simulation has progressed from Feynman’s proposal to algorithms and resource estimates spanning Hamiltonian dynamics, quantum chemistry, and other quantum systems.Prior circuit-compilation studies, including the QCS program, generally did not target minimal super-classical computations, while spin-model simulation may require fewer resources than factoring or quantum chemistry.Source: A Related work · p. 10

B Self-thermalization in spin models

• Classical simulation is limited to fewer than 25 qubits, motivating a one-dimensional random-field Heisenberg model whose localization transition could be studied at larger scale.The most extensive cited numerical study reached at most 22 spins [54]. The proposed benchmarks use product-state quenches, standard-basis measurements, and observables such as Hamming distance or even–odd imbalance.Source: B Self-thermalization in spin models · p. 11

C Simulation algorithms

• The appendix compares product formulas, direct Taylor-series implementation, and quantum signal processing for approximating exp(−iHt) within error ǫ for Pauli-term Hamiltonians.The target Hamiltonian is a sum of L positive-coefficient terms, each acting nontrivially on at most two qubits; negative evolution times can be absorbed into the Hamiltonian sign.Source: C Simulation algorithms · pp. 11–12

C.1 Product formula algorithm

• For the target n-qubit system, higher-order product formulas have gate complexity O(n^(3+1/k)), while commutator bounds improve this to O(n^(3+2/(2k+1))).The commutator bound exploits commuting term pairs and can be computed in closed form for the target Hamiltonian, whereas empirical bounds are non-rigorous extrapolations from small classical instances.Source: §C.1 · p. 13

C.2 Taylor series algorithm

• The Taylor-series algorithm implements truncated short-time evolutions as a linear combination of unitaries, repeats segments, and boosts the desired ancilla amplitude through isometries and rotations.Its implementation succeeds probabilistically because it requires an ancilla measurement; the appendix accounts for this overhead when comparing it fairly with product formulas.Source: §C.2 · pp. 13–15
• For the 2-local target Hamiltonian, the Taylor-series gate count tightens to O(n^3 log^2 n log log n), improving on the general bound O(n^4 log n log log n).The general analysis allows Pauli terms acting on all qubits, whereas the target’s 2-local structure yields the tighter asymptotic bound.Source: §C.2 · p. 15
• A binary-tree implementation of select(V) reduces its gate complexity from O(Γ log Γ) to O(Γ), but empirical Taylor-series error bounds provide no significant improvement.Direct classical simulation of the Taylor-series ancilla register is infeasible even for very small system sizes, limiting empirical error estimation.Source: §C.2 · p. 15

Algorithm

• QSP [51, 52] uses qubitization to map Hamiltonian eigenvalues to eigenphases, then applies phased iterates whose ancilla action is an SU(2) rotation.For eigenvalues λ ∈ (−1, 1), each Hamiltonian eigenvalue corresponds to two eigenvalues of −iQ, while unreachable eigenspaces can be neglected.Source: §C.3 · pp. 16–17

Approximation and preprocessing

• The algorithm approximates e^(−iλt) by truncating a Jacobi–Anger expansion to polynomial degree M, with phases computed classically from polynomial roots.The truncation provides a stated error bound, while computing the required angles involves finding roots of a degree-2M polynomial to high precision.Source: §C.3 · pp. 17–18

Post-selection

• QSP post-selects the ancilla on |+⟩⊗|G⟩; successful measurement produces a state close to e^(−iHt)|ψ⟩, while other outcomes fail.The success probability is analyzed separately to enable comparison with deterministic product-formula methods.Source: §C.3 · p. 17

Implementation and empirical performance

• The improved phased-iterate definition saves O(n^2 log n) gates overall, while the unsegmented implementation has asymptotic complexity O(n^3 log n), reduced to O(n^3) with improved select(H).Empirical bounds offer only a small gate-count reduction, and QSP performance was not significantly improved for systems of size 5 to 9 at ε = 10^−3.Source: §C.3 · pp. 17–18

Segmented implementation

• With M = 28, the segmented QSP implementation has gate complexity O(n^3.14) for the studied Hamiltonian-simulation instance.The general segmented complexity is O(n^(3+4/M)) under t = n and α = O(n).Source: §C.3 · p. 18

D System-size dependence for other simulation algorithms

• The appendix also derives system-size-dependent gate complexities for fractional-query and linear-combination-of-quantum-walk-steps algorithms.For the fractional-query analysis, L = Θ(n) and ∥H∥max = Θ(n); for the linear-combination approach, d = Θ(n).Source: D System-size dependence for other… · p. 18
• The quantum-walk algorithm uses phase estimation, O(d∥H∥maxt) lazy-walk steps, and a second phase estimate to correct the phase.The first phase estimate has one bit of precision, while the final estimate uses O(d∥H∥maxt) walk-operator applications.Source: D System-size dependence for other… · pp. 18–19
• The quantum-walk procedure uses O(n^3) walk steps, which dominate the phase-estimation Fourier transform and coherent sine-correction costs.The Fourier transform has complexity O(log n log log n), while sine correction is poly(log n).Source: D System-size dependence for other… · p. 19
• The walk operator can be implemented with O(n log n) gate complexity for O_F and O(n) complexity for O_H.O_F prepares and uncomputes the adjacent-bit-swap index, while O_H computes diagonal and off-diagonal Hamiltonian elements in O(n) time.Source: D System-size dependence for other… · p. 20
• O(n^4) gate complexity is achieved for quantum-walk simulation using the improved O(n) implementation of O_F.The earlier implementation gave O(n^4 log n), while the improved select-gate construction reduces this to O(n^4).Source: D System-size dependence for other… · p. 20

E Circuit synthesis and optimization

• For the implemented algorithms, Quipper provides high-level combinators and hierarchical circuit structure for concise specification and manipulation of very large circuits.The implementations, sample output circuits, and optimized versions are available in a public repository.Source: E Circuit synthesis and optimization · p. 20

E.1.1 Product formulas

• Product-formula implementations span orders 1, 2, 4, 6, and 8, with 18 algorithm types combining analytic, minimized, empirical, and selected commutator error bounds.Each algorithm exponentiates 1- or 2-qubit Pauli terms in a repeated, error-controlled sequence.Source: §E.1.1 · pp. 20–21

E.1.2 Taylor series

• The Taylor-series implementation uses mixed unary-binary control encoding, two state-preparation routines, select(V), and a multiply-controlled-Z reflection.The second state-preparation routine uses a specialized controlled-rotation construction [14], while generic coefficient preparation follows [69].Source: §E.1.2 · p. 21

E.1.3 Quantum signal processing

• The two QSP implementations differ in computability: non-segmented QSP uses random placeholder angles for gate counts, whereas segmented QSP computes rigorous parameters offline in Mathematica.The non-segmented circuits have correct structure but do not implement the desired unitary; segmented circuits are limited to sizes represented in lookup tables [26].Source: §E.1.3 · p. 21

E.2 Gate counts and synthesis

• Resource estimates are reported in Clifford+Rz and Clifford+T bases, with arbitrary z-rotations approximated using the optimal Ross–Selinger algorithm [66].The synthesis builds on exact synthesis by Kliuchnikov, Maslov, and Mosca.Source: §E.2 · pp. 21–22
• Repeat-until-success synthesis, unitary mixing, and Rz(π/6) distillation are projected to improve fault-tolerant resource counts by a factor of 5 or more, but remain future work.These methods trade lower T-counts for measurements, classical feedback, additional CNOT gates, or alternative distillation resources [16] [18] [29].Source: §E.2 · p. 22
• Non-segmented QSP Clifford+T counts are approximate because randomly selected angles replace unavailable exact angles, although many rotations make typical costs representative.The approximation cost is roughly 3 log(1/τ), and the total error budget is split evenly between simulation and synthesis errors.Source: §E.2 · p. 22

E.3 Optimization

• The automated optimizer reduces gate counts through Hadamard rewrites, commutations, cancellations, phase-polynomial transformations, rotation merging, and selected Toffoli decompositions [2] [57].The reported results use the light optimizer; the heavy option is more computationally intensive and is not expected to change conclusions qualitatively.Source: §E.3 · pp. 22–23

E.4 Correctness

• Correctness tests compare full PF circuits through 15 qubits, segmented QSP at size 5, Taylor-series subroutines through 15 qubits, select(V) instances at size 5, and optimized circuits before and after optimization [57].Full Taylor-series simulation is infeasible at larger sizes because of ancilla requirements, so its subroutines are tested individually.Source: §E.4 · p. 23

F Product formula implementation details

• The implementation provides analytic, minimized, commutator, and empirical error bounds to choose product-formula segment counts r for target error ǫ.Analytic and minimized bounds guarantee ǫ-closeness, while empirical bounds use numerical extrapolation and reduce gate counts without guaranteeing the true error.Source: F Product formula implementation details · p. 23
• Simulation error is measured in spectral norm, with the diamond-norm distance for a unitary process bounded by twice that spectral-norm distance [15, Lemma 7].This norm convention defines the error metric used throughout the product-formula analysis.Source: F Product formula implementation details · p. 23

F.1 Analytic and minimized bounds

• Analytic bounds are efficiently computable but pessimistic, while minimized bounds reduce r by searching for the smallest value satisfying the analytic constraints.Minimized bounds use doubling to bracket r followed by binary search; the corresponding circuits are smaller than those based on pessimistic analytic estimates.Source: §F.1 · p. 26

F.2 Commutator bounds

• The new commutator bounds exploit commuting Hamiltonian-term pairs for second- and fourth-order formulas, extending prior first-order ideas to higher orders.These are presented as the first higher-order product-formula bounds that use commutator structure.Source: §F.2 · p. 26

F.2.1 Abstract commutator bounds

• The abstract commutator analysis expresses error bounds through counts of noncommuting pairs and tuples with specified commutation patterns.For the second-order bound, the construction uses augmented Pauli-operator lists and tuple-count coefficients such as D, T1, T2, and T3.Source: §F.2.1 · p. 27

2. This shows that the third-order error is at most

• The general fourth-order commutator theorem expresses error bounds through counts of pair, triple, quadruple, and quintuple commutation patterns.Its coefficients can in principle be computed programmatically, but the appendix omits the lengthy coefficient list and gives a specialized model-specific treatment later.Source: §2 · pp. 29–30
• The product-formula derivation uses Pauli-tensor commutation relations, allowing multiplication orders to be exchanged while tracking possible minus signs.Source: §2 · p. 31
• The derivation sets f(i, j) = −1 after subtracting the relevant expressions to obtain the third-order error term.Source: §2 · p. 31
• The resulting operator expression is bounded using its spectral norm.Source: §2 · p. 31
• C−1 = 24 follows by comparing the derived bound with the preceding third-order error expression.Source: §2 · p. 31

F.2.2 Concrete commutator bounds

• For the target Hamiltonian, symmetry makes each required tuple count a low-degree polynomial in n, enabling closed-form commutator bounds from interpolation of constantly many numerical values.This avoids direct enumeration of all 5-tuples, which would take O(n^5) time with a large constant for Hamiltonians containing 40n terms.Source: §F.2.2 · p. 31
• The polynomial-counting result applies to oblivious counting problems for local translated operators, where the count depends on interval patterns rather than precise supports or system size.Theorem F.8 states that, under the stated locality and fixed-tuple-size assumptions, |f^-1(1)| is a polynomial in n.Source: §F.2.2 · p. 33
• For periodic boundary conditions, every oblivious counting problem |f^−1(1)| is a polynomial in n.The proof separates boundary-free terms, handled on a line, from boundary-crossing terms, which reduce to a constant number of polynomial contributions.Source: §F.2.2 · pp. 35–36
• Symbolic polynomial interpolation produces succinct second- and fourth-order commutator bounds for the model Hamiltonian.The construction verifies obliviousness by translating operator tuples between equivalent interval supports and separately handling boundary and infix supports.Source: §F.2.2 · p. 36
• O(n^3.4) fourth-order gate complexity suffices for constant-error simulation at t = Θ(n), improving the prior O(n^3.5) bound.The corresponding first- and second-order bounds give O(n^4) and O(n^11/3), respectively, versus prior O(n^5) and O(n^4).Source: §F.2.2 · p. 37
• Exact forms of the 2kth-order commutator bounds become challenging to compute for k ≥3, although their asymptotic n-dependence remains obtainable.The analysis requires counting (2k + 1)-tuples, whose mutually commuting contribution has leading term (8 · 5^(k−1)n)^(2k+1).Source: §F.2.2 · p. 37
• For 2kth-order formulas, the commutator analysis yields O(n^(3+2/(2k+1))) gates, improving the analytic and minimized O(n^(3+1/k)) complexity.This follows because O(n^(2k)) non-canceling tuples remain after mutually commuting tuples cancel, and r = O(n^(2+2/(2k+1))) segments suffice at t = n.Source: §F.2.2 · p. 38

F.3 Empirical bounds

• For systems of size 5 to 12, empirical segment fits for 10^−3 error are r1 = 2417n^1.964, r2 = 39.47n^1.883, r4 = 4.035n^1.555, r6 = 1.789n^1.311, and r8 = 1.144n^1.141.The fits average five random local-field choices and are obtained by numerically determining the required segment count.Source: §F.3 · p. 38
• The empirical circuit complexities are roughly 9668n^2.964, 315.8n^2.883, 161.4n^2.555, 357.8n^2.311, and 1144n^2.141 for first through eighth order.These estimates are extrapolated from small-instance simulations and do not guarantee correctness.Source: §F.3 · p. 38

G Taylor series implementation details

• The Taylor series implementation appendix provides concrete error bounds and analyzes the approach’s failure probability.Source: G Taylor series implementation details · p. 38
• The appendix identifies select(V) gates as a major Taylor-series component and explains how their control registers are encoded.Source: G Taylor series implementation details · p. 38
• It also gives an optimized implementation of select(V) gates.Source: G Taylor series implementation details · p. 38

G.1 Error analysis

• The Taylor-series analysis combines truncation, isometry, contraction, and normalization bounds to derive an explicit overall accuracy guarantee.The truncation order K is chosen by tabulating integer-valued error estimates rather than solving for K in closed form.Source: §G.1 · pp. 38, 40, 41, 42
• Direct empirical error estimation is infeasible because the Taylor-series algorithm’s ancilla requirements exceed classical simulation even for very small systems.Improving the truncated-series estimate empirically could reduce K by at most an additive ln 2, so this option is omitted.Source: §G.1 · p. 42

G.2 Failure probability

• With ǫ = 10^-3, the expected repetitions are approximately 1/0.998 ≈ 1.002, so failure overhead is neglected when comparing Taylor-series and product-formula gate counts.Unlike product formulas, the Taylor-series algorithm can fail an ancilla measurement and must restart.Source: §G.2 · p. 43

G.3 Encoding of the control register

• The control-register representation strongly affects select(V) synthesis cost in both the Taylor-series and quantum-signal-processing algorithms.For the Taylor-series algorithm, the register indexes the Taylor order k and operator labels ℓ1, …, ℓk.Source: §G.3 · p. 43
• The implementation uses unary encoding for k and binary encoding for each operator label, applying each selected factor through a single controlled operation.The map applies (−i)^k H_ℓ1 ··· H_ℓk to the target state.Source: §G.3 · p. 43

G.4 Implementation of select(V )

• The NCT construction cycles through Boolean products on a binary tree, visits every leaf, resets ancillas, and can terminate early when only some products are needed.The control register uses w := ⌈log2 Γ⌉ binary bits, and the construction applies Vγ when the ancilla identifies the γth product.Source: §G.4 · pp. 43–45
• The optimized NCT circuit approaches the lower bound of 2w −w −1 Toffoli gates, while replacing shortcut sequences and paired decompositions reduces Toffoli, cnot, Hadamard, and T/T † costs.Lemma G.6 gives the Toffoli lower bound, and the circuit optimizations combine red and green shortcuts with paired Toffoli cancellations.Source: §G.4 · pp. 44, 46, 48
• The optimized select(V ) circuit uses 2 not gates, 2 · 2w + 2w −8 Hadamard gates, 0.5 · 2w −w Phase gates, 7.5 · 2w + 6w −28 T/T † gates, and 7.5 · 2w + 6w −26 cnot gates.Its control-generation construction is equivalent before and after optimization by direct computation.Source: §G.4 · p. 48
• The optimized implementation uses 17.5 · 2w + o(2w) elementary gates, compared with a baseline estimate of 18w2w + o(w2w).It uses w −1 ancilla qubits and has a T/T †-count about 7% higher than expected for a circuit with 2w −w −1 Toffoli gates.Source: §G.4 · p. 48

H.1 Failure probability

• With ǫ = 10−3, QSP succeeds with probability at least 0.998, requiring approximately 1.002 expected repetitions, so repetition overhead is neglected in gate-count comparisons.The bound applies to the postselected operator for any input state under the stated error setting.Source: §H.1 · p. 48

H Quantum signal processing implementation details

• The QSP implementation reuses the optimized select(V ) subroutine and addresses success probability, circuit optimizations, phase computation, segmentation, and empirical truncation-error bounds.These topics comprise the QSP implementation-details section and its subsections.Source: H Quantum signal processing… · p. 48, §H.2 · p. 49

H.2 Circuit optimizations

• Cancelling inner partial reflections and removing trivial ancilla-register phases saves O(n2 log n) gates because each of O(n2) phased iterates otherwise uses O(log n) elementary gates.The cancellations rely on the phased-iterate sequence and initialization and postselection of the ancilla register in |G⟩.Source: §H.2 · p. 49
• Controlled state-preparation conjugations can be replaced by uncontrolled versions, and neighboring phased iterates cancel pairs of U and U † operations.This simplifies controlled reflection about |G⟩ while preserving the circuit behavior.Source: §H.2 · p. 49

Phase computation

• The QSP phase computation becomes prohibitive for M greater than about 32, while a representative n = 10 instance requires M = 1100.The bottleneck is high-precision root finding for a high-degree polynomial, making practical phase computation an open problem.Source: §H.3 · p. 49
• Random angles can estimate Clifford+T resource requirements without the true phases, but they do not produce a valid quantum simulation circuit.This benchmark is useful only if the exact angles can ultimately be computed.Source: §H.3 · p. 49

Segmented algorithm

• Figure 7 shows that the segmented implementation uses only 2–3 times as many phased iterates as the optimal implementation over the range of interest.This moderate overhead accompanies a complete implementation, unlike the random-angle resource estimate.Source: Figure 7 · p. 50, §H.3 · p. 50
• The segmented algorithm has gate complexity O(n3+4/M) for t = n, α = O(n), and fixed M, because it uses O(n2+4/M) segments with M phased iterates of size O(n).Segmentation makes the angles readily computable within each short evolution segment, but increases asymptotic complexity relative to a single segment.Source: §H.3 · pp. 49–50

Empirical bound

• The empirical bound improves the QSP gate count by a factor between 1.25 and 1.45 for 10 ≤ n ≤ 100.The estimate extrapolates numerical evaluations of the Jacobi–Anger remainder from system sizes 10 to 20.Source: §H.4 · p. 51
• QSP complexity is O(n^2.988) with the analytic bound versus O(n^2.939) with the empirical bound.Each phased iterate has gate complexity O(n), and the analytic scaling is roughly consistent with O(n^3 log n).Source: §H.4 · p. 51

Scope and limitations

• The empirical bound is applied only to non-segmented QSP, producing the algorithm’s most optimistic benchmark, while segmented QSP retains rigorous guarantees.Savings for segmented QSP are small, especially at M = 28.Source: §H.4 · p. 51
• Full empirical error bounds are excluded because QSP requires n+⌈log 4n⌉+1 qubits for direct simulation and shows little error reduction.For system sizes 5–9, QSP error is consistently around 5 × 10^-5, never below 10^-5, and shows no decrease indication; its complexity depends logarithmically on 1/ε.Source: §H.4 · pp. 51–52, Figure 9 · p. 52

I Detailed results

• Product-formula gate counts are largely insensitive to Hamiltonian coefficients, whereas TS varies by about 10% at size 13 and about 2% at size 100.QSP’s cnot and Rz counts are coefficient-independent, while its Clifford and T counts vary by less than 1%.Source: I Detailed results · p. 53

I.1 Product formulas

• The first-order formula uses 10^2 to over 10^4 times more gates than fourth- or sixth-order formulas, indicating that higher-order methods matter even for relatively small instances.This contrasts with prior experimental demonstrations that primarily used first-order formulas, with limited second-order applications [6] [19] [48].Source: §I.1 · p. 53
• For rigorous product-formula bounds, fourth order is preferred except at very small sizes, whereas sixth order begins outperforming it near 30 qubits under the empirical bound.The second-order method with the minimized bound only outperforms fourth order for n ≤28.Source: §I.1 · p. 53, Figure 10 · p. 54
• The empirical product-formula improvements persist under h = 1/10 and h = 10, producing essentially the same n exponent with only slightly different prefactors.The empirical bound is directly applicable only to the studied system and parameters, although qualitatively similar improvements are expected elsewhere.Source: §I.1 · pp. 54–55
• The commutator bound reduces fourth-order gate counts by more than 10× versus the minimized bound, while the empirical bound saves about 100× to over 500× more.The empirical savings range from systems in the tens to systems around 100 qubits, but lack a rigorous correctness guarantee.Source: §I.1 · p. 54, Figure 11 · p. 55
• Commutator and empirical bounds improve system-size scaling, with the eighth-order empirical formula having asymptotic complexity only slightly greater than quadratic in n.The commutator method reduces the lowest-order error’s n-dependence and yields asymptotic complexity O(n3+2/(2k+1)).Source: §I.1 · pp. 54–55, Table 3

I.2 Other algorithms and comparisons

• TS beats rigorous fourth-order product formulas for n of about 30 or more and reduces T counts by about 7×, but requires 116–171 qubits for systems of 20–50.Its cnot improvement is negligible, and QSP always outperforms TS in both circuit size and qubit count.Source: §I.2 · pp. 55–56
• Segmented QSP has the lowest gate counts among completely implemented algorithms with rigorous accuracy guarantees, while empirical product formulas are cheaper when heuristic estimates suffice.Segmented QSP uses at least 5× fewer cnot gates than fourth-order product formulas and TS; empirical product formulas significantly outperform both QSP variants without ancillas.Source: §I.2 · p. 56

I.3 Circuit optimization

• 33% fewer cnot gates are obtained for PF circuits versus about 1% for both TS and QSP, while T-count reductions are approximately 30%, 0.5%, and 1%, respectively.These reductions are reported for Clifford+Rz cnot counts and Clifford+T T counts, respectively.Source: §I.3 · p. 56, Figure 12 · p. 57
• Optimization makes PF outperform TS in cnot count for system sizes below about 30, although TS otherwise outperforms the best rigorously guaranteed PF algorithm shown.QSP remains more efficient than TS, but the example demonstrates that optimization can alter relative algorithm performance.Source: §I.3 · p. 56, Figure 12 · p. 57
• About 33% fewer cnot gates and 29% fewer Rz gates result for higher-order PF circuits, whereas first-order circuits receive no corresponding reductions.The Rz savings arise from reflection symmetry in formulas of order 2 and higher, with marginally greater cnot savings at higher orders.Source: §I.3 · p. 56, Figure 13 · p. 57
• Because optimization depends on PF circuit structure rather than the chosen error bound, essentially the same relative improvements apply across bounds.The comparison uses PF circuits with the empirical bound, which offers the best performance.Source: §I.3 · p. 56, Figure 13 · p. 57