Hyper-optimized tensor network contraction

Johnnie Gray1,2 and Stefanos Kourtis1,3,4

1Blackett Laboratory, Imperial College London, London SW7 2AZ, United Kingdom
2Division of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, California 91125, USA
3Department of Physics, Boston University, Boston, MA, 02215, USA
4Institut quantique & Département de physique, Université de Sherbrooke, Québec J1K 2R1, Canada

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


Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000$\times$ compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.

Tensor networks offer a universal language that can express a large variety of scientific concepts, from partition functions to quantum circuits. Tensor network contraction can be a practical method for addressing computational challenges, such as the solution of hard constraint satisfaction problems or the simulation and benchmarking of quantum computation on classical computers. The core task of contracting a tensor network is exponentially sensitive to the quality of a so-called contraction tree, which describes a series of pairwise merges that turn the network into a single tensor. We tackle this problem with three key techniques. Firstly, we re-conceive the tensor network as a hyper-graph and use hyper-graph partitioning to build the tree. Secondly, we introduce various simplification schemes to prepare the tensor network for contraction. Finally, we use a Bayesian optimizer that intelligently learns to build ever better trees for a particular contraction. We show vastly improved performance for a variety of problems, including the simulation of Google's Sycamore circuits, the simulation of the quantum approximate optimization algorithm, as well as the solution of weighted model counting problems. For accessible sizes, the paths we find are very close to optimal.

► BibTeX data

► References

[1] F. Verstraete, V. Murg, and J. Cirac, Adv. Phys. 57, 143 (2008).

[2] R. Orús, Ann. Phys. (N. Y). 349, 117 (2014).

[3] J. C. Bridgeman and C. T. Chubb, J. Phys. A Math. Theor. 50, 223001 (2017).

[4] J. D. Biamonte and V. Bergholm, arXiv:1708.00006 (2017), arXiv:1708.00006.

[5] M. Levin and C. P. Nave, Phys. Rev. Lett. 99, 120601 (2007).

[6] G. Evenbly and G. Vidal, Phys. Rev. Lett. 115, 180405 (2015).

[7] G. Evenbly, Phys. Rev. B 95, 045117 (2017).

[8] A. Cichocki, N. Lee, I. Oseledets, A.-H. Phan, Q. Zhao, and D. P. Mandic, Found. Trends Mach. Learn. 9, 249 (2016).

[9] A. Cichocki, N. Lee, I. Oseledets, A.-H. Phan, Q. Zhao, M. Sugiyama, and D. P. Mandic, Found. Trends Mach. Learn. 9, 431 (2017).

[10] L. Dueñas-Osorio, M. Y. Vardi, and J. Rojo, Struct. Saf. 75, 110 (2018).

[11] I. L. Markov and Y. Shi, SIAM J. Comput. 38, 963 (2008).

[12] E. Stoudenmire and D. J. Schwab, in Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (Curran Associates, Inc., 2016) pp. 4799–4807.

[13] E. M. Stoudenmire, Quantum Sci. Technol. 3, 034003 (2018).

[14] C. Roberts, A. Milsted, M. Ganahl, A. Zalcman, B. Fontaine, Y. Zou, J. Hidary, G. Vidal, and S. Leichenauer, arXiv:1905.01330 (2019), arXiv:1905.01330.

[15] H. C. Jiang, Z. Y. Weng, and T. Xiang, Phys. Rev. Lett. 101, 090603 (2008).

[16] Z.-C. Gu and X.-G. Wen, Phys. Rev. B 80, 155131 (2009).

[17] Z. Y. Xie, J. Chen, M. P. Qin, J. W. Zhu, L. P. Yang, and T. Xiang, Phys. Rev. B 86, 045139 (2012).

[18] H.-H. Zhao, Z. Y. Xie, T. Xiang, and M. Imada, Phys. Rev. B 93, 125115 (2016).

[19] M. Bal, M. Mariën, J. Haegeman, and F. Verstraete, Phys. Rev. Lett. 118, 250602 (2017).

[20] S. Yang, Z.-C. Gu, and X.-G. Wen, Phys. Rev. Lett. 118, 110504 (2017).

[21] Y.-Y. Shi, L.-M. Duan, and G. Vidal, Phys. Rev. A 74, 022320 (2006).

[22] L. G. Valiant, SIAM J. Comput. 37, 1565 (2008).

[23] S. Bravyi, Contemp. Math. 482, 179 (2008), arXiv:0801.2989.

[24] M. Aguado and G. Vidal, Phys. Rev. Lett. 100, 070404 (2008).

[25] R. König, B. W. Reichardt, and G. Vidal, Phys. Rev. B 79, 195123 (2009).

[26] S. J. Denny, J. D. Biamonte, D. Jaksch, and S. R. Clark, J. Phys. A Math. Theor. 45, 015309 (2012).

[27] L. G. Valiant, Theor. Comput. Sci. 8, 189 (1979).

[28] C. Damm, M. Holzer, and P. McKenzie, Comput. Complex. 11, 54 (2002).

[29] B. M. Terhal and D. P. DiVincenzo, Quant. Inf. Comp. 4, 134 (2004), arXiv:0205133 [quant-ph].

[30] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A Math. Phys. Eng. Sci. 467, 459 (2010).

[31] S. Aaronson and A. Arkhipov, Theory Comput. 9, 143 (2013).

[32] R. Jozsa and M. V. den Nest, arXiv:1305.6190 (2013), https:/​/​doi.org/​10.26421/​qic14.7-8-7, arXiv:1305.6190.

[33] T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014).

[34] J. Carolan, C. Harrold, C. Sparrow, E. Martin-Lopez, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O'Brien, and A. Laing, Science 349, 711 (2015).

[35] E. Farhi and A. W. Harrow, arXiv:1602.07674 (2016), arXiv:1602.07674.

[36] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (2017) pp. 317–327.

[37] S. Aaronson and L. Chen, arXiv:1612.05903 (2016), arXiv:1612.05903.

[38] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nat. Phys. 14, 595 (2018).

[39] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nat. Phys. 15, 159 (2019).

[40] E. S. Fried, N. P. D. Sawaya, Y. Cao, I. D. Kivlichan, J. Romero, and A. Aspuru-Guzik, PLoS One 13, e0208510 (2018).

[41] J. Chen, F. Zhang, C. Huang, M. Newman, and Y. Shi, arXiv:1805.01450 (2018), arXiv:1805.01450.

[42] E. F. Dumitrescu, A. L. Fisher, T. D. Goodrich, T. S. Humble, B. D. Sullivan, and A. L. Wright, PLoS One 13, e0207827 (2018).

[43] S. Kourtis, C. Chamon, E. R. Mucciolo, and A. E. Ruckenstein, SciPost Phys. 7, 60 (2019).

[44] J. M. Dudek, L. Dueñas-Osorio, and M. Y. Vardi, arXiv:1908.04381 (2019), arXiv:1908.04381.

[45] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Nature 574, 505 (2019).

[46] D. Bienstock, Journal of Combinatorial Theory, Series B 49, 103 (1990).

[47] B. O'Gorman, in 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 135, edited by W. van Dam and L. Mancinska (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019) pp. 10:1–10:19.

[48] R. N. C. Pfeifer, J. Haegeman, and F. Verstraete, Phys. Rev. E 90, 033315 (2014).

[49] D. G. A. Smith and J. Gray, J. Open Source Softw. 3, 753 (2018).

[50] V. Gogate and R. Dechter, in Proceedings of the 20th conference on Uncertainty in artificial intelligence (AUAI Press, 2004) pp. 201–208, arXiv:1207.4109.

[51] M. Hamann and B. Strasser, J. Exp. Algorithmics 23, 1.2 (2018).

[52] B. Strasser, arXiv:1709.08949 (2017), arXiv:1709.08949.

[53] M. A. Porter, J.-P. Onnela, and P. J. Mucha, Not. Am. Math. Soc. 56, 1082 (2009), arXiv:0902.3788.

[54] S. Fortunato, Phys. Rep. 486, 75 (2010).

[55] M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. 99, 7821 (2002).

[56] S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz, in 2016 Proc. Eighteenth Work. Algorithm Eng. Exp. (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2016) pp. 53–67.

[57] Y. Akhremtsev, T. Heuer, P. Sanders, and S. Schlag, in 2017 Proc. Ninteenth Work. Algorithm Eng. Exp. (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017) pp. 28–42.

[58] D. A. Papa and I. L. Markov, in Handbook of Approximation Algorithms and Metaheuristics (2007).

[59] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas, Proceedings of the IEEE 104, 148 (2016).

[60] L. Gustafson, Bayesian Tuning and Bandits: An Extensible, Open Source Library for AutoML, M. eng thesis, Massachusetts Institute of Technology, Cambridge, MA (2018).

[61] C. K. Williams and C. E. Rasmussen, Gaussian processes for machine learning, Vol. 2 (MIT press Cambridge, MA, 2006).

[62] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, arXiv:1712.05384 (2017), arXiv:1712.05384.

[63] J. Gray, Journal of Open Source Software 3, 819 (2018).

[64] J. Gray, ``cotengra,'' https:/​/​github.com/​jcmgray/​cotengra (2020).

[65] B. Villalonga, D. Lyakh, S. Boixo, H. Neven, T. S. Humble, R. Biswas, E. G. Rieffel, A. Ho, and S. Mandrà, Quantum Science and Technology 5, 034003 (2020).

[66] I. L. Markov and Y. Shi, Algorithmica 59 (2009), https:/​/​doi.org/​10.1007/​s00453-009-9312-5.

[67] F. Viger and M. Latapy, in COCOON'05 Proc. 11th Annu. Int. Conf. Comput. Comb. (2005) pp. 440–449.

[68] K. Meichanetzidis and S. Kourtis, Phys. Rev. E 100, 033303 (2019).

[69] É. Fusy, Random Struct. Algorithms 35, 464 (2009).

[70] J.-Y. Cai and V. Choudhary, Theoretical Computer Science 384, 22 (2007), theory and Applications of Models of Computation.

[71] F. Bacchus, S. Dalmao, and T. Pitassi, in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003) pp. 340–351.

[72] C. Domshlak and J. Hoffmann, J. Artif. Int. Res. 30, 565–620 (2007).

[73] C. P. Gomes, A. Sabharwal, and B. Selman, in Handbook of Satisfiability (2009).

[74] ``1st international competition on model counting (mc 2020),''.

[75] J. Dudek, V. Phan, and M. Vardi, ``Addmc: Weighted model counting with algebraic decision diagrams,'' (2020).

[76] E. Farhi, J. Goldstone, and S. Gutmann, (2014), arXiv:1411.4028 [quant-ph].

[77] C. Huang, M. Szegedy, F. Zhang, X. Gao, J. Chen, and Y. Shi, (2019), arXiv:1909.02559 [quant-ph].

[78] J. Preskill, arXiv:1203.5813 (2012), arXiv:1203.5813.

[79] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, E. W. Draeger, E. T. Holland, and R. Wisnieff, arXiv:1710.05867 (2017), arXiv:1710.05867.

[80] F. Zhang, C. Huang, M. Newman, J. Cai, H. Yu, Z. Tian, B. Yuan, H. Xu, J. Wu, X. Gao, J. Chen, M. Szegedy, and Y. Shi, arXiv:1907.11217 (2019), arXiv:1907.11217.

[81] B. Villalonga, S. Boixo, B. Nelson, C. Henze, E. Rieffel, R. Biswas, and S. Mandrà, npj Quantum Inf. 5, 86 (2019).

[82] C. Guo, Y. Liu, M. Xiong, S. Xue, X. Fu, A. Huang, X. Qiang, P. Xu, J. Liu, S. Zheng, H.-L. Huang, M. Deng, D. Poletti, W.-S. Bao, and J. Wu, Phys. Rev. Lett. 123, 190501 (2019).

[83] I. L. Markov, A. Fatima, S. V. Isakov, and S. Boixo, arXiv preprint arXiv:1807.10749 (2018).

[84] https:/​/​github.com/​sboixo/​GRCS.

[85] I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Phys. Rev. Lett. 120, 110501 (2018).

[86] J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, and S. Wanderman-Milne, ``JAX: composable transformations of Python+NumPy programs,'' (2018).

[87] S. Bravyi, M. Suchara, and A. Vargo, Phys. Rev. A 90, 032326 (2014).

[88] A. J. Ferris and D. Poulin, Phys. Rev. Lett. 113, 030501 (2014).

[89] C. T. Chubb and S. T. Flammia, arXiv:1809.10704 (2018).

Cited by

[1] Reza Haghshenas, "Optimization schemes for unitary tensor-network circuit", Physical Review Research 3 2, 023148 (2021).

[2] Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang-Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, and Jianxin Chen, "Efficient parallelization of tensor network contraction for simulating quantum computation", Nature Computational Science 1 9, 578 (2021).

[3] Ryan L. Mann, "Simulating quantum computations with Tutte polynomials", npj Quantum Information 7 1, 141 (2021).

[4] Robert Cimrman, "Fast evaluation of finite element weak forms using python tensor contraction packages", Advances in Engineering Software 159, 103033 (2021).

[5] Jordi Tura, "Boosting simulation of quantum computers", Nature Computational Science (2021).

[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", arXiv:2005.06787.

[7] Ramis Movassagh, "Quantum supremacy and random circuits", arXiv:1909.06210.

[8] Xiao Mi, Pedram Roushan, Chris Quintana, Salvatore Mandra, Jeffrey Marshall, Charles Neill, Frank Arute, Kunal Arya, Juan Atalaya, Ryan Babbush, Joseph C. Bardin, Rami Barends, Andreas Bengtsson, Sergio Boixo, Alexandre Bourassa, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Zijun Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Alan R. Derk, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Edward Farhi, Austin G. Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Jonathan A. Gross, Matthew P. Harrigan, Sean D. Harrington, Jeremy Hilton, Alan Ho, Sabrina Hong, Trent Huang, William J. Huggins, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Julian Kelly, Seon Kim, Alexei Kitaev, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R. McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Kevin C. Miao, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Michael Newman, Murphy Yuezhen Niu, Thomas E. O'Brien, Alex Opremcak, Eric Ostby, Balint Pato, Andre Petukhov, Nicholas Redd, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vladimir Shvarts, Doug Strain, Marco Szalay, Matthew D. Trevithick, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, Igor Aleiner, Kostyantyn Kechedzhi, Vadim Smelyanskiy, and Yu Chen, "Information Scrambling in Computationally Complex Quantum Circuits", arXiv:2101.08870.

[9] Feng Pan and Pan Zhang, "Simulating the Sycamore quantum supremacy circuits", arXiv:2103.03074.

[10] 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", Physical Review Letters 125 6, 060503 (2020).

[11] Alexander Zlokapa, Sergio Boixo, and Daniel Lidar, "Boundaries of quantum supremacy via random circuit sampling", arXiv:2005.02464.

[12] Xin Hong, Xiangzhen Zhou, Sanjiang Li, Yuan Feng, and Mingsheng Ying, "A Tensor Network based Decision Diagram for Representation of Quantum Circuits", arXiv:2009.02618.

[13] Jin-Guo Liu, Lei Wang, and Pan Zhang, "Tropical Tensor Network for Ground States of Spin Glasses", Physical Review Letters 126 9, 090506 (2021).

[14] Roman Schutski, Taras Khakhulin, Ivan Oseledets, and Dmitry Kolmakov, "Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation", Physical Review A 102 6, 062614 (2020).

[15] Zhimin Wang, Zhaoyun Chen, Shengbin Wang, Wendong Li, Yongjian Gu, Guoping Guo, and Zhiqiang Wei, "A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer", arXiv:2008.07140.

[16] Jeffrey M. Dudek and Moshe Y. Vardi, "Parallel Weighted Model Counting with Tensor Networks", arXiv:2006.15512.

[17] Trevor Vincent, Lee J. O'Riordan, Mikhail Andrenkov, Jack Brown, Nathan Killoran, Haoyu Qi, and Ish Dhand, "Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction", arXiv:2107.09793.

[18] Linjian Ma and Chao Yang, "Low Rank Approximation in Simulations of Quantum Algorithms", arXiv:2104.11396.

[19] Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C. Platt, Vadim N. Smelyanskiy, and Sergio Boixo, "Efficient approximation of experimental Gaussian boson sampling", arXiv:2109.11525.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-20 08:01:36) and SAO/NASA ADS (last updated successfully 2021-10-20 08:01:37). The list may be incomplete as not all publishers provide suitable and complete citation data.