Quantum Hamiltonian Simulation

This blog is jointly written with Mostafizur Rahaman

"Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly, it’s a wonderful problem, because it doesn’t look so easy". - Richard Feynman

The above phrase [1],[2] perfectly captures the spirit of Quantum Hamiltonian Simulation (QHS) by highlighting the necessity of using quantum technologies to effectively simulate the intricacies of the natural world. By allowing the simulation of molecular interactions to be efficient it holds the potential to revolutionize multiple fields including chemistry, material sciences, complex optimizations, and drug discovery. Thus QHS is one of the main quantum sub-routines used in many quantum algorithms. Given a quantum system (often called a Hamiltonian), QHS helps to get its time-evolution operator. It helps in studying the underlying properties of the Hamiltonian such as its eigenvalue estimation and system evolution.

Quantum simulation efforts have long aimed to understand the evolution of quantum wave functions over time. However, directly calculating the time evolution operator for these systems involves a matrix exponential with complex coefficients, making it a highly challenging task [3]. Consequently, there emerged a need for algorithms that could approximate this exponential, making the process more feasible while maintaining acceptable error levels. This need for new algorithms was particularly driven by Hamiltonian operators related to atomic particles, which contain nonlocal terms. [4], [5].

The Challenge

The key challenge in quantum Hamiltonian simulation is the efficient approximation of the evolution operator for a given Hamiltonian.

In the Hamiltonian simulation, the aim is to devise an efficient algorithm that prepares an approximate unitary operator U for the Hamiltonian operator H. This approximation should satisfy the condition || U ? e^{-iHt}|| ≤ ε, where ε > 0 denotes a finite and bounded precision, and t represents the evolution time [6]. Notably, the perfect evolution operator U = e^{-iHt} is derived by solving Schrodinger’s wave equation. When encoded in a quantum circuit with n qubits, both matrices H and U have dimensions of 2^n x 2^n.

The discussion ahead will delve into significant milestones within quantum Hamiltonian simulation (QHS) algorithms, employing a comparative approach. It's crucial to note that these algorithms stem from distinct underlying assumptions, which can be further elucidated by referencing respective literature sources.

Exploring the background

The Sum of Local Hamiltonian (SLH) approach decomposes the system's Hamiltonian into local terms, efficiently simulating sparse Hamiltonian systems with limited qubit interactions. It maintains polynomial time complexity and poly-logarithmic gate complexity, making it suitable for various problems. SLH excels in systems with sparse interactions but may be less efficient for highly entangled systems [7].

The product-based approach, often paired with Trotterization, decomposes a complex Hamiltonian into simpler unitary operators, simplifying quantum state evolution. Trotterization approximates the unitary evolution operator through Trotter steps, improving accuracy with increasing step count. The Suzuki-Trotter decomposition enhances accuracy via higher-order approximations [8], [9]. This method is versatile and handles various Hamiltonians efficiently, even on resource-limited quantum computers, though it introduces approximations that can impact accuracy over extended evolution times[10].

Linear Combination of Unitaries (LCU) method is potent for simulating quantum systems governed by complex Hamiltonians [11]. LCU ex-presses the Hamiltonian as a linear combination of unitary operators, offering flexibility with linear time complexity in the number of terms and polynomial query complexity. It efficiently captures quantum system behavior but requires precise knowledge for accurate simulation [12].

The Truncated Taylor series Approach (TSA) approximates quantum system evolution by truncating the Taylor series expansion of the unitary evolution operator. This method is effective for systems with time-dependent Hamiltonians, balancing accuracy and computational complexity with truncation order[13]. TSA’s complexity scales with truncation order and step count, making it suitable for quantum chemistry and dynamics simulations [14].

Quantum Signal Processing (QSP) applies classical signal processing techniques to quantum computing, simulating systems governed by time-independent Hamiltonians [15]. It constructs quantum circuits to emulate a target Hamiltonian’s behavior through quantum signal processing operations. QSP is efficient, utilizing relatively few quantum resources for precise control over quantum state evolution, making it suitable for specific quantum simulations [16]. However, it may not be optimal for time-dependent Hamiltonians, necessitating alternative techniques, and can grow complex with increasing precision and problem size [17].

Computational Complexity

Quantum Hamiltonian simulation (QHS) algorithms play a pivotal role in quantum computing, with their query complexities offering a key comparison metric. Initially, these algorithms are predominantly focused on theoretical exploration due to the unavailability of practical quantum computers. Hence, comparing QHS algorithms primarily involves assessing their query complexities.

Various QHS methods have been developed, each with distinct query complexities. The Sum of Local Hamiltonian (SLH) approach offers efficient simulation for sparse Hamiltonians. The Trotter formula and Truncated Taylor series approach (TSA) are widely used due to their practical gate-level integration. The Linear Combination of Unitaries (LCU)method is favored for its ease of implementation, while the Quantum Walk (QW) algorithm, quantization, and Quantum Signal Processing (QSP) method provide promising results but face implementation challenges on current quantum hardware [15], [17]–[20], [22].

QHS algorithms’ query complexities are influenced by factors such as matrix sparsity (d), qubitsize (n), and precision (ε). For instance, the method’s query complexity scales polynomially with the system size and Hamiltonian norm. The Trotter formula and TSA methods offer query complexities that balance accuracy and computational cost. LCU’s complexity scales with the logarithm of the input size, while QSP offers an efficient approach with logarithmic complexity in the precision parameter [8], [9], [21], [23], [24].

In recent years, quantum gate complexity (QGC) has become a critical parameter for evaluating quantum algorithms. Minimizing QGC is crucial for resource assessment, algorithm selection, scaling behavior, practical error estimation, identifying quantum advantages, and optimizing resource consumption. Comparing QGCs of various methods helps in selecting the most efficient algorithm for a given task, ensuring feasibility on existing or near-term quantum hardware. While QW, qubitization, and QSP methods exhibit favorable query complexities, Trotterization, LCU, and TSA approaches are preferred for practical Hamiltonian simulations due to their reliable gate-level integration [20], [25].

Applications and implementation with IBM's Qiskit

Quantum Hamiltonian simulations (QHS) address time evolution problems in various fields. They can model chemical reaction dynamics [26]–[28], protein folding (link to the LinkedIn blog), and condensed matter physics [29]. A variant for QHS where the evolution happens in imaginary time(QITE) is used to estimate the ground state of a wide range of Hamiltonians [30]. Not restricting its application to chemical physics QHS also extends to engineering applications, including simulating communication channel matrices and automotive systems [31]. This capability makes QHS essential for advancing both scientific research and practical technologies.

To get started with the implementation of QHS in Qiskit please follow this link to the tutorial. In this tutorial, you will learn how to construct operators, create quantum circuits, create the propagator, and finally approximate the propagator using the Pauli-Trotter formalism. Beware this notebook is compatible with older versions of Qiskit (26.0) and to make it work you will either need to create an environment with an older version or make this notebook compatible with newer versions using this migration guide.

References

[1] A. Hey, Feynman and Computation. CRC Press, 2018.

[2] T. Gramss, “Solving the Schrodinger Equation for the Feyn- man Quantum Computer,” International Journal of Theoretical Physics, vol. 37, no. 5, pp. 1423–1439, 1998.

[3] M. A. Nielsen, M. J. Bremner, J. L. Dodd, A. M. Childs, and C. M. Dawson, “Universal Simulation of Hamiltonian Dynamics for Quantum Systems with Finite-Dimensional State Spaces,” Physical Review A, vol. 66, no. 2, p. 022317, 2002.

[4] S. Lloyd, “Universe as Quantum Computer,” Complexity, vol. 3, no. quant-ph/9912088, pp. 32–35, 1997.

[5] G. Brassard, I. Chuang, S. Lloyd, and C. Monroe, “Quantum Computing,” Proceedings of the National Academy of Sciences, vol. 95, no. 19, pp. 11032–11033, 1998.

[6] R. Kothari, “Efficient Algorithms in Quantum Query Complexity,” 2014.

[7] J. Kempe, A. Kitaev, and O. Regev, “The Complexity of the Local Hamiltonian Problem,” Siam Journal on Computing, vol. 35, no. 5, pp. 1070–1097, 2006.

[8] R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe, “Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation,” Physical Review A, vol. 91, no. 2, p. 022311, 2015.

[9] S. Zhuk, N. Robertson, and S. Bravyi, “Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation,” arXiv preprint arXiv:2306.12569, 2023.

[10] C.-P. Chou, F. Pollmann, and T.-K. Lee, “Matrix-Product-based Projected Wave Functions Ansatz for Quantum Many-Body Ground States,” Physical Review B, vol. 86, no. 4, p. 041105, 2012.

[11] A. M. Childs and N. Wiebe, “Hamiltonian Simulation using Linear Combinations of Unitary Operations,” arXiv preprint arXiv:1202.5822, 2012.

[12] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, “Unitary Partitioning Approach to the Measurement Problem in the Variational Quantum Eigensolver Method,” Journal of Chemical Theory and Computation, vol. 16, no. 1, pp. 190– 195, 2019.

[13] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, “Simulating Hamiltonian Dynamics with a Truncated Taylor Series,” Physical Review Letters, vol. 114, no. 9, p. 090502, 2015.

[14] L. Novo and D. W. Berry, “Improved Hamiltonian Simulation via a Truncated Taylor Series and Corrections,” arXiv preprint arXiv:1611.10033, 2016.

[15] Low, Guang Hao and Chuang, Isaac L, “Optimal Hamiltonian Simulation by Quantum Signal Processing,” Physical Review Letters, vol. 118, no. 1, p. 010501, 2017.

[16] Y. Dong, X. Meng, K. B. Whaley, and L. Lin, “Efficient Phase- Factor Evaluation in Quantum Signal Processing,” Physical Review A, vol. 103, no. 4, p. 042419, 2021.

[17] D. Motlagh and N. Wiebe, “Generalized Quantum Signal Processing,” arXiv preprint arXiv:2308.01501, 2023.

[18] A. M. Childs and R. Kothari, “Simulating Sparse Hamiltonians with Star Decompositions,” in Conference on Quantum Computation, Communication, and Cryptography, pp. 94–103, Springer, 2010.

[19] D. W. Berry and A. M. Childs, “Black-Box Hamiltonian Simulation and Unitary Implementation,” arXiv preprint arXiv:0910.4157, 2009.

[20] D. W. Berry, A. M. Childs, and R. Kothari, “Hamiltonian Simulation with Nearly Optimal Dependence on All Parameters,” in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 792–809, IEEE, 2015.

[21] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, “To- ward the First Quantum Simulation with Quantum Speedup,” Proceedings of the National Academy of Sciences, vol. 115, no. 38, pp. 9456–9461, 2018.

[22] G. H. Low and I. L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum, vol. 3, p. 163, 2019.

[23] H. De Raedt and B. De Raedt, “Applications of the generalized Trotter formula,” Physical Review A, vol. 28, no. 6, p. 3575, 1983.

[24] N. Wiebe, D. Berry, P. H?yer, and B. C. Sanders, “Higher Order Decompositions of Ordered Operator Exponentials,” Journal of Physics A: Mathematical and Theoretical, vol. 43, no. 6, p. 065203, 2010.

[25] S. Shokri, S. Rafibakhsh, R. Pooshgan, and R. Faeghi, “Implementation of a Quantum Algorithm to Estimate the Energy of a Particle in a Finite Square Well Potential on IBM Quantum Computer,” The European Physical Journal Plus, vol. 136, pp. 1–18, 2021.

[26] M. R. Laskar, A. Bhattacharya, and K. Dasgputa, “Efficient simulation of potential energy operators on quantum hardware: a study on sodium iodide (NaI),” Scientific Reports, vol. 14, no. 1, p. 10831, 2024.

[27] S. S. Kale and S. Kais, “Simulation of chemical reactions on a quantum computer,” The Journal of Physical Chemistry Letters, vol. 15, pp. 5633–5642, 2024.

[28] S. S. Kale, Y. P. Chen, and S. Kais, “Constructive quantum interference in photochemical reactions,” Journal of Chemical Theory and Computation, vol. 17, no. 12, pp. 7822–7826, 2021.

[29] M. Sajjan, R. Gupta, S. S. Kale, V. Singh, K. Kumaran, and S. Kais, “Physics-inspired quantum simulation of resonating valence bond states a prototypical template for a spin-liquid ground state,” The Journal of Physical Chemistry A, vol. 127, no. 41, pp. 8751–8764, 2023.

[30] M. Motta, C. Sun, A. T. Tan, M. J. O’rourke, E. Ye, A. J. Minnich, F. G. Brandao, and G. K.-L. Chan, “Quantum imaginary time evolution, quantum lanczos, and quantum thermal averaging,” arXiv preprint arXiv:1901.07653, vol. 10, 2019.

[31] M. R. Laskar, S. Mondal, and A. K. Dutta, “A Low Complexity Quantum Simulation Framework for Toeplitz-Structured Matrix and its Application in Signal Processing,” IEEE Transactions on Quantum Engineering, pp. 1–23, 2023.