# Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters

Ewout van den Berg and Kristan Temme

IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY, USA

### Abstract

Many applications of practical interest rely on time evolution of Hamiltonians that are given by a sum of Pauli operators. Quantum circuits for exact time evolution of single Pauli operators are well known, and can be extended trivially to sums of commuting Paulis by concatenating the circuits of individual terms. In this paper we reduce the circuit complexity of Hamiltonian simulation by partitioning the Pauli operators into mutually commuting clusters and exponentiating the elements within each cluster after applying simultaneous diagonalization. We provide a practical algorithm for partitioning sets of Paulis into commuting subsets, and show that the proposed approach can help to significantly reduce both the number of ${CNOT}$ operations and circuit depth for Hamiltonians arising in quantum chemistry. The algorithms for simultaneous diagonalization are also applicable in the context of stabilizer states; in particular we provide novel four- and five-stage representations, each containing only a single stage of conditional gates.

### ► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, (70): 052328, 2004. 10.1103/​PhysRevA.70.052328.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[2] Héctor Abraham, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, et al. Qiskit: An open-source framework for quantum computing, 2019. URL https:/​/​qiskit.org.
https:/​/​qiskit.org

[3] Matthew Amy and Michele Mosca. T-Count optimization and Reed-Muller codes. IEEE Transactions on Information Theory, 65 (8): 4771–4784, 2019. 10.1109/​TIT.2019.2906374.
https:/​/​doi.org/​10.1109/​TIT.2019.2906374

[4] Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33 (10): 1476–1489, 2014. 10.1109/​TCAD.2014.2341953.

[5] Elwyn R. Berlekamp. The technology of error-correcting codes. Proceedings of the IEEE, 68 (5), 1980. 10.1109/​PROC.1980.11696.
https:/​/​doi.org/​10.1109/​PROC.1980.11696

[6] Dominic. W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information & Computation, 12 (1&2): 29–62, 2012.

[7] 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. 10.1103/​PhysRevLett.114.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[8] Béla Bollobás. Modern graph theory, volume 184 of Graduate texts in mathematics. Springer Science & Business Media, New York, USA, 2013. 10.1007/​978-1-4612-0619-4.
https:/​/​doi.org/​10.1007/​978-1-4612-0619-4

[9] Xavier Bonet-Monroig, Ryan Babbush, and Thomas E O'Brien. Nearly optimal measurement scheduling for partial tomography of quantum states. arXiv:1908.05628, 2019. URL https:/​/​arxiv.org/​abs/​1908.05628.
arXiv:1908.05628

[10] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the Clifford group. arXiv:2003.09412, 2020. URL https:/​/​arxiv.org/​abs/​2003.09412.
arXiv:2003.09412

[11] Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210–226, 2002. 10.1006/​aphy.2002.6254.
https:/​/​doi.org/​10.1006/​aphy.2002.6254

[12] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unary operators. Quantum Information & Computation, 12 (11& 12): 901–924, 2012.

[13] Andrew M. Childs, Dmitri Maslov, Yonseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. PNAS, 115 (38): 9456–9461, 2018. 10.1073/​pnas.1801723115.
https:/​/​doi.org/​10.1073/​pnas.1801723115

[14] Kenny Choo, Antonio Mezzacapo, and Giuseppe Carleo. Fermionic neural-network states for ab-initio electronic structure. Nature Communications, 11 (1): 2368, 2020. 10.1038/​s41467-020-15724-9.
https:/​/​doi.org/​10.1038/​s41467-020-15724-9

[15] Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley. Efficient quantum measurement of Pauli operators in the presence of finite sampling error. arXiv:1908.06942, 2019. URL https:/​/​arxiv.org/​abs/​1908.06942.
arXiv:1908.06942

[16] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6–7): 467–488, 1982. 10.1007/​BF02650179.
https:/​/​doi.org/​10.1007/​BF02650179

[17] Héctor J. García, Igor L. Markov, and Andrew W. Cross. Efficient inner-product algorithm for stabilizer states. arXiv:1210.6646, 2013. URL https:/​/​arxiv.org/​abs/​1210.6646.
arXiv:1210.6646

[18] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T. Chong. Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. arXiv:1907.13623, 2019. URL https:/​/​arxiv.org/​abs/​1907.13623.
arXiv:1907.13623

[19] Daniel Gottesman. The Heisenberg representation of quantum computers. In Proceedings of the 22nd International Colloquium on Group Theoretical Methods in Physics – GROUP22 ICGTMP98, pages 32–43, Cambridge, MA, 1998. International Press. URL https:/​/​arxiv.org/​abs/​quant-ph/​9807006.
arXiv:quant-ph/9807006

[20] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), pages 11––15, August 2008.

[21] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge university press, 1985. 10.1017/​CBO9780511810817.
https:/​/​doi.org/​10.1017/​CBO9780511810817

[22] Andrew Jena, Scott Genin, and Michele Mosca. Pauli partitioning with respect to gate sets. arXiv:1907.07859, 2019. URL https:/​/​arxiv.org/​abs/​1907.07859.
arXiv:1907.07859

[23] Pascual Jordan and Eugene Wigner. Über das Paulische Äquivalenzverbot. Zeitschrift für Physik, 47 (9–10): 631–651, 1928. 10.1007/​978-3-662-02781-3_9.
https:/​/​doi.org/​10.1007/​978-3-662-02781-3_9

[24] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242–246, 2017. 10.1038/​nature23879.
https:/​/​doi.org/​10.1038/​nature23879

[25] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, 1996. 10.1126/​science.273.5278.1073.
https:/​/​doi.org/​10.1126/​science.273.5278.1073

[26] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118 (1): 010501, 2017. 10.1103/​PhysRevLett.118.010501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501

[27] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[28] Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits. Quantum Information & Computation, 8 (3&4): 282–294, 2008.

[29] Rahul Sarkar and Ewout van den Berg. On sets of commuting and anticommuting Paulis. arXiv:1909.08123, 2019. URL https:/​/​arxiv.org/​abs/​1909.08123.
arXiv:1909.08123

[30] Masuo Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics. Journal of Mathematical Physics, 32 (2): 400–407, February 1991. 10.1063/​1.529425.
https:/​/​doi.org/​10.1063/​1.529425

[31] Attila Szabo and Neil S. Ostlund. Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. McGraw-Hill, 1989.

[32] Andrew Tranter, Peter J. Love, Florian Mintert, and Peter V. Coveney. A comparison of the Bravyi-Kitaev and Jordan-Wigner transformations for the quantum simulation of quantum chemistry. Journal of Chemical Theory and Computation, 14 (11): 5617–5630, 2018. 10.1021/​acs.jctc.8b00450.
https:/​/​doi.org/​10.1021/​acs.jctc.8b00450

[33] Hale F. Trotter. On the product of semi-groups of operators. Proc. Am. Math. Soc., 10 (4): 545–551, 1959. 10.2307/​2033649.
https:/​/​doi.org/​10.2307/​2033649

[34] Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F. Izmaylov. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. The Journal of Chemical Physics, 152 (12): 124114, 2020. 10.1063/​1.5141458.
https:/​/​doi.org/​10.1063/​1.5141458

[35] Tzu-Ching Yen, Vladyslav Verteletskyi, and Artur F. Izmaylov. Measuring all compatible operators in one series of a single-qubit measurements using unitary transformations. Journal of Chemical Theory and Computation, 16 (4): 2400–2409, 2020. 10.1021/​acs.jctc.0c00008.
https:/​/​doi.org/​10.1021/​acs.jctc.0c00008

### Cited by

[1] Abhinav Anand, Philipp Schleich, Sumner Alperin-Lea, Phillip W. K. Jensen, Sukin Sim, Manuel Díaz-Tinoco, Jakob S. Kottmann, Matthias Degroote, Artur F. Izmaylov, and Alán Aspuru-Guzik, "A quantum computing view on unitary coupled cluster theory", Chemical Society Reviews 51 5, 1659 (2022).

[2] Lingling Lao and Dan E. Browne, Proceedings of the 49th Annual International Symposium on Computer Architecture 351 (2022) ISBN:9781450386104.

[3] Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).

[4] Simon Martiel and Timothée Goubault de Brugière, "Architecture aware compilation of quantum circuits via lazy synthesis", Quantum 6, 729 (2022).

[5] Will Simmons, "Relating Measurement Patterns to Circuits via Pauli Flow", Electronic Proceedings in Theoretical Computer Science 343, 50 (2021).

[6] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov, "Clifford Circuit Optimization with Templates and Symbolic Pauli Gates", Quantum 5, 580 (2021).

[7] Gushu Li, Anbang Wu, Yunong Shi, Ali Javadi-Abhari, Yufei Ding, and Yuan Xie, Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems 554 (2022) ISBN:9781450392051.

[8] Mitali Sisodia, Abhishek Shukla, Alexandre A.A. de Almeida, Gerhard W. Dueck, and Anirban Pathak, "A method to improve quantum state fidelity in circuits executed on IBM’s quantum computers", Canadian Journal of Physics 99 10, 924 (2021).

[9] Teague Tomesh, Kaiwen Gui, Pranav Gokhale, Yunong Shi, Frederic T. Chong, Margaret Martonosi, and Martin Suchara, 2021 International Conference on Rebooting Computing (ICRC) 1 (2021) ISBN:978-1-6654-2332-8.

[10] Alexander Cowtan, Will Simmons, and Ross Duncan, "A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz", arXiv:2007.10515.

[11] Yoshiaki Kawase and Keisuke Fujii, "Fast Classical Simulation of Hamiltonian Dynamics by Simultaneous Diagonalization Using Clifford Transformation with Parallel Computation", arXiv:2206.11664.

The above citations are from Crossref's cited-by service (last updated successfully 2022-10-04 00:04:26) and SAO/NASA ADS (last updated successfully 2022-10-04 14:47:34). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2022-10-04 14:47:33: Could not fetch cited-by data for 10.22331/q-2020-09-12-322 from Crossref. This is normal if the DOI was registered recently.