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] Alexander Cowtan, Will Simmons, and Ross Duncan, "A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz", arXiv:2007.10515.

The above citations are from SAO/NASA ADS (last updated successfully 2020-09-22 11:22:35). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2020-09-22 11:22:34).