{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T10:04:51Z","timestamp":1766311491995,"version":"3.35.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T00:00:00Z","timestamp":1738281600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T00:00:00Z","timestamp":1738281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PID2020-113656RB-C21","PID2020-113656RB-C21","PID2020-113656RB-C21"],"award-info":[{"award-number":["PID2020-113656RB-C21","PID2020-113656RB-C21","PID2020-113656RB-C21"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004834","name":"Universitat Jaume I","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004834","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Quantum computing holds significant promise for solving complex problems, but simulating quantum circuits on classical computers remains essential due to the current limitations of quantum hardware. Efficient simulation is crucial for the development and validation of quantum algorithms and quantum computers. This paper explores and compares various strategies to leverage different levels of parallelism to accelerate the contraction of tensor networks representing large quantum circuits. We propose a new parallel multistage algorithm based on communities. The original tensor network is partitioned into several communities, which are then contracted in parallel. The pairs of tensors of the resulting network can be contracted in parallel using a GPU. We use the Girvan\u2013Newman algorithm to obtain the communities and the contraction plans. We compare the new algorithm with two other parallelisation strategies: one based on contracting all the pairs of tensors in the GPU and another one that uses slicing to cut some indexes of the tensor network and then MPI processes to contract the resulting slices in parallel. The new parallel algorithm gets the best results with different well-known quantum circuits with a high degree of entanglement, including random quantum circuits. In conclusion, the results show that the main factor that limits the simulation is the space cost. However, the parallel multistage algorithm manages to reduce the cost of sequential simulation for circuits with a high number of qubits and allows simulating larger circuits.<\/jats:p>","DOI":"10.1007\/s11227-025-06918-3","type":"journal-article","created":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T17:56:40Z","timestamp":1738346200000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A community detection-based parallel algorithm for quantum circuit simulation using tensor networks"],"prefix":"10.1007","volume":"81","author":[{"given":"Alfred M.","family":"Pastor","sequence":"first","affiliation":[]},{"given":"Jose M.","family":"Badia","sequence":"additional","affiliation":[]},{"given":"Maribel","family":"Castillo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,31]]},"reference":[{"key":"6918_CR1","doi-asserted-by":"publisher","DOI":"10.17226\/25196","volume-title":"Quantum computing: progress and prospects","author":"National Academies of Sciences, Engineering, and Medicine","year":"2019","unstructured":"National Academies of Sciences, Engineering, and Medicine (2019) Quantum computing: progress and prospects. The National Academies Press, Washington. https:\/\/doi.org\/10.17226\/25196"},{"key":"6918_CR2","unstructured":"Bobier J-F, Langione M, Tao E, Gourevitch A (2021) What happens when \u2018if\u2019 turns to \u2018when \u2019in quantum computing? Boston Consulting Group"},{"key":"6918_CR3","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 (2018) Quantum computing in the NISQ era and beyond. Quantum 2:79","journal-title":"Quantum"},{"key":"6918_CR4","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press, New York"},{"key":"6918_CR5","volume-title":"A practical guide to quantum machine learning and quantum optimization: hands-on approach to modern quantum algorithms","author":"EF Combarro","year":"2023","unstructured":"Combarro EF, Gonz\u00e1lez-Castillo S, Di Meglio A (2023) A practical guide to quantum machine learning and quantum optimization: hands-on approach to modern quantum algorithms. Packt Publishing Ltd, Birmingham"},{"issue":"1","key":"6918_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1038\/s41534-019-0196-1","volume":"5","author":"B Villalonga","year":"2019","unstructured":"Villalonga B, Boixo S, Nelson B, Henze C, Rieffel E, Biswas R, Mandr\u00e0 S (2019) A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware. NPJ Quant Inf 5(1):86","journal-title":"NPJ Quant Inf"},{"key":"6918_CR7","unstructured":"Xu X, Benjamin S, Sun J, Yuan X, Zhang P (2023) A herculean task: classical simulation of quantum computers. arXiv preprint arXiv:2302.08880"},{"key":"6918_CR8","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 (2014) A practical introduction to tensor networks: matrix product states and projected entangled pair states. Ann Phys 349:117\u2013158","journal-title":"Ann Phys"},{"issue":"3","key":"6918_CR9","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"IL Markov","year":"2008","unstructured":"Markov IL, Shi Y (2008) Simulating quantum computation by contracting tensor networks. SIAM J Comput 38(3):963\u2013981","journal-title":"SIAM J Comput"},{"issue":"12","key":"6918_CR10","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821\u20137826","journal-title":"Proc Natl Acad Sci"},{"key":"6918_CR11","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 (2021) Hyper-optimized tensor network contraction. Quantum 5:410","journal-title":"Quantum"},{"issue":"3","key":"6918_CR12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.032603","volume":"104","author":"Y-Q Zhao","year":"2021","unstructured":"Zhao Y-Q, Li R-G, Jiang J-Z et al (2021) Simulation of quantum computing on classical supercomputers with tensor-network edge cutting. Phys Rev A 104(3):032603","journal-title":"Phys Rev A"},{"key":"6918_CR13","doi-asserted-by":"crossref","unstructured":"Brennan J, Allalen M, Brayford D, Hanley K, Iapichino L, O\u2019Riordan LJ, Doyle M, Moran N (2021) Tensor network circuit simulation at exascale. In: 2021 IEEE\/ACM second international workshop on quantum computing software (QCS). IEEE, pp 20\u201326","DOI":"10.1109\/QCS54837.2021.00006"},{"key":"6918_CR14","unstructured":"Quantiki (2023) List of QC simulators. https:\/\/quantiki.org\/wiki\/list-qc-simulators"},{"key":"6918_CR15","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.cpc.2014.12.013","volume":"189","author":"DI Lyakh","year":"2015","unstructured":"Lyakh DI (2015) An efficient tensor transpose algorithm for multicore cpu, intel xeon phi, and nvidia tesla gpu. Comput Phys Commun 189:84\u201391","journal-title":"Comput Phys Commun"},{"key":"6918_CR16","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2022.838601","volume":"8","author":"DI Lyakh","year":"2022","unstructured":"Lyakh DI, Nguyen T, Claudino D, Dumitrescu E, McCaskey AJ (2022) ExaTN: scalable GPU-accelerated high-performance processing of general tensor networks at exascale. Front Appl Math Stat 8:838601","journal-title":"Front Appl Math Stat"},{"key":"6918_CR17","doi-asserted-by":"publisher","first-page":"709","DOI":"10.22331\/q-2022-05-09-709","volume":"6","author":"T Vincent","year":"2022","unstructured":"Vincent T, O\u2019Riordan LJ, Andrenkov M, Brown J, Killoran N, Qi H, Dhand I (2022) Jet: fast quantum circuit simulations with parallel task-based tensor-network contraction. Quantum 6:709","journal-title":"Quantum"},{"issue":"2","key":"6918_CR18","first-page":"1149","volume":"35","author":"D Jin","year":"2021","unstructured":"Jin D, Yu Z, Jiao P, Pan S, He D, Wu J, Philip SY, Zhang W (2021) A survey of community detection approaches: From statistical modeling to deep learning. IEEE Trans Knowl Data Eng 35(2):1149\u20131170","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"6918_CR19","doi-asserted-by":"publisher","first-page":"5233","DOI":"10.1038\/s41598-019-41695-","volume":"9","author":"V Traag","year":"2019","unstructured":"Traag V, Waltman L, Van Eck N (2019) From Louvain to Leiden: guaranteeing well-connected communities. Sci Rep 9:5233. https:\/\/doi.org\/10.1038\/s41598-019-41695-","journal-title":"Sci Rep"},{"issue":"3","key":"6918_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.036115","volume":"80","author":"VA Traag","year":"2009","unstructured":"Traag VA, Bruggeman J (2009) Community detection in networks with positive and negative links. Phys Rev E 80(3):036115","journal-title":"Phys Rev E"},{"issue":"5","key":"6918_CR21","doi-asserted-by":"publisher","first-page":"060","DOI":"10.21468\/SciPostPhys.7.5.060","volume":"7","author":"S Kourtis","year":"2019","unstructured":"Kourtis S, Chamon C, Mucciolo E, Ruckenstein A (2019) Fast counting with tensor networks. SciPost Phys 7(5):060","journal-title":"SciPost Phys"},{"issue":"02","key":"6918_CR22","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1142\/S0129626497000176","volume":"7","author":"L Chi-Chung","year":"1997","unstructured":"Chi-Chung L, Sadayappan P, Wenger R (1997) On optimizing a class of multi-dimensional loops with reduction for parallel execution. Parallel Processing Letters 7(02):157\u2013168","journal-title":"Parallel Processing Letters"},{"issue":"3","key":"6918_CR23","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender HL, Koster AM (2010) Treewidth computations I. upper bounds. Inf Comput 208(3):259\u2013275","journal-title":"Inf Comput"},{"key":"6918_CR24","doi-asserted-by":"publisher","DOI":"10.1145\/3173045","author":"M Hamann","year":"2018","unstructured":"Hamann M, Strasser B (2018) Graph bisection with pareto optimization. ACM J Exp Algorithmics. https:\/\/doi.org\/10.1145\/3173045","journal-title":"ACM J. Exp. Algorithmics."},{"issue":"4","key":"6918_CR25","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","volume":"37","author":"H Tamaki","year":"2019","unstructured":"Tamaki H (2019) Positive-instance driven dynamic programming for treewidth. J Comb Optim 37(4):1283\u20131311. https:\/\/doi.org\/10.1007\/s10878-018-0353-z","journal-title":"J Comb Optim"},{"key":"6918_CR26","doi-asserted-by":"publisher","unstructured":"Dell H, Komusiewicz C, Talmon N, Weller M (2018) The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In: Lokshtanov D, Nishimura N (eds) 12th international symposium on parameterized and exact computation (IPEC 2017). Leibniz international proceedings in informatics (LIPIcs), vol 89. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp 30\u201313012. https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30","DOI":"10.4230\/LIPIcs.IPEC.2017.30"},{"issue":"04","key":"6918_CR27","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1142\/S0219525903001067","volume":"6","author":"PM Gleiser","year":"2003","unstructured":"Gleiser PM, Danon L (2003) Community structure in jazz. Adv Complex Syst 6(04):565\u2013573","journal-title":"Adv Complex Syst"},{"issue":"3\u20135","key":"6918_CR28","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486(3\u20135):75\u2013174","journal-title":"Phys Rep"},{"issue":"4","key":"6918_CR29","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.physrep.2013.08.002","volume":"533","author":"FD Malliaros","year":"2013","unstructured":"Malliaros FD, Vazirgiannis M (2013) Clustering and community detection in directed networks: a survey. Phys Rep 533(4):95\u2013142","journal-title":"Phys Rep"},{"issue":"2","key":"6918_CR30","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"ME Newman","year":"2004","unstructured":"Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113","journal-title":"Phys Rev E"},{"issue":"2","key":"6918_CR31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.027104","volume":"72","author":"J Duch","year":"2005","unstructured":"Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E 72(2):027104","journal-title":"Phys Rev E"},{"issue":"4","key":"6918_CR32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.042822","volume":"88","author":"ME Newman","year":"2013","unstructured":"Newman ME (2013) Spectral methods for community detection and graph partitioning. Phys Rev E 88(4):042822","journal-title":"Phys Rev E"},{"issue":"2","key":"6918_CR33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.025101","volume":"70","author":"R Guimera","year":"2004","unstructured":"Guimera R, Sales-Pardo M, Amaral LAN (2004) Modularity from fluctuations in random graphs and complex networks. Phys Rev E 70(2):025101","journal-title":"Phys Rev E"},{"issue":"10","key":"6918_CR34","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):10008. https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/P10008","journal-title":"J Stat Mech Theory Exp"},{"issue":"6","key":"6918_CR35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E Stat Nonlinear Soft Matter Phys 70(6):066111","journal-title":"Phys Rev E Stat Nonlinear Soft Matter Phys"},{"issue":"9","key":"6918_CR36","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1038\/s43588-021-00119-7","volume":"1","author":"C Huang","year":"2021","unstructured":"Huang C, Zhang F, Newman M, Ni X, Ding D, Cai J, Gao X, Wang T, Wu F, Zhang G et al (2021) Efficient parallelization of tensor network contraction for simulating quantum computation. Nat Comput Sci 1(9):578\u2013587","journal-title":"Nat Comput Sci"},{"key":"6918_CR37","doi-asserted-by":"crossref","unstructured":"Lykov D, Schutski R, Galda A, Vinokur V, Alexeev Y (2022) Tensor network quantum simulator with step-dependent parallelization. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, pp 582\u2013593","DOI":"10.1109\/QCE53715.2022.00081"},{"issue":"3","key":"6918_CR38","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab7eeb","volume":"5","author":"B Villalonga","year":"2020","unstructured":"Villalonga B, Lyakh D, Boixo S, Neven H, Humble TS, Biswas R, Rieffel EG, Ho A, Mandr\u00e0 S (2020) Establishing the quantum supremacy frontier with a 281 pflop\/s simulation. Quant Sci Technol 5(3):034003","journal-title":"Quant Sci Technol"},{"issue":"6","key":"6918_CR39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.062614","volume":"102","author":"R Schutski","year":"2020","unstructured":"Schutski R, Khakhulin T, Oseledets I, Kolmakov D (2020) Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation. Phys Rev A 102(6):062614","journal-title":"Phys Rev A"},{"issue":"1.5","key":"6918_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.21468\/SciPostPhysCodeb.4","volume":"4","author":"M Fishman","year":"2022","unstructured":"Fishman M, White SR, Stoudenmire EM (2022) The ITensor software library for tensor network calculations. SciPost Phys Codebases 4(1.5):1. https:\/\/doi.org\/10.21468\/SciPostPhysCodeb.4","journal-title":"SciPost Phys Codebases"},{"issue":"1","key":"6918_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M108968X","volume":"40","author":"DA Matthews","year":"2018","unstructured":"Matthews DA (2018) High-performance tensor contraction without transposition. SIAM J Sci Comput 40(1):1\u201324","journal-title":"SIAM J Sci Comput"},{"key":"6918_CR42","unstructured":"NVIDIA (2024) cuTENSOR: A high-performance CUDA library for tensor primitives. https:\/\/docs.nvidia.com\/cuda\/cutensor"},{"issue":"4","key":"6918_CR43","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1109\/TPDS.2018.2872064","volume":"30","author":"T Besard","year":"2018","unstructured":"Besard T, Foket C, De Sutter B (2018) Effective extensible programming: unleashing Julia on GPUs. IEEE Trans Parallel Distrib Syst 30(4):827\u2013841","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"6918_CR44","unstructured":"Pastor A, Badia JM, Castillo MI (2023) Efficient quantum circuit simulation using tensor networks. In: Quantum information in Spain (ICE-8): Santiago de Compostela, 29th May to 1st June, Spain"},{"issue":"6","key":"6918_CR45","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1038\/s41567-018-0124-x","volume":"14","author":"S Boixo","year":"2018","unstructured":"Boixo S, Isakov SV, Smelyanskiy VN, Babbush R, Ding N, Jiang Z, Bremner MJ, Martinis JM, Neven H (2018) Characterizing quantum supremacy in near-term devices. Nat Phys 14(6):595\u2013600","journal-title":"Nat Phys"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-06918-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-025-06918-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-06918-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T17:56:47Z","timestamp":1738346207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-025-06918-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,31]]},"references-count":45,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["6918"],"URL":"https:\/\/doi.org\/10.1007\/s11227-025-06918-3","relation":{},"ISSN":["1573-0484"],"issn-type":[{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,31]]},"assertion":[{"value":"2 January 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"450"}}