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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

► BibTeX data

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, (70): 052328, 2004. 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:/​/​

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

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

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

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

[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:/​/​​abs/​1908.05628.

[10] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the Clifford group. arXiv:2003.09412, 2020. URL https:/​/​​abs/​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.

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

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

[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:/​/​​abs/​1908.06942.

[16] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6–7): 467–488, 1982. 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:/​/​​abs/​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:/​/​​abs/​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:/​/​​abs/​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.

[22] Andrew Jena, Scott Genin, and Michele Mosca. Pauli partitioning with respect to gate sets. arXiv:1907.07859, 2019. URL https:/​/​​abs/​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.

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

[25] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, 1996. 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.

[27] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 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:/​/​​abs/​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.

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

[33] Hale F. Trotter. On the product of semi-groups of operators. Proc. Am. Math. Soc., 10 (4): 545–551, 1959. 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.

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

Cited by

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

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

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

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

[5] Andrei Alexandru, Paulo F. Bedaque, Andrea Carosso, Michael J. Cervia, Edison M. Murairi, and Andy Sheng, "Fuzzy gauge theory for quantum computers", Physical Review D 109 9, 094502 (2024).

[6] 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).

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

[8] Michael Fromm, Owe Philipsen, Wolfgang Unger, and Christopher Winterowd, "Quantum gate sets for lattice QCD in the strong-coupling limit: $N_{f}=1$", EPJ Quantum Technology 11 1, 24 (2024).

[9] Boris Arseniev, Dmitry Guskov, Richik Sengupta, Jacob Biamonte, and Igor Zacharov, "Tridiagonal matrix decomposition for Hamiltonian simulation on a quantum computer", Physical Review A 109 5, 052627 (2024).

[10] 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).

[11] Yuxiang Peng, Jacob Young, Pengyu Liu, and Xiaodi Wu, "SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation", Proceedings of the ACM on Programming Languages 8 POPL, 2425 (2024).

[12] Edison M. Murairi, Michael J. Cervia, Hersh Kumar, Paulo F. Bedaque, and Andrei Alexandru, "How many quantum gates do gauge theories require?", Physical Review D 106 9, 094504 (2022).

[13] Ignacio Loaiza, Alireza Marefat Khah, Nathan Wiebe, and Artur F Izmaylov, "Reducing molecular electronic Hamiltonian simulation cost for linear combination of unitaries approaches", Quantum Science and Technology 8 3, 035019 (2023).

[14] Igor O. Sokolov, Werner Dobrautz, Hongjun Luo, Ali Alavi, and Ivano Tavernelli, "Orders of magnitude increased accuracy for quantum many-body problems on quantum computers via an exact transcorrelated method", Physical Review Research 5 2, 023174 (2023).

[15] Edison M. Murairi and Michael J. Cervia, "Reducing circuit depth with qubitwise diagonalization", Physical Review A 108 6, 062414 (2023).

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

[17] Priyanka Mukhopadhyay, Nathan Wiebe, and Hong Tao Zhang, "Synthesizing efficient circuits for Hamiltonian simulation", npj Quantum Information 9 1, 31 (2023).

[18] Luis A. Martínez-Martínez, Tzu-Ching Yen, and Artur F. Izmaylov, "Assessment of various Hamiltonian partitionings for the electronic structure problem on a quantum computer using the Trotter approximation", Quantum 7, 1086 (2023).

[19] Priyanka Mukhopadhyay, "Synthesis of V-count-optimal quantum circuits for multiqubit unitaries", Physical Review A 109 5, 052619 (2024).

[20] Lieuwe Vinkhuijzen, Tim Coopmans, David Elkouss, Vedran Dunjko, and Alfons Laarman, "LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States", Quantum 7, 1108 (2023).

[21] Sergey Bravyi, Dmitri Maslov, and Yunseong Nam, "Constant-Cost Implementations of Clifford Operations and Multiply-Controlled Gates Using Global Interactions", Physical Review Letters 129 23, 230501 (2022).

[22] 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.

[23] Lane G. Gunderman, "Transforming collections of Pauli operators into equivalent collections of Pauli operators over minimal registers", Physical Review A 107 6, 062416 (2023).

[24] Daniel Volya and Prabhat Mishra, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 1394 (2023) ISBN:979-8-3503-4323-6.

[25] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

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

[27] Yoshiaki Kawase and Keisuke Fujii, "Fast classical simulation of Hamiltonian dynamics by simultaneous diagonalization using Clifford transformation with parallel computation", Computer Physics Communications 288, 108720 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-24 18:44:45) and SAO/NASA ADS (last updated successfully 2024-05-24 18:44:46). The list may be incomplete as not all publishers provide suitable and complete citation data.