Skip to content

Product formulae

Rough overview (in words)

Product formulae (or Trotter–Suzuki formulae/Trotterization) [1], are the most commonly used approach for Hamiltonian simulation and are applicable to Hamiltonians in the Pauli and sparse access models (see below for definitions of these models). Product formulae divide the evolution into a repeating sequence of short unitary evolutions under subterms of the Hamiltonian. These subterm evolutions have a known decomposition into elementary quantum gates. The error in product formulae depends on the commutators between different terms in the decomposition; if all of the terms in the Hamiltonian commute, product formulae are exact.

Product formula approaches have also been extended to treat time-dependent Hamiltonians [2, 3, 4, 5, 6]. In the following discussion, we will restrict our focus to the time-independent case, noting that the time-dependent approaches are executed in the same way, but have a slightly more complex error analysis.

Rough overview (in math)

Given a Hamiltonian \(H\), desired evolution time \(t\), and error \(\epsilon\), return a circuit \(U(t)\) made of elementary gates such that

\[\begin{align} \nrm{ U(t) - \mathrm{e}^{\mathrm{i} H t} } \le \epsilon\,, \end{align}\]

In the above, we use the operator norm \(\nrm{\cdot}\) (the maximal singular value) to quantify the quality of approximation, which controls the error for arbitrary input states (in trace distance) and for observables. This worst-case metric is mathematically convenient, but, as discussed below, tighter bounds may be obtained by using error metrics more closely aligned with the specification of the problem.

A product formula generates \(U(t)\) through a product of easy-to-implement evolutions under terms in the Hamiltonian. For a Hamiltonian decomposition \(H = \sum_{j=1}^L H_j\) with \(L\) terms, the first-order product formula with \(r\) steps is

\[\begin{equation} S_1(t) = \left( \prod\nolimits_{j=1}^L e^{iH_jt/r } \right)^r. \end{equation}\]

The error in the first-order product formula is upper bounded as [7]

\[\begin{equation} \nrm{S_1(t) - e^{iHt} } \leq \frac{t^2}{2r} \sum_i^L \left\lVert \sum_{j>i}^L [H_i, H_j] \right\rVert \leq \frac{\nrm{H}_1^2 t^2}{2r} \end{equation}\]

where \(\nrm{H}_1 := \sum_{j=1}^L \nrm{H_j}\). Higher-order formulae can be defined recursively and are referred to as \((2k)\)th-order product formulae. The error in a recursively defined \((2k)\)th-order product formula is bounded by [7]

\[\begin{equation} \nrm{S_{2k}(t) - e^{iHt} } = \mathcal{O}\left( \frac{\nrm{H}_1^{2k+1} t^{2k+1}}{r^{2k}} \right). \end{equation}\]

Product formulae can be applied to \(d\)-sparse Hamiltonians (at most \(d\) nonzero elements per row/column) with efficiently row-computable nonzero elements [8]. Access to the nonzero elements of the Hamiltonian is provided via oracles \(O_f\) and \(O_H\). The oracle \(O_f\) returns the column index (\(j\)) of the \(k \in \{1,...,d\}\)th nonzero element in row \(i\). The oracle \(O_H\) returns the value of the matrix element \(H_{ij}\).

\[\begin{align} O_f & : O_f \ket{k} \ket{i} \ket{0} = \ket{k} \ket{i} \ket{j} \\ O_H & : O_H \ket{i}\ket{j}\ket{0} = \ket{i}\ket{j}\ket{H_{ij}} \end{align}\]

Using graph-coloring algorithms, a \(d\)-sparse Hamiltonian \(H\) can be efficiently decomposed into a sum of efficiently simulable Hamiltonians [9, 10].

As a special case of the \(d\)-sparse access model, one can consider Hamiltonians given as a linear combination of \(L\) Pauli terms \(H = \sum_{j=1}^L H_j = \sum_{j=1}^L \alpha_j P_j\), as each Pauli tensor product is already a \(1\)-sparse matrix (so in this case, \(d\leq L\)). Time evolution under each Pauli term (or in some cases, groups of Pauli terms) can be simulated efficiently, thus simplifying the \(d\)-sparse construction by removing the need for oracles \(O_f\) and \(O_H\).

Dominant resource cost (gates/qubits)

For an \(n\)-qubit Hamiltonian, product formulae act on \(n\) qubits. In the Pauli access model, no additional ancilla qubits are required. In the sparse access model, ancilla qubits may be required to implement the oracles \(O_f\) and \(O_H\) and to implement time evolution under \(1\)-sparse Hamiltonians \(H_j\).

The gate complexity is obtained by choosing the number of Trotter steps \(r\) sufficiently large to obtain an error \(\epsilon\) and multiplying by the complexity of implementing each step of the product formula. It is necessary to balance the improved asymptotic scaling with \(t\) (approaches linear dependence) and \(\epsilon\) of higher-order Trotter formulae against the exponentially growing prefactor of the higher-order formulae. In practical simulations of chemistry, condensed matter systems, or quantum field theories, a low-order formula (2nd–6th) typically minimizes the gate count.

A recursively defined \((2k)\)th-order product formula (the first-order formula is given by \(k=1/2\), and is the base case) for simulating a \(d\)-sparse Hamiltonian for time \(t\) to accuracy \(\epsilon\) requires [10]

\[\begin{equation} \mathcal{O}\left( 5^{2k} d^2 (d + \log^*n) \nrm{H}t \left(\frac{d \nrm{H} t}{\epsilon} \right)^{1/2k} \right) \end{equation}\]

calls to the oracles \(O_f\) and \(O_H\), where \(\log^*\) is the iterated logarithm.1

A recursively defined \((2k)\)th-order product formula for simulating an \(L\)-term Hamiltonian in the Pauli access model for time \(t\) to accuracy \(\epsilon\) requires [7]

\[\begin{equation} \mathcal{O}\left( 5^{2k} nLt\left(\frac{t \alpha_{\mathrm{comm},k}}{\epsilon} \right)^{1/2k} \right) \end{equation}\]

elementary single and two-qubit gates, where \(\alpha_{\mathrm{comm},k} := \sum_{i_1, i_2,\ldots, i_{2k+1}} \nrm{[H_{i_{2k+1}},\ldots [H_{i_2}, H_{i_1}]]}\). The dependence on \(\alpha_{\mathrm{comm},k}\) can be tightened and calculated for lower-order formulae (see [7] for full calculations). The dependence on \(n\) can be reduced to \(w\) for local Hamiltonians with Pauli terms that each act on at most \(w\) qubits.

Caveats

The error bounds of product formulae in the Pauli access model have been the object of significant investigation. Evaluating the tightest spectral norm bounds requires computing a large number of commutators between the terms in the Hamiltonian, which can be computationally intensive. Numerical simulations have shown that the commutator bounds can be loose by several orders of magnitude for chemical [11, 12] or spin [13] systems.

The spectral norm is the worst-case metric; it is an active area of research to find error metrics better suited to the problem at hand. For example, one may consider the average-case error over random input states [14, 15] by the normalized Frobenius norm \(\nrm{U(t) - \mathrm{e}^{\mathrm{i} H t}}_{F}/\sqrt{2^n}\). Recently, in [14] it was shown that the average-case error can be much smaller than the worst-case error for systems with large connectivity. More directly, one can also compute the Trotter error associated with input states from the low-energy [16] or low-particle-number subspace [17, 18].

The gate counts of product formulae approaches can also be reduced by grouping together mutually commuting terms such that they can be implemented using fewer gates than would be required to implement all the terms individually [19, 20, 21]. One can also reduce the number of Trotter steps required by randomizing the ordering of the terms [22, 23, 6] (although this must be balanced against any compilation benefits that may be obtained from a fixed ordering).

Example use cases

Further reading

Bibliography

  1. Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073–1078, 1996. doi:10.1126/science.273.5278.1073.

  2. J Huyghebaert and H De Raedt. Product formula methods for time-dependent schrodinger problems. Journal of Physics A: Mathematical and Theoretical, 23(24):5777, 1990. doi:10.1088/0305-4470/23/24/019.

  3. Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C Sanders. Higher order decompositions of ordered operator exponentials. Journal of Physics A: Mathematical and Theoretical, 43(6):065203, 1 2010. arXiv: https://arxiv.org/abs/0812.0562. URL: https://dx.doi.org/10.1088/1751-8113/43/6/065203, doi:10.1088/1751-8113/43/6/065203.

  4. Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak, and Matthias Troyer. Solving strongly correlated electron models on a quantum computer. Physical Review A, 92:062318, 12 2015. arXiv: https://arxiv.org/abs/1506.05135. URL: https://link.aps.org/doi/10.1103/PhysRevA.92.062318, doi:10.1103/PhysRevA.92.062318.

  5. Dong An, Di Fang, and Lin Lin. Time-dependent unbounded hamiltonian simulation with vector norm scaling. Quantum, 5:459, 5 2021. arXiv: https://arxiv.org/abs/2012.13105. URL: https://doi.org/10.22331/q-2021-05-26-459, doi:10.22331/q-2021-05-26-459.

  6. David Poulin, Angie Qarry, Rolando Somma, and Frank Verstraete. Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space. Physical Review Letters, 106:170501, 4 2011. arXiv: https://arxiv.org/abs/1102.1360. URL: https://link.aps.org/doi/10.1103/PhysRevLett.106.170501, doi:10.1103/PhysRevLett.106.170501.

  7. Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Physical Review X, 2 2021. arXiv: https://arxiv.org/abs/1912.08854. doi:10.1103/physrevx.11.011020.

  8. Dorit Aharonov and Amnon Ta‐Shma. Adiabatic quantum state generation. SIAM Journal on Computing, 37(1):47–82, 2007. Earlier version in STOC'03, arXiv: https://arxiv.org/abs/quant-ph/0301023. doi:10.1137/060648829.

  9. Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270(2):359–371, 2007. arXiv: https://arxiv.org/abs/quant-ph/0508139. doi:10.1007/s00220-006-0150-x.

  10. Andrew M. Childs and Robin Kothari. Simulating sparse hamiltonians with star decompositions. In Wim van Dam, Vivien M. Kendon, and Simone Severini, editors, Proceedings of the 5th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), 94–103. Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. arXiv: https://arxiv.org/abs/1003.3683. doi:10.1007/978-3-642-18073-6\_8.

  11. Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe. Chemical basis of trotter-suzuki errors in quantum chemistry simulation. Physical Review A, 91:022311, 2 2015. arXiv: https://arxiv.org/abs/1410.8159. doi:10.1103/PhysRevA.91.022311.

  12. David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doberty, and Matthias Troyer. The trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Info. Comput., 15(5–6):361–384, 4 2015. arXiv: https://arxiv.org/abs/1406.4920. doi:10.26421/QIC15.5-6-1.

  13. Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. arXiv: https://arxiv.org/abs/1711.10980. doi:10.1073/pnas.1801723115.

  14. Chi-Fang Chen and Fernando G. S. L. Brandão. Average-case speedup for product formulas. arXiv: https://arxiv.org/abs/2111.05324, 2021.

  15. Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. Hamiltonian simulation with random inputs. Physical Review Letters, 129:270502, 12 2022. arXiv: https://arxiv.org/abs/2111.04773. URL: https://link.aps.org/doi/10.1103/PhysRevLett.129.270502, doi:10.1103/PhysRevLett.129.270502.

  16. Burak Şahinoğlu and Rolando D. Somma. Hamiltonian simulation in the low-energy subspace. npj Quantum Information, 7 2021. arXiv: https://arxiv.org/abs/2006.02660. URL: https://doi.org/10.1038\%2Fs41534-021-00451-w, doi:10.1038/s41534-021-00451-w.

  17. Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, and Yuan Su. Provably accurate simulation of gauge theories and bosonic systems. Quantum, 6:816, 9 2022. arXiv: https://arxiv.org/abs/2110.06942. URL: https://doi.org/10.22331/q-2022-09-22-816, doi:10.22331/q-2022-09-22-816.

  18. Yuan Su, Hsin Yuan Huang, and Earl T. Campbell. Nearly tight trotterization of interacting electrons. Quantum, 5(1):1–58, 2021. arXiv: https://arxiv.org/abs/2012.09194. arXiv:2012.09194, doi:10.22331/Q-2021-07-05-495.

  19. Ewout van den Berg and Kristan Temme. Circuit optimization of hamiltonian simulation by simultaneous diagonalization of pauli clusters. Quantum, 4:322, 9 2020. arXiv: https://arxiv.org/abs/2003.13599. URL: https://doi.org/10.22331/q-2020-09-12-322, doi:10.22331/q-2020-09-12-322.

  20. Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush. Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization. Quantum, 4:296, 7 2020. arXiv: https://arxiv.org/abs/1902.10673. URL: https://doi.org/10.22331/q-2020-07-16-296, doi:10.22331/q-2020-07-16-296.

  21. Earl T Campbell. Early fault-tolerant simulations of the hubbard model. Quantum Science and Technology, 7(1):015007, 11 2021. arXiv: https://arxiv.org/abs/2012.09238. URL: https://dx.doi.org/10.1088/2058-9565/ac3110, doi:10.1088/2058-9565/ac3110.

  22. Andrew M. Childs, Aaron Ostrander, and Yuan Su. Faster quantum simulation by randomization. Quantum, 3:182, 9 2019. arXiv: https://arxiv.org/abs/1805.08385. URL: https://doi.org/10.22331/q-2019-09-02-182, doi:10.22331/q-2019-09-02-182.

  23. Chien Hung Cho, Dominic W Berry, and Min-Hsiu Hsieh. Doubling the order of approximation via the randomized product formula. arXiv: https://arxiv.org/abs/2210.11281, 2022.

  1. For practical purposes, the iterated logarithm is essentially constant, since \(\log^*(n) \leq 5\) for all \(n \leq 2^{65536}\). ↩