Simulating quantum circuits using tree tensor networks

Philipp Seitz1, Ismael Medina2, Esther Cruz3, Qunsheng Huang1, and Christian B. Mendl1

1Technical University of Munich, Department of Informatics, Boltzmannstraße 3, 85748 Garching, Germany
2University of Göttingen, Campus Institute Data Science
3Max-Planck-Institute of Quantum Optics, Hans-Kopfermann-Straße 1, 85748 Garching, Germany

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


We develop and analyze a method for simulating quantum circuits on classical computers by representing quantum states as rooted tree tensor networks. Our algorithm first determines a suitable, fixed tree structure adapted to the expected entanglement generated by the quantum circuit. The gates are sequentially applied to the tree by absorbing single-qubit gates into leaf nodes, and splitting two-qubit gates via singular value decomposition and threading the resulting virtual bond through the tree. We theoretically analyze the applicability of the method as well as its computational cost and memory requirements, and identify advantageous scenarios in terms of required bond dimensions as compared to a matrix product state representation. The study is complemented by numerical experiments for different quantum circuit layouts up to 37 qubits.

Classical simulations of quantum systems lie at the heart of the quantum supremacy discussion, with tensor network methods being one of the most competitive classical simulation approaches.

In this work, we perform quantum circuit simulations by representing quantum states as tree tensor networks. Our algorithm clusters qubits based on the expected entanglement between them, reducing the computational cost. Two-qubit quantum gates are applied by threading their introduced entanglement, represented as a "virtual bond", through the tree structure.

We conduct theoretical analysis by comparing the computational cost and memory consumption with traditional statevector based simulations under different scenarios. In favorable scenarios, our simulator outperforms the baseline implementation significantly; we see a simulation speedup of up to two magnitudes and a memory reduction by a factor of up to 32x.

► BibTeX data

► References

[1] F. Verstraete, V. Murg, and J. I. Cirac. ``Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems''. Adv. Phys. 57, 143–224 (2008).

[2] U. Schollwöck. ``The density-matrix renormalization group in the age of matrix product states''. Ann. Phys. 326, 96–192 (2011).

[3] Jacob C. Bridgeman and Christopher T. Chubb. ``Hand-waving and interpretive dance: an introductory course on tensor networks''. J. Phys. Math. Theor. 50, 223001 (2017).

[4] Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal. ``What limits the simulation of quantum computers?''. Phys. Rev. X 10, 041038 (2020).

[5] Feng Pan, Pengfei Zhou, Sujie Li, and Pan Zhang. ``Contracting arbitrary tensor networks: general approximate algorithm and applications in graphical models and quantum circuit simulations''. Phys. Rev. Lett. 125, 060503 (2020).

[6] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. ``Classical simulation of quantum supremacy circuits'' (2020). arXiv:2005.06787.

[7] Tianyi Peng, Aram W. Harrow, Maris Ozols, and Xiaodi Wu. ``Simulating large quantum circuits on a small quantum computer''. Phys. Rev. Lett. 125, 150504 (2020).

[8] Johnnie Gray and Stefanos Kourtis. ``Hyper-optimized tensor network contraction''. Quantum 5, 410 (2021).

[9] Feng Pan and Pan Zhang. ``Simulating the sycamore quantum supremacy circuits'' (2021). arXiv:2103.03074.

[10] Danylo Lykov, Roman Schutski, Alexey Galda, Valeri Vinokur, and Yuri Alexeev. ``Tensor network quantum simulator with step-dependent parallelization''. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 582–593. (2022).

[11] G. Vidal. ``Entanglement renormalization''. Phys. Rev. Lett. 99, 220405 (2007).

[12] G. Vidal. ``Class of quantum many-body states that can be efficiently simulated''. Phys. Rev. Lett. 101, 110501 (2008).

[13] V. Murg, F. Verstraete, Ö. Legeza, and R. M. Noack. ``Simulating strongly correlated quantum systems with tree tensor networks''. Phys. Rev. B 82, 205105 (2010).

[14] M. Gerster, P. Silvi, M. Rizzi, R. Fazio, T. Calarco, and S. Montangero. ``Unconstrained tree tensor network: An adaptive gauge picture for enhanced performance''. Phys. Rev. B 90, 125154 (2014).

[15] V. Murg, F. Verstraete, R. Schneider, P. R. Nagy, and Ö. Legeza. ``Tree tensor network state with variable tensor order: An efficient multireference method for strongly correlated systems''. J. Chem. Theory Comput. 11, 1027–1036 (2015).

[16] Klaas Gunst, Frank Verstraete, Sebastian Wouters, Örs Legeza, and Dimitri Van Neck. ``T3NS: Three-legged tree tensor network states''. J. Chem. Theory Comput. 14, 2026–2033 (2018).

[17] Florian Schröder, David Turban, Andrew Musser, Nicholas Hine, and Alex Chin. ``Tensor network simulation of multi-environmental open quantum dynamics via machine learning and entanglement renormalisation''. Nat. Commun. 10 (2019).

[18] L. Tagliacozzo, G. Evenbly, and G. Vidal. ``Simulation of two-dimensional quantum systems using a tree tensor network that exploits the entropic area law''. Phys. Rev. B 80, 235127 (2009).

[19] Gianluca Ceruti, Christian Lubich, and Hanna Walach. ``Time integration of tree tensor networks''. SIAM J. Numer. Anal. 59, 289–313 (2021).

[20] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou. ``Quantum simulation with hybrid tensor networks''. Phys. Rev. Lett. 127, 040501 (2021).

[21] Eugene Dumitrescu. ``Tree tensor network approach to simulating shor's algorithm''. Phys. Rev. A 96, 062322 (2017).

[22] Shi-Ju Ran, Emanuele Tirrito, Cheng Peng, Xi Chen, Luca Tagliacozzo, Gang Su, and Maciej Lewenstein. ``Tensor Network Contractions''. Springer Cham. (2020).

[23] Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. ``Tree tensor networks for generative modeling''. Phys. Rev. B 99, 155131 (2019).

[24] Szilárd Szalay, Max Pfeffer, Valentin Murg, Gergely Barcza, Frank Verstraete, Reinhold Schneider, and Örs Legeza. ``Tensor product methods and entanglement optimization for ab initio quantum chemistry''. Int. J. Quantum Chem. 115, 1342–1391 (2015).

[25] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).

[26] Adam S. Jermyn. ``Efficient tree decomposition of high-rank tensors''. J. Comput. Phys. 377, 142–154 (2019).

[27] Giovanni Ferrari, Giuseppe Magnifico, and Simone Montangero. ``Adaptive-weighted tree tensor networks for disordered quantum many-body systems''. Phys. Rev. B 105, 214201 (2022).

[28] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.

[29] Benjamin F. Schiffer, Jordi Tura, and J. Ignacio Cirac. ``Adiabatic spectroscopy and a variational quantum adiabatic algorithm''. PRX Quantum 3, 020347 (2022).

Cited by

[1] Yaling Ke, "Tree tensor network state approach for solving hierarchical equations of motion", The Journal of Chemical Physics 158 21, 211102 (2023).

[2] Kouichi Okunishi, Hiroshi Ueda, and Tomotoshi Nishino, "Entanglement bipartitioning and tree tensor networks", Progress of Theoretical and Experimental Physics 2023 2, 023A02 (2023).

[3] Toshiya Hikihara, Hiroshi Ueda, Kouichi Okunishi, Kenji Harada, and Tomotoshi Nishino, "Automatic structural optimization of tree tensor networks", Physical Review Research 5 1, 013031 (2023).

[4] Marcel Niedermeier, Jose L. Lado, and Christian Flindt, "Tensor-Network Simulations of Noisy Quantum Computers", arXiv:2304.01751, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-09 12:33:24) and SAO/NASA ADS (last updated successfully 2023-06-09 12:33:25). The list may be incomplete as not all publishers provide suitable and complete citation data.