Skip to content

Taylor and Dyson series (linear combination of unitaries)

Rough overview (in words)

Taylor and Dyson series approaches for Hamiltonian simulation expand the time evolution operator as a Taylor series (time independent) [1] or Dyson series (time dependent) [2, 3] and use the linear combination of unitaries (LCU) primitive to apply the terms in the expansion, followed by (robust, oblivious) amplitude amplification to boost the success probability close to unity. These methods are close to being asymptotically optimal, achieving linear scaling in time and logarithmic dependence on the error. However, they use a large number of ancilla qubits, compared to other Hamiltonian simulation algorithms.

Rough overview (in math)

We focus on the time-independent case and follow the presentation in [1]. 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 (the maximal singular value) to quantify the worst-case error in the simulation.

The total evolution time \(t\) is divided into \(r\) segments. In each segment we evolve under an approximation of \(e^{iHt/r}\). The Hamiltonian is decomposed into a linear combination of unitary operations \(H = \sum_{l=1}^L \alpha_l H_l\), where we choose \(\alpha_l\) real and positive by shifting phases into \(H_l\), and \(\nrm{H_l}=1\). This decomposition appears naturally when the Hamiltonian is given as a linear combination of Pauli products. We approximate \(e^{iHt/r}\) using a Taylor expansion truncated to degree \(K\)

\[\begin{align} e^{iHt/r} \approx U(t/r) & := \sum_{k=0}^K \frac{1}{k!} (iHt/r)^k \\ \nonumber & =\sum_{k=0}^K \sum_{l_1, ... l_k=1}^L \frac{(it/r)^k}{k!} \alpha_{l_1} ... \alpha_{l_k} H_{l_1} ... H_{l_k}. \end{align}\]

Each segment \(U(t/r)\) is implemented using robust oblivious amplitude amplification. Amplitude amplification is necessary because truncating the Taylor series at degree \(K\) makes \(U(t/r)\) non-unitary. However, textbook amplitude amplification necessitates reflecting around the initial state, (as well as the "good" state), which would be problematic since Hamiltonian simulation requires synthesizing a unitary that works simultaneously for all input states. This can be circumvented using oblivious amplitude amplification: we are given a unitary \(V\) such that for any state \(\ket{\psi}\), we have \(V \ket{\bar{0}_m} \ket{\psi} = a \ket{\bar{0}_m} U \ket{\psi} + b \ket{(\bar{0}_m \psi)^\perp}\), for a unitary operator \(U\), and the goal is to amplify the state \(\ket{\bar{0}_m} U \ket{\psi}\) to be obtained with probability 1 (we can recognize \(V\) as an \((a, m, 0)\) unitary block-encoding of \(U\)). A further problem is that the above operator \(U(t/r)\) is non-unitary, and so deviates from the formulation of oblivious amplitude amplification [4]. The proven "robustness" property of oblivious amplitude amplification [1] ensures that the error induced by treating \(U(t/r)\) as a probabilistically implemented unitary does not accumulate.

The value of \(K\) controls the error in the simulation and can be chosen as

\[\begin{equation} K=\mathcal{O}\left( \frac{\log(\nrm{H}_1 t /\epsilon)}{ \log\log(\nrm{H}_1 t / \epsilon )} \right)\,, \end{equation}\]

where we define \(\nrm{H}_1: = \sum_{l=1}^L \alpha_l\). The total time evolution is divided into \(r = \nrm{H}_1 t / \ln(2)\) segments, each of duration \(\ln(2) / \nrm{H}_1\). This ensures that a single application of robust oblivious amplitude amplification boosts the success probability of the segment to unity.

Within each segment we apply \(U(t/r)\) using the LCU primitive. This technique can be applied to Hamiltonians given in both the Pauli and \(d\)-sparse access models. For the Pauli access model, the Hamiltonian is already in the form of a linear combination of unitary operators. For the \(d\)-sparse case, we can use graph coloring algorithms [5, 6] to decompose the \(d\)-sparse Hamiltonian into a linear combination of unitaries, where each unitary is \(1\)-sparse and self-inverse.

Dominant resource cost (gates/qubits)

In addition to the \(n\)-qubit data register, the Taylor series approach requires a number of ancilla registers to implement the LCU technique. A register with \(K\) qubits is used to control the degree of the Taylor expansion, storing the value as \(\ket{k} = \ket{1^{\otimes k} 0^{\otimes (K-k) }}\). An additional \(K\) registers, each containing \(\lceil \log_2(L) \rceil\) qubits, are used to index the possible values of each of the possible \(H_{l_k}\). Hence, the overall space complexity is \(\mathcal{O}\left( n + K\log(L) \right) = \mathcal{O}\left( n + \log(\nrm{H}_1 t/\epsilon)\log(L) \right)\).

Additional ancilla qubits may be required to implement the LCU gadget (i.e. in the sparse access model) or for the reflections used in robust oblivious amplitude amplification.

As discussed above, implementing each segment requires one use of robust oblivious amplitude amplification, which makes 2 calls to the LCU circuit and 1 call to its inverse. The method incurs approximation errors from truncating the Taylor series at degree \(K\) and from the use of robust oblivious amplitude amplification. The resulting error per segment is bounded by \(\left(e \ln{2}/(K+1) \right)^{K+1}\).

The cost of the LCU circuit depends on the Hamiltonian access model. For the case of the Pauli access model the LCU circuit requires two calls to a PREPARE operation that prepares the ancilla registers with the correct coefficients. This requires \(\mathcal{O}\left( LK \right)\) gates. The LCU circuit also requires one call to a SELECT oracle, which can be implemented using \(K\) controlled-select\((H)\) operations that act as \(\ket{b}\ket{l}\ket{\psi} \rightarrow \ket{b}\ket{l} (iH_l)^b \ket{\psi}\) (where \(b \in \{0,1\}\)), and each act on a different one of the \(K\) different \(\log(L)\)-qubit registers. These can each be implemented using \(\mathcal{O}\left( L(n + \log(L) \right)\) elementary gates [1]. The overall gate complexity in the Pauli access model is thus

\[\begin{align} \mathcal{O}\left( \frac{\nrm{H}_1 t L(n + \log(L))\log(\nrm{H}_1 t / \epsilon) }{\log\log(\nrm{H}_1 t / \epsilon)} \right) = \widetilde{\mathcal{O}}\left( \nrm{H}_1 t Ln \log\left( \frac{1}{\epsilon} \right) \right) \end{align}\]

Using the LCU approach applied to a 1-sparse decomposition of a \(d\)-sparse Hamiltonian, the overall complexity is [1]

\[\begin{align} \mathcal{O}\left( \frac{d^2 \nrm{H}_{\mathrm{max}} t n \log^2(d^2 |H|_{\mathrm{max}} t / \epsilon) }{\log\log(d^2 \nrm{H}_{\mathrm{max}} t / \epsilon)} \right) = \widetilde{\mathcal{O}}\left( d^2 \nrm{H}_{\mathrm{max}} t n \log^2\left( \frac{1}{\epsilon} \right) \right) \end{align}\]

where \(\nrm{H}_{\mathrm{max}} = \mathrm{max}_{i,j} \lvert \bra{i}H\ket{j} \rvert\).

The extension to time-dependent Hamiltonians, through the use of a Dyson series, requires an additional "clock" register to store the time value and introduces a logarithmic dependence on the time derivative of the Hamiltonian [2, 3].

Caveats

Concrete resource estimates for physical systems of interest have observed that the Taylor series approach may require more ancilla qubits and gates than product formulae or quantum signal processing approaches for Hamiltonian simulation [7]. The gate complexity of the algorithm can be reduced by exploiting anticommutativity in the Hamiltonian [8], adding a corrective operation [9], or pruning terms with small magnitudes from the expansion [10].

Example use cases

Further reading

Bibliography

  1. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Physical Review Letters, 114(9):090502, 2015. arXiv: https://arxiv.org/abs/1412.4687. doi:10.1103/PhysRevLett.114.090502.

  2. Mária Kieferová, Artur Scherer, and Dominic W. Berry. Simulating the dynamics of time-dependent hamiltonians with a truncated dyson series. Physical Review A, 99:042314, 4 2019. arXiv: https://arxiv.org/abs/1805.00582. URL: https://link.aps.org/doi/10.1103/PhysRevA.99.042314, doi:10.1103/PhysRevA.99.042314.

  3. Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent hamiltonian simulation with \(l^1\)-norm scaling. Quantum, 4:254, 2020. arXiv: https://arxiv.org/abs/1906.07115. doi:10.22331/q-2020-04-20-254.

  4. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse hamiltonians. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), 283–292. 2014. arXiv: https://arxiv.org/abs/1312.1414. doi:10.1145/2591796.2591854.

  5. 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.

  6. 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.

  7. 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.

  8. Qi Zhao and Xiao Yuan. Exploiting anticommutation in hamiltonian simulation. Quantum, 5:534, 8 2021. arXiv: https://arxiv.org/abs/2103.07988. URL: https://doi.org/10.22331/q-2021-08-31-534, doi:10.22331/q-2021-08-31-534.

  9. Leonardo Novo and Dominic W Berry. Improved hamiltonian simulation via a truncated taylor series and corrections. Quantum Information and Computation, 17(7&8):623–635, 2017. arXiv: https://arxiv.org/abs/1611.10033. doi:10.26421/QIC17.7-8-5.

  10. Richard Meister, Simon C. Benjamin, and Earl T. Campbell. Tailoring term truncations for electronic structure calculations using a linear combination of unitaries. Quantum, 6:637, 2 2022. arXiv: https://arxiv.org/abs/2007.11624. URL: https://doi.org/10.22331/q-2022-02-02-637, doi:10.22331/q-2022-02-02-637.

  11. Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in second quantization. New Journal of Physics, 18(3):033032, 3 2016. arXiv: https://arxiv.org/abs/1506.01020. URL: https://dx.doi.org/10.1088/1367-2630/18/3/033032, doi:10.1088/1367-2630/18/3/033032.

  12. Ryan Babbush, Dominic W Berry, Yuval R Sanders, Ian D Kivlichan, Artur Scherer, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in the configuration interaction representation. Quantum Science and Technology, 3(1):015006, 2017. arXiv: https://arxiv.org/abs/1506.01029. doi:10.1088/2058-9565/aa9463.

  13. Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush. Fault-tolerant quantum simulations of chemistry in first quantization. PRX Quantum, 2(4):040332, 2021. arXiv: https://arxiv.org/abs/2105.12767. doi:10.1103/PRXQuantum.2.040332.

  14. Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture. arXiv: https://arxiv.org/abs/1805.00675, 2018.