{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T23:06:25Z","timestamp":1778108785273,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 10<jats:sup>5<\/jats:sup> times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.<\/jats:p>","DOI":"10.1038\/s43588-021-00119-7","type":"journal-article","created":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T16:03:30Z","timestamp":1631549010000},"page":"578-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Efficient parallelization of tensor network contraction for simulating quantum computation"],"prefix":"10.1038","volume":"1","author":[{"given":"Cupjin","family":"Huang","sequence":"first","affiliation":[]},{"given":"Fang","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Newman","sequence":"additional","affiliation":[]},{"given":"Xiaotong","family":"Ni","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7728-5380","authenticated-orcid":false,"given":"Dawei","family":"Ding","sequence":"additional","affiliation":[]},{"given":"Junjie","family":"Cai","sequence":"additional","affiliation":[]},{"given":"Xun","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Tenghui","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Feng","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Gengyan","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Hsiang-Sheng","family":"Ku","sequence":"additional","affiliation":[]},{"given":"Zhengxiong","family":"Tian","sequence":"additional","affiliation":[]},{"given":"Junyin","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Haihong","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Huanjun","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Bo","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5523-6166","authenticated-orcid":false,"given":"Yaoyun","family":"Shi","sequence":"additional","affiliation":[]},{"given":"Hui-Hai","family":"Zhao","sequence":"additional","affiliation":[]},{"given":"Chunqing","family":"Deng","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9365-776X","authenticated-orcid":false,"given":"Jianxin","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,13]]},"reference":[{"key":"119_CR1","unstructured":"Preskill, J. Quantum computing and the entanglement frontier. Preprint at https:\/\/arxiv.org\/abs\/1203.5813 (2012)."},{"key":"119_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505\u2013510 (2019).","journal-title":"Nature"},{"key":"119_CR3","doi-asserted-by":"crossref","unstructured":"Zhong, H.-S. et al. Quantum computational advantage using photons. Science 370, 1460\u20131463 (2020).","DOI":"10.1126\/science.abe8770"},{"key":"119_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).","journal-title":"Quantum"},{"key":"119_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.22331\/q-2018-01-31-49","volume":"2","author":"DS Steiger","year":"2018","unstructured":"Steiger, D. S., H\u00e4ner, T. & Troyer, M. ProjectQ: an open source software framework for quantum computing. Quantum 2, 49 (2018).","journal-title":"Quantum"},{"key":"119_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1038\/s41567-018-0124-x","volume":"14","author":"S Boixo","year":"2018","unstructured":"Boixo, S. et al. Characterizing quantum supremacy in near-term devices. Nat. Phys. 14, 595\u2013600 (2018).","journal-title":"Nat. Phys."},{"key":"119_CR7","unstructured":"Pednault, E. et al. Breaking the 49-qubit barrier in the simulation of quantum circuits. Preprint at https:\/\/arxiv.org\/abs\/1710.05867 (2017)."},{"key":"119_CR8","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1007\/s10955-015-1276-z","volume":"160","author":"JD Biamonte","year":"2015","unstructured":"Biamonte, J. D., Morton, J. & Turner, J. Tensor network contractions for #SAT. J. Stat. Phys. 160, 1389\u20131404 (2015).","journal-title":"J. Stat. Phys."},{"key":"119_CR9","doi-asserted-by":"publisher","first-page":"5585","DOI":"10.1109\/TIT.2020.3004427","volume":"66","author":"C Huang","year":"2020","unstructured":"Huang, C., Newman, M. & Szegedy, M. Explicit lower bounds on strong quantum simulation. IEEE Trans. Inf. Theory 66, 5585\u20135600 (2020).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"119_CR10","doi-asserted-by":"publisher","first-page":"2863","DOI":"10.1103\/PhysRevLett.69.2863","volume":"69","author":"SR White","year":"1992","unstructured":"White, S. R. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett. 69, 2863 (1992).","journal-title":"Phys. Rev. Lett."},{"key":"119_CR11","doi-asserted-by":"publisher","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","volume":"91","author":"G Vidal","year":"2003","unstructured":"Vidal, G. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91, 147902 (2003).","journal-title":"Phys. Rev. Lett."},{"key":"119_CR12","doi-asserted-by":"publisher","first-page":"070201","DOI":"10.1103\/PhysRevLett.98.070201","volume":"98","author":"G Vidal","year":"2007","unstructured":"Vidal, G. Classical simulation of infinite-size quantum lattice systems in one spatial dimension. Phys. Rev. Lett. 98, 070201 (2007).","journal-title":"Phys. Rev. Lett."},{"key":"119_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1103\/RevModPhys.77.259","volume":"77","author":"U Schollw\u00f6ck","year":"2005","unstructured":"Schollw\u00f6ck, U. The density-matrix renormalization group. Rev. Modern Phys. 77, 259 (2005).","journal-title":"Rev. Modern Phys."},{"key":"119_CR14","doi-asserted-by":"publisher","first-page":"032326","DOI":"10.1103\/PhysRevA.90.032326","volume":"90","author":"S Bravyi","year":"2014","unstructured":"Bravyi, S., Suchara, M. & Vargo, A. Efficient algorithms for maximum likelihood decoding in the surface code. Phys. Rev. A 90, 032326 (2014).","journal-title":"Phys. Rev. A"},{"key":"119_CR15","doi-asserted-by":"publisher","first-page":"030501","DOI":"10.1103\/PhysRevLett.113.030501","volume":"113","author":"AJ Ferris","year":"2014","unstructured":"Ferris, A. J. & Poulin, D. Tensor networks and quantum error correction. Phys. Rev. Lett. 113, 030501 (2014).","journal-title":"Phys. Rev. Lett."},{"key":"119_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.4171\/AIHPD\/105","volume":"8","author":"CT Chubb","year":"2021","unstructured":"Chubb, C. T. & Flammia, S. T. Statistical mechanical models for quantum codes with correlated noise. Ann. Henri Poincar\u00e9 D 8, 269\u2013321 (2021).","journal-title":"Ann. Henri Poincar\u00e9 D"},{"key":"119_CR17","doi-asserted-by":"publisher","first-page":"051302","DOI":"10.1103\/PhysRevE.97.051302","volume":"97","author":"AS Darmawan","year":"2018","unstructured":"Darmawan, A. S. & Poulin, D. Linear-time general decoding algorithm for the surface code. Phys. Rev. E 97, 051302 (2018).","journal-title":"Phys. Rev. E"},{"key":"119_CR18","unstructured":"Dudek, J. M. and Vardi, M. Y. Parallel weighted model counting with tensor networks. Preprint at https:\/\/arxiv.org\/abs\/2006.15512 (2020)."},{"key":"119_CR19","doi-asserted-by":"publisher","first-page":"062614","DOI":"10.1103\/PhysRevA.102.062614","volume":"102","author":"R Schutski","year":"2020","unstructured":"Schutski, R., Khakhulin, T., Oseledets, I. & Kolmakov, D. Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation. Phys. Rev. A 102, 062614 (2020).","journal-title":"Phys. Rev. A"},{"key":"119_CR20","unstructured":"Lykov, D., Schutski, R., Galda, A., Vinokur, V. & Alexeev, Y. Tensor network quantum simulator with step-dependent parallelization. Preprint at https:\/\/arxiv.org\/abs\/2012.02430 (2020)."},{"key":"119_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41534-019-0196-1","volume":"5","author":"B Villalonga","year":"2019","unstructured":"Villalonga, B. et al. A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware. npj Quantum Inf. 5, 1\u201316 (2019).","journal-title":"npj Quantum Inf."},{"key":"119_CR22","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.aop.2014.06.013","volume":"349","author":"R Or\u00fas","year":"2014","unstructured":"Or\u00fas, R. A practical introduction to tensor networks: matrix product states and projected entangled pair states. Annals Phys. 349, 117\u2013158 (2014).","journal-title":"Annals Phys."},{"key":"119_CR23","doi-asserted-by":"publisher","first-page":"110501","DOI":"10.1103\/PhysRevLett.101.110501","volume":"101","author":"G Vidal","year":"2008","unstructured":"Vidal, G. Class of quantum many-body states that can be efficiently simulated. Phys. Rev. Lett. 101, 110501 (2008).","journal-title":"Phys. Rev. Lett."},{"key":"119_CR24","first-page":"031012","volume":"8","author":"Z-Y Han","year":"2018","unstructured":"Han, Z.-Y., Wang, J., Fan, H., Wang, L. & Zhang, P. Unsupervised generative modeling using matrix product states. Phys. Rev. X 8, 031012 (2018).","journal-title":"Phys. Rev. X"},{"key":"119_CR25","doi-asserted-by":"publisher","first-page":"eaat9004","DOI":"10.1126\/sciadv.aat9004","volume":"4","author":"X Gao","year":"2018","unstructured":"Gao, X., Zhang, Z.-Y. & Duan, L.-M. A quantum machine learning algorithm based on generative models. Sci. Adv. 4, eaat9004 (2018).","journal-title":"Sci. Adv."},{"key":"119_CR26","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"IL Markov","year":"2008","unstructured":"Markov, I. L. & Shi, Y. Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38, 963\u2013981 (2008).","journal-title":"SIAM J. Comput."},{"key":"119_CR27","unstructured":"Boixo, S., Isakov, S. V., Smelyanskiy, V. N. & Neven, H. Simulation of low-depth quantum circuits as complex undirected graphical models. Preprint at https:\/\/arxiv.org\/abs\/1712.05384 (2017)."},{"key":"119_CR28","doi-asserted-by":"publisher","first-page":"410","DOI":"10.22331\/q-2021-03-15-410","volume":"5","author":"J Gray","year":"2021","unstructured":"Gray, J. & Kourtis, S. Hyper-optimized tensor network contraction. Quantum 5, 410 (2021).","journal-title":"Quantum"},{"key":"119_CR29","doi-asserted-by":"publisher","first-page":"042335","DOI":"10.1103\/PhysRevA.101.042335","volume":"101","author":"R Schutski","year":"2020","unstructured":"Schutski, R., Lykov, D. & Oseledets, I. Adaptive algorithm for quantum circuit simulation. Physical Review A 101, 042335 (2020).","journal-title":"Physical Review A"},{"key":"119_CR30","unstructured":"Pan, F. & Zhang, P. Simulating the sycamore quantum supremacy circuits. Preprint at https:\/\/arxiv.org\/abs\/2103.03074 (2021)."},{"key":"119_CR31","unstructured":"Szegedy, M. What do QAOA energies reveal about graphs? Preprint at https:\/\/arxiv.org\/abs\/1912.12277 (2019)."},{"key":"119_CR32","doi-asserted-by":"publisher","first-page":"115302","DOI":"10.1088\/1751-8113\/48\/11\/115302","volume":"48","author":"H Wang","year":"2015","unstructured":"Wang, H., Wu, J., Yang, X. & Yi, X. A graph isomorphism algorithm using signatures computed via quantum walk search model. J. Phys. A 48, 115302 (2015).","journal-title":"J. Phys. A"},{"key":"119_CR33","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1016\/j.patcog.2008.10.025","volume":"42","author":"D Emms","year":"2009","unstructured":"Emms, D., Severini, S., Wilson, R. C. & Hancock, E. R. Coined quantum walks lift the cospectrality of graphs and trees. Pattern Recognit. 42, 1988\u20132002 (2009).","journal-title":"Pattern Recognit."},{"key":"119_CR34","doi-asserted-by":"publisher","first-page":"265301","DOI":"10.1088\/1751-8113\/48\/26\/265301","volume":"48","author":"A Mahasinghe","year":"2015","unstructured":"Mahasinghe, A., Izaac, J. A., Wang, J. B. & Wijerathna, J. K. Phase-modified CTQW unable to distinguish strongly regular graphs efficiently. J. Phys. A 48, 265301 (2015).","journal-title":"J. Phys. A"},{"key":"119_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41534-017-0039-x","volume":"3","author":"TE O\u2019Brien","year":"2017","unstructured":"O\u2019Brien, T. E., Tarasinski, B. & DiCarlo, L. Density-matrix simulation of small surface codes under current and projected experimental noise. npj Quantum Inf. 3, 1\u20138 (2017).","journal-title":"npj Quantum Inf."},{"key":"119_CR36","doi-asserted-by":"publisher","first-page":"043038","DOI":"10.1088\/1367-2630\/aab341","volume":"20","author":"CJ Trout","year":"2018","unstructured":"Trout, C. J. et al. Simulating the performance of a distance-3 surface code in a linear ion trap. New J. Phys. 20, 043038 (2018).","journal-title":"New J. Phys."},{"key":"119_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-020-20314-w","volume":"12","author":"JPB Ataides","year":"2021","unstructured":"Ataides, J. P. B., Tuckett, D. K., Bartlett, S. D., Flammia, S. T. & Brown, B. J. The XZZX surface code. Nat. Commun. 12, 1\u201312 (2021).","journal-title":"Nat. Commun."},{"key":"119_CR38","first-page":"041038","volume":"10","author":"Y Zhou","year":"2020","unstructured":"Zhou, Y., Stoudenmire, E. M. & Waintal, X. What limits the simulation of quantum computers? Phys. Rev. X 10, 041038 (2020).","journal-title":"Phys. Rev. X"},{"key":"119_CR39","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1080\/14789940801912366","volume":"57","author":"F Verstraete","year":"2008","unstructured":"Verstraete, F., Murg, V. & Cirac, J. I. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Adv. Phys. 57, 143\u2013224 (2008).","journal-title":"Adv. Phys."},{"key":"119_CR40","doi-asserted-by":"publisher","first-page":"025012","DOI":"10.1088\/1367-2630\/12\/2\/025012","volume":"12","author":"B Pirvu","year":"2010","unstructured":"Pirvu, B., Murg, V., Cirac, J. I. & Verstraete, F. Matrix product operator representations. New J. Phys. 12, 025012 (2010).","journal-title":"New J. Phys."},{"key":"119_CR41","doi-asserted-by":"publisher","first-page":"207204","DOI":"10.1103\/PhysRevLett.93.207204","volume":"93","author":"F Verstraete","year":"2004","unstructured":"Verstraete, F., Garcia-Ripoll, J. J. & Cirac, J. I. Matrix product density operators: simulation of finite-temperature and dissipative systems. Physical review letters 93, 207204 (2004).","journal-title":"Physical review letters"},{"key":"119_CR42","doi-asserted-by":"publisher","first-page":"318","DOI":"10.22331\/q-2020-09-11-318","volume":"4","author":"K Noh","year":"2020","unstructured":"Noh, K., Jiang, L. & Fefferman, B. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum 4, 318 (2020).","journal-title":"Quantum"},{"key":"119_CR43","doi-asserted-by":"publisher","unstructured":"Hansen, N., Akimoto, Y. & Baudis, P. CMA-ES\/pycma on Github (Zenodo, 2019); https:\/\/doi.org\/10.5281\/zenodo.2559634","DOI":"10.5281\/zenodo.2559634"},{"key":"119_CR44","unstructured":"Schlag, S. High-Quality Hypergraph Partitioning. PhD thesis, Karlsruhe Institute of Technology (2020)."},{"key":"119_CR45","doi-asserted-by":"publisher","first-page":"753","DOI":"10.21105\/joss.00753","volume":"3","author":"G Daniel","year":"2018","unstructured":"Daniel, G. et al. Opt_einsum\u2014a python package for optimizing contraction order for einsum-like expressions. J. Open Source Software 3, 753 (2018).","journal-title":"J. Open Source Software"},{"key":"119_CR46","doi-asserted-by":"publisher","unstructured":"Martinis, J. M. et al. Quantum Supremacy Using a Programmable Superconducting Processor (Dryad, 2021); https:\/\/doi.org\/10.5061\/dryad.k6t1rj8","DOI":"10.5061\/dryad.k6t1rj8"},{"key":"119_CR47","unstructured":"Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at https:\/\/arxiv.org\/abs\/1411.4028 (2014)."},{"key":"119_CR48","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1038\/nature08121","volume":"460","author":"L DiCarlo","year":"2009","unstructured":"DiCarlo, L. et al. Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature 460, 240\u2013244 (2009).","journal-title":"Nature"},{"key":"119_CR49","doi-asserted-by":"publisher","unstructured":"Huang, C. et al. Efficient Parallelization of Tensor Network Contractions for Simulating Quantum Computation (Dryad, 2021); https:\/\/doi.org\/10.5061\/dryad.nk98sf7t8","DOI":"10.5061\/dryad.nk98sf7t8"},{"key":"119_CR50","doi-asserted-by":"publisher","unstructured":"Huang, C., Zhang, F. & Chen, J. An open-source simulator-driven development tool for quantum computing. Code Ocean https:\/\/doi.org\/10.24433\/CO.4349832.v2 (2021).","DOI":"10.24433\/CO.4349832.v2"},{"key":"119_CR51","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G","volume":"30","author":"M Meringer","year":"1999","unstructured":"Meringer, M. Fast generation of regular graphs and construction of cages. J. Graph Theory 30, 137\u2013146 (1999).","journal-title":"J. Graph Theory"},{"key":"119_CR52","unstructured":"Brouwer, A. E. Paulus-Rozenfeld Graphs https:\/\/www.win.tue.nl\/~aeb\/graphs\/Paulus.html"}],"container-title":["Nature Computational Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s43588-021-00119-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-021-00119-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-021-00119-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,3]],"date-time":"2022-12-03T21:30:43Z","timestamp":1670103043000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s43588-021-00119-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,13]]},"references-count":52,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["119"],"URL":"https:\/\/doi.org\/10.1038\/s43588-021-00119-7","relation":{},"ISSN":["2662-8457"],"issn-type":[{"value":"2662-8457","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,13]]},"assertion":[{"value":"26 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Alibaba Group Holding Ltd has filed patent application US20190332731A1 for inventors J. Chen, F.Z., Y.S., C.H. and M.N., as well as provisional patent applications 62\/957,442 (C.H., F.Z. and J. Chen), 63\/015,178 (C.H. and J. Chen) and 63\/015,116 (C.H. and J. Chen).","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}