Skip to content

Hamiltonian simulation

The task of Hamiltonian simulation is to approximately compile the evolution under a Hamiltonian \(H(t)\), for time \(t\), into a sequence of quantum gates. For a time-independent Hamiltonian, solving the Schrödinger equation yields a time evolution operator \(U(t)=e^{-iHt}\). In this section we will discuss the equivalent operator \(U(t) = e^{iHt}\), which is the more common definition in an algorithmic setting. The Hamiltonian of interest can arise from physical systems (e.g., quantum chemistry, condensed matter systems, or quantum field theories) but may also be constructed for other applications, such as differential equation simulation. Quantum simulation does not give full access to the amplitudes of the wavefunction during the simulation, unlike classical approaches based on exact diagonalization (or similar methods). Instead, we are only able to measure observables with respect to the time-evolved state, or use the state as an input to other quantum subroutines. Nevertheless, there are no known efficient classical methods that achieve this for general local or sparse Hamiltonians, suggesting an exponential quantum speedup. In fact, as a quantum computation can be expressed as a time evolution under a sequence of local (time-dependent) Hamiltonians, quantum simulation (i.e. time evolution and measurement of a given observable) is a BQP-complete problem.

Hamiltonian simulation algorithms require access to the Hamiltonian. There are three commonly used input models. The Pauli input model assumes that the Hamiltonian is given classically as a sum of products of Pauli operators, e.g. \(H = \sum_l h_l H_l\), where \(h_l\) are coefficients and \(H_l\) are multiqubit Pauli products. The \(d\)-sparse access model assumes that the Hamiltonian is a sparse matrix with at most \(d\) nonzero elements per row or column. We require that the locations of the nonzero elements and their values are efficient to compute classically. The density matrix access model assumes that the Hamiltonian corresponds to a density matrix, which we are either provided access to copies of [1] or given a unitary that prepares a purification of the density matrix [2]. All of these input models can be used to prepare block-encodings of the Hamiltonian, which provides a standard form access model favored by some algorithms for Hamiltonian simulation (e.g. qubitization with quantum signal processing) [2].

Hamiltonian simulation can be used as a subroutine in a range of algorithms including: quantum phase estimation, quantum linear system solvers, Gibbs state preparation, and the quantum adiabatic algorithm. We remark that some of these algorithms are implicitly using Hamiltonian simulation to provide coherent, unitary access to the Hamiltonian. This can be particularly useful if few ancilla qubits are available, which may inhibit the use of some approaches to coherently access the Hamiltonian (e.g. block-encodings based on linear-combinations of unitaries) but does not prevent the use of Hamiltonian simulation based on product formulae.

Each algorithm has its own advantages and disadvantages, as described at a high level in Table 0.7. Specific optimizations of each algorithm may be available for a given Hamiltonian. One can also consider hybridized methods combining two or more of the algorithms [3, 4, 5, 6, 7, 8]. There are also other methods for Hamiltonian simulation, such as quantum walks [9, 10, 11] or density matrix–based Hamiltonian simulation [1, 12], which we do not discuss, due to their less widespread use as algorithmic primitives for the applications discussed elsewhere in this document.

| | | qDRIFT | Taylor and Dyson series | QSP/QSVT | | :-—–—--—–—--—–—--—-: | :-—–—--—–—--—–—--—–—--—–—--—–—--—–—--—–—--—–—--—–—--: | :-—–—--—–—--—–—--—–—--—–—--—–-: | :-—–—--—–—--—–—--—–—--—–—--—–—--—–—--—-: | :-—–—--—–—--—–—--—–-: | | # Qubits | \(\mathcal{O}\left( n \right)\) | \(\mathcal{O}\left( n \right)\) | \(\mathcal{O}\left( n + \log(\nrm{H}_1 t\epsilon^{-1})\log(L) \right)\) | \(\mathcal{O}\left( n + \log(L) \right)\) | | | | | | | | model | | | | | | Sparse | | | | | | Sparse | | | | | | Sparse | | | | | | Purified density matrix | | | | | | Scaling | \(\mathcal{O}\left( 5^{2k}nL \nrm{H}_1 t \left(\nrm{H}_1 t \epsilon^{-1} \right)^{\frac{1}{2k}} \right)\) | \(\mathcal{O}\left( n\nrm{H}_1^2 t^2\epsilon^{-1} \right)\) | \(\widetilde{\mathcal{O}}\left( \nrm{H}_1 t n L \log(\epsilon^{-1}) \right)\) | | | Pros | | | | | | Simple implementation. | | | | | | Empirical performance. | | | | | | Minimal ancilla qubits. | | | | | | No ancilla qubits. | | | | | | Time-dependent simulations. | | | | | | Few ancilla qubits for algorithm. | | | | | | Cons | | | | | | Exponential prefactor (in order \(k\)). | Scaling with \(t, \epsilon\). | Many ancilla qubits. | | | | Ancilla/gate cost of block-encoding. | | | | |

Table: High-level comparison of Hamiltonian simulation techniques. For the stated complexity, we consider evolution \(U(t)=e^{iHt}\) for time \(t\) under a time-independent Hamiltonian \(H\) on \(n\) qubits, given as a sum of \(L\) Pauli products \(H = \sum_{j=1}^L h_j P_j\). The evolution is approximate to error \(\epsilon\) in the spectral norm (diamond norm for qDRIFT). We define \(\smash{\nrm{H}_1 = \sum_{j=1}^L |h_j|}\). In specific applications it may be possible to reduce the number of qubits and/or gate complexity further by exploiting knowledge of the system, such as symmetries, commutation structure, or energy scales. For example, the factor of \(n\) present in the above complexities may be reduced by exploiting locality in the Pauli product terms of the Hamiltonian.

Bibliography

  1. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631–633, 2014. arXiv: https://arxiv.org/abs/1307.0401. doi:10.1038/nphys3029.

  2. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv: https://arxiv.org/abs/1610.06546. doi:10.22331/q-2019-07-12-163.

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

  4. Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe. Well-conditioned multiproduct hamiltonian simulation. arXiv: https://arxiv.org/abs/1907.11679, 2019.

  5. Yingkai Ouyang, David R. White, and Earl T. Campbell. Compilation by stochastic hamiltonian sparsification. Quantum, 4:235, 2 2020. arXiv: https://arxiv.org/abs/1910.06255. URL: https://doi.org/10.22331/q-2020-02-27-235, doi:10.22331/q-2020-02-27-235.

  6. Matthew Hagan and Nathan Wiebe. Composite quantum simulations. arXiv: https://arxiv.org/abs/2206.06409, 2022.

  7. Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe. Hybridized methods for quantum simulation in the interaction picture. Quantum, 6:780, 2022. arXiv: https://arxiv.org/abs/2109.03308. doi:10.22331/q-2022-08-17-780.

  8. Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee. Time-dependent hamiltonian simulation using discrete clock constructions. arXiv: https://arxiv.org/abs/2203.11353, 2022.

  9. Andrew M. Childs. On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics, 294(2):581–603, 2010. arXiv: https://arxiv.org/abs/0810.0312. doi:10.1007/s00220-009-0930-1.

  10. Dominic W. Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12(1&2):29–62, 2012. arXiv: https://arxiv.org/abs/0910.4157. doi:10.26421/QIC12.1-2.

  11. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), 792–809. 2015. arXiv: https://arxiv.org/abs/1501.01715. doi:10.1109/FOCS.2015.54.

  12. Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(1):13, 2017. arXiv: https://arxiv.org/abs/1608.00281. doi:10.1038/s41534-017-0013-7.