All you need is Trotter
Fujitsu Research of America, Inc, Santa Clara, CA 95054, USA
| Published: | 2026-11-06, volume 10, page 2261 |
| Editor: | Felix Huber |
| Eprint: | arXiv:2311.01533v6 |
| Doi: | https://doi.org/10.22331/q-2026-11-06-2261 |
| Citation: | Quantum 10, 2261 (2026). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The work here enables a cost scaling of $\tilde{O}\left( \frac{T ^{1+o(1)} {\rm log}^2 (1/\epsilon)}{\varepsilon}\right)$ and maximum depth $\tilde{O}\left( \frac{T^{1+o(1)} {\rm log} (1/\epsilon)}{\varepsilon}\right)$ for estimating observables after some Hamiltonian evolution $e^{i H T}$ using no extra block-encoding qubits, where $\epsilon$ is the algorithmic error of the target Hamiltonian evolution and $\varepsilon$ is the statistical error from the observable estimation. Throughout, $\tilde{O}$ suppresses factors that are doubly logarithmic in $1/\epsilon$ (i.e. ${\rm polyloglog}(1/\epsilon)$), which are subdominant to the displayed ${\rm polylog}(1/\epsilon)$ factors. This is achieved through product formulas, stable interpolation (Chebyshev), and to calculate the needed fractional queries, cardinal sine interpolation is used. This is an improvement over similar work using interpolation methods which have a superlinear scaling of the form $5^p T^{1+1/p}$, where $p$ is the order of the product formula used and an improvement on required qubits over Quantum Signal Processing methods while maintaining scaling with ${\rm polylog}{1/\epsilon}$. This is accomplished through an optimized and variable (with $T$) order $p$. The slightly better $\log^2(1/\epsilon)$ compared to $\log^3(1/\epsilon)$ comes from the use of cardinal sine interpolation compared to other methods using Chebyshev interpolation and product formulas. The work presented here also provides an alternative to Quantum Signal Processing techniques to calculate observables or amplitudes after a fractional query evolution with a cost $O(T\log{1/\epsilon})$ through this cardinal sine interpolation.
Featured image: Recovering a fractional quantum operation from whole-number ones. Each vertical line is a circuit that repeats the Trotter step a whole number of times, $S_p^{m+n}$, and the dots are the measured results. Shaped by a Gaussian window (orange), these samples are combined on a classical computer with cardinal sine weights to obtain the result of the fractional operation $S_p^{f}$ (star), which need not be run directly.
Popular summary
The simplest and most hardware-friendly way to do this is the Trotter method. It breaks the evolution into many small time steps, each built from simple pieces that are easy to run. The catch is accuracy. Every step introduces a small error, and pushing the error down requires ever smaller steps and ever deeper circuits. More sophisticated techniques avoid this problem and reach high precision far more cheaply, but they need extra qubits and additional circuitry, which will be scarce on the first generations of error-corrected quantum computers.
This work shows that one can have the best of both worlds. The idea is to run the simple Trotter circuit at several different step sizes, measure the results, and then extrapolate on an ordinary computer to what the answer would be at zero step size, where the Trotter error disappears. For this extrapolation to be reliable, the step sizes must be chosen at special, carefully spaced points. Unfortunately, those points ask the quantum computer to repeat a step a fractional number of times, say 7.42 times, which cannot be done directly.
The key ingredient of this work solves that problem without touching the quantum hardware. Instead of running 7.42 steps, the quantum computer runs whole numbers of steps nearby (5, 6, 7, 8, 9, and so on) and measures each result. A classical computer then combines these measurements using cardinal sine interpolation, the same mathematics that lets digital audio rebuild a smooth sound wave from discrete samples. A Gaussian window keeps the number of required samples small, and the reconstruction is accurate and stable against measurement noise.
The resulting algorithm estimates quantities after quantum time evolution with a cost that grows only nearly linearly with the simulation time and only polylogarithmically with the desired precision, matching the precision scaling of the advanced methods. Yet it uses nothing but Trotter circuits and two extra qubits. As a byproduct, it also gives a simple new way to evaluate “fractional” quantum operations, a long-standing ingredient in quantum algorithms. These features make the approach well suited to early fault-tolerant quantum computers, where every qubit counts.
► BibTeX data
► References
[1] S. Aaronson, ``The ten most annoying questions in quantum computing, 2006.'' https://www.scottaaronson.com/blog/?p=112.
https://www.scottaaronson.com/blog/?p=112
[2] L. Sheridan, D. Maslov and M. Mosca, Approximating fractional time quantum evolution, Journal of Physics A Mathematical General 42 (2009) 185302 [0810.3843].
https://doi.org/10.1088/1751-8113/42/18/185302
arXiv:0810.3843
[3] R. Cleve, D. Gottesman, M. Mosca, R.D. Somma and D. Yonge-Mallo, Efficient discrete-time simulations of continuous-time quantum query algorithms, in Proceedings of the forty-first annual ACM symposium on Theory of computing, STOC ’09, p. 409–416, ACM, May, 2009, DOI.
https://doi.org/10.1145/1536414.1536471
[4] D.W. Berry, A.M. Childs, R. Cleve, R. Kothari and R.D. Somma, Exponential improvement in precision for simulating sparse Hamiltonians, in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pp. 283–292, ACM, 2014, DOI [1312.1414].
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414
[5] G.H. Low and I.L. Chuang, Optimal hamiltonian simulation by quantum signal processing, Physical Review Letters 118 (2017).
https://doi.org/10.1103/physrevlett.118.010501
[6] G.H. Low and N. Wiebe, Hamiltonian simulation in the interaction picture, 2018. 10.48550/arXiv.1805.00675.
[7] A. Gilyén, Y. Su, G.H. Low and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 193–204, ACM, 2019, DOI [1806.01838].
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838
[8] G. Rendon, J. Watkins and N. Wiebe, Improved accuracy for Trotter simulations using Chebyshev interpolation, Quantum 8 (2024) 1266 [ 2212.14144].
https://doi.org/10.22331/q-2024-02-26-1266
arXiv:2212.14144
[9] E.T. Whittaker, XVIII.—on the functions which are represented by the expansions of the interpolation-theory, Proceedings of the Royal Society of Edinburgh 35 (1915) 181.
https://doi.org/10.1017/S0370164600017806
[10] V.A. Kotel'nikov, On the transmission capacity of `ether' and wire in electric communications, Physics-Uspekhi 49 (2006) 736.
https://doi.org/10.1070/PU2006v049n07ABEH006160
[11] H. Nyquist, Certain topics in telegraph transmission theory, Transactions of the American Institute of Electrical Engineers 47 (1928) 617.
https://doi.org/10.1109/T-AIEE.1928.5055024
[12] C.E. Shannon, A mathematical theory of communication, The Bell System Technical Journal 27 (1948) 379.
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
[13] M. Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics 32 (1991) 400.
https://doi.org/10.1063/1.529425
[14] G.H. Low and I.L. Chuang, Hamiltonian Simulation by Qubitization, Quantum 3 (2019) 163.
https://doi.org/10.22331/q-2019-07-12-163
[15] G. Rendon, T. Izubuchi and Y. Kikuchi, Effects of cosine tapering window on quantum phase estimation, Physical Review D 106 (2022) 034503 [2110.09590].
https://doi.org/10.1103/PhysRevD.106.034503
arXiv:2110.09590
[16] J.D. Watson and J. Watkins, Exponentially reduced circuit depths using Trotter error mitigation, PRX Quantum 6 (2025) 030325 [ 2408.14385].
https://doi.org/10.1103/kw39-yxq5
arXiv:2408.14385
[17] G.H. Low, V. Kliuchnikov and N. Wiebe, Well-conditioned multiproduct Hamiltonian simulation, 2019. 10.48550/arXiv.1907.11679.
[18] J. Watkins, N. Wiebe, A. Roggero and D. Lee, Time-dependent Hamiltonian simulation using discrete-clock constructions, PRX Quantum 5 (2024) 040316.
https://doi.org/10.1103/PRXQuantum.5.040316
[19] G. Brassard, P. Høyer, M. Mosca and A. Tapp, Quantum amplitude amplification and estimation, in Quantum Computation and Information, vol. 305 of Contemporary Mathematics, pp. 53–74, American Mathematical Society (2002), DOI [ quant-ph/0005055].
https://doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055
[20] D. Grinko, J. Gacon, C. Zoufal and S. Woerner, Iterative quantum amplitude estimation, npj Quantum Information 7 (2021) 52 [1912.05559].
https://doi.org/10.1038/s41534-021-00379-1
arXiv:1912.05559
[21] W. Gautschi, How (un)stable are Vandermonde systems?, in Asymptotic and Computational Analysis, R. Wong, ed., vol. 124 of Lecture Notes in Pure and Applied Mathematics, (New York), pp. 193–210, Marcel Dekker, 1990, DOI.
https://doi.org/10.1201/9781003072584-9
[22] M. Kuian, L. Reichel and S. Shiyanovskii, Optimally conditioned vandermonde-like matrices, SIAM Journal on Matrix Analysis and Applications 40 (2019) 1399 [ https://doi.org/10.1137/19M1237272].
https://doi.org/10.1137/19M1237272
arXiv:https://doi.org/10.1137/19M1237272
[23] J.C. Mason and D.C. Handscomb, Chebyshev Polynomials, Chapman and Hall/CRC (2002), 10.1201/9781420036114.
https://doi.org/10.1201/9781420036114
[24] L.N. Trefethen, Approximation Theory and Approximation Practice, Extended Edition, SIAM, Philadelphia, PA (2019), 10.1137/1.9781611975949.
https://doi.org/10.1137/1.9781611975949
[25] J. van Apeldoorn, A. Gilyén, S. Gribling and R. de Wolf, Quantum SDP-solvers: Better upper and lower bounds, Quantum 4 (2020) 230.
https://doi.org/10.22331/q-2020-02-14-230
[26] H. Vandeven, Family of spectral filters for discontinuous problems, J. Sci. Comput. 6 (1991) 159–192.
https://doi.org/10.1007/BF01062118
Cited by
Could not fetch Crossref cited-by data during last attempt 2026-11-06 09:42:14: Could not fetch cited-by data for 10.22331/q-2026-11-06-2261 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-11-06 09:42:14: Cannot retrieve data from ADS due to rate limitations.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.