Simulating Quantum Circuits Using Tree Tensor Networks

Abstract

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.

Featured image: Tree Tensor Network with quantum pates.

Popular summary

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

@article{Seitz2023simulatingquantum, doi = {10.22331/q-2023-03-30-964}, url = {https://doi.org/10.22331/q-2023-03-30-964}, title = {Simulating quantum circuits using tree tensor networks}, author = {Seitz, Philipp and Medina, Ismael and Cruz, Esther and Huang, Qunsheng and Mendl, Christian B.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {964}, month = mar, year = {2023}<br /> }

► 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).
https://doi.org/10.1080/14789940801912366

[2] U. Schollwöck. “The density-matrix renormalization group in the age of matrix product states”. Ann. Phys. 326, 96–192 (2011).
https://doi.org/10.1016/j.aop.2010.09.012

[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).
https://doi.org/10.1088/1751-8121/aa6dc3

[4] Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal. “What limits the simulation of quantum computers?”. Phys. Rev. X 10, 041038 (2020).
https://doi.org/10.1103/physrevx.10.041038

[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).
https://doi.org/10.1103/PhysRevLett.125.060503

[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.
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).
https://doi.org/10.1103/PhysRevLett.125.150504

[8] Johnnie Gray and Stefanos Kourtis. “Hyper-optimized tensor network contraction”. Quantum 5, 410 (2021).
https://doi.org/10.22331/q-2021-03-15-410

[9] Feng Pan and Pan Zhang. “Simulating the sycamore quantum supremacy circuits” (2021). arXiv:2103.03074.
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).
https://doi.org/10.1109/QCE53715.2022.00081

[11] G. Vidal. “Entanglement renormalization”. Phys. Rev. Lett. 99, 220405 (2007).
https://doi.org/10.1103/PhysRevLett.99.220405

[12] G. Vidal. “Class of quantum many-body states that can be efficiently simulated”. Phys. Rev. Lett. 101, 110501 (2008).
https://doi.org/10.1103/PhysRevLett.101.110501

[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).
https://doi.org/10.1103/physrevb.82.205105

[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).
https://doi.org/10.1103/PhysRevB.90.125154

[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).
https://doi.org/10.1021/ct501187j

[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).
https://doi.org/10.1021/acs.jctc.8b00098

[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).
https://doi.org/10.1038/s41467-019-09039-7

[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).
https://doi.org/10.1103/PhysRevB.80.235127

[19] Gianluca Ceruti, Christian Lubich, and Hanna Walach. “Time integration of tree tensor networks”. SIAM J. Numer. Anal. 59, 289–313 (2021).
https://doi.org/10.1137/20M1321838

[20] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou. “Quantum simulation with hybrid tensor networks”. Phys. Rev. Lett. 127, 040501 (2021).
https://doi.org/10.1103/PhysRevLett.127.040501

[21] Eugene Dumitrescu. “Tree tensor network approach to simulating shor’s algorithm”. Phys. Rev. A 96, 062322 (2017).
https://doi.org/10.1103/PhysRevA.96.062322

[22] Shi-Ju Ran, Emanuele Tirrito, Cheng Peng, Xi Chen, Luca Tagliacozzo, Gang Su, and Maciej Lewenstein. “Tensor Network Contractions”. Springer Cham. (2020).
https://doi.org/10.1007/978-3-030-34489-4

[23] Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. “Tree tensor networks for generative modeling”. Phys. Rev. B 99, 155131 (2019).
https://doi.org/10.1103/PhysRevB.99.155131

[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).
https://doi.org/10.1002/qua.24898

[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).
https://doi.org/10.1038/s41586-019-1666-5

[26] Adam S. Jermyn. “Efficient tree decomposition of high-rank tensors”. J. Comput. Phys. 377, 142–154 (2019).
https://doi.org/10.1016/j.jcp.2018.10.026

[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).
https://doi.org/10.1103/PhysRevB.105.214201

[28] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028.
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).
https://doi.org/10.1103/PRXQuantum.3.020347

Cited by

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-31 10:58:04). 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 2023-03-31 10:58:02).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Generative Data Intelligence

Simulating quantum circuits using tree tensor networks

Abstract

Popular summary

► BibTeX data

► References

Cited by

DOJ insists Tornado Cash operated as a ‘commercial enterprise’

Top 8 ICOs for 2024: BlockDAG Leads with Record-Breaking Presale

Latest Intelligence

BDAG’s $20.7M Presale, Eclipsing Galaxy Fox Debut

Upbit Dominates South Korea’s Crypto Market, Ranking Top 5 Globally: Report

Justin Biever’s NFT Portfolio Lost Over 94% of Its Value, Gong from $2 Million to $100,000

Solana Witnessing ‘Dramatic Increase’ in Investor Allocations This Year, According to New CoinShares Survey – The Daily Hodl

CFI, Deriv, Gold-i and More: Executive Moves of the Week

Best Undrafted Free Agents From the 2024 NFL Draft

Chat with us