{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T01:21:37Z","timestamp":1781313697451,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T00:00:00Z","timestamp":1560211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Office of Science of the U.S. Department of Energy","award":["DE-AC05-00OR22725"],"award-info":[{"award-number":["DE-AC05-00OR22725"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            complex matrices run in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n              \/2\n            <\/jats:sup>\n            ) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 \u00d7 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 \u00d7 100 matrix.\n          <\/jats:p>","DOI":"10.1145\/3325111","type":"journal-article","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T13:28:16Z","timestamp":1560259696000},"page":"1-17","source":"Crossref","is-referenced-by-count":61,"title":["A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a Supercomputer"],"prefix":"10.1145","volume":"24","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lund University, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6352-8342","authenticated-orcid":false,"given":"Brajesh","family":"Gupt","sequence":"additional","affiliation":[{"name":"Xanadu, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicol\u00e1s","family":"Quesada","sequence":"additional","affiliation":[{"name":"Xanadu, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Nicolas Quesada Brajesh Gupt and Josh Izaac. 2018. hafnian. Retrieved from https:\/\/github.com\/XanaduAI\/hafnian.  Nicolas Quesada Brajesh Gupt and Josh Izaac. 2018. hafnian. Retrieved from https:\/\/github.com\/XanaduAI\/hafnian."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993682"},{"key":"e_1_2_1_3_1","volume-title":"Stegun","author":"Abramowitz Milton","year":"1972","unstructured":"Milton Abramowitz and Irene A . Stegun . 1972 . Handbook of Mathematical Functions: With Formulas , Graphs, and Mathematical Tables. Vol. 55 . Dover . Milton Abramowitz and Irene A. Stegun. 1972. Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables. Vol. 55. Dover."},{"key":"e_1_2_1_4_1","volume-title":"Anne Greenbaum, Sven Hammarling, Alan McKenney, et al.","author":"Anderson Edward","year":"1999","unstructured":"Edward Anderson , Zhaojun Bai , Christian Bischof , L. Susan Blackford , James Demmel , Jack Dongarra , Jeremy Du Croz , Anne Greenbaum, Sven Hammarling, Alan McKenney, et al. 1999 . LAPACK Users\u2019 Guide. SIAM. Edward Anderson, Zhaojun Bai, Christian Bischof, L. Susan Blackford, James Demmel, Jack Dongarra, Jeremy Du Croz, Anne Greenbaum, Sven Hammarling, Alan McKenney, et al. 1999. LAPACK Users\u2019 Guide. SIAM."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Alexander Barvinok. {n. d.}. Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Rand. Struct. Algor. 14 1 ({n. d.}) 29--61.   Alexander Barvinok. {n. d.}. Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Rand. Struct. Algor. 14 1 ({n. d.}) 29--61.","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X"},{"issue":"2017","key":"e_1_2_1_7_1","first-page":"34","article-title":"Approximating permanents and hafnians","volume":"2","author":"Barvinok Alexander","year":"2016","unstructured":"Alexander Barvinok . 2016 . Approximating permanents and hafnians . Discrete Analysis 2 ( 2017 ), 34 . Alexander Barvinok. 2016. Approximating permanents and hafnians. Discrete Analysis 2 (2017), 34.","journal-title":"Discrete Analysis"},{"key":"e_1_2_1_8_1","volume-title":"Combinatorics and Complexity of Partition Functions","author":"Barvinok Alexander","unstructured":"Alexander Barvinok . 2016. Combinatorics and Complexity of Partition Functions . Vol. 274 . Springer . Alexander Barvinok. 2016. Combinatorics and Complexity of Partition Functions. Vol. 274. Springer."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871880.2871884"},{"key":"e_1_2_1_10_1","unstructured":"E. Bax and J. Franklin. 1996. A finite-difference sieve to compute the permanent. Caltech-CS-TR-96-04 California Institute of Technology (1996).  E. Bax and J. Franklin. 1996. A finite-difference sieve to compute the permanent. Caltech-CS-TR-96-04 California Institute of Technology (1996)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095189"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119186"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Chien Steve","year":"2004","unstructured":"Steve Chien . 2004 . A determinant-based algorithm for counting perfect matchings in a general graph . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 728--735. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982903 Steve Chien. 2004. A determinant-based algorithm for counting perfect matchings in a general graph. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). Society for Industrial and Applied Mathematics, Philadelphia, PA, 728--735. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982903"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175276"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252687"},{"key":"e_1_2_1_17_1","volume-title":"Nicol\u00e1s Quesada, and Thomas R Bromley.","author":"Gupt Brajesh","year":"2018","unstructured":"Brajesh Gupt , Juan Miguel Arrazola , Nicol\u00e1s Quesada, and Thomas R Bromley. 2018 . Classical benchmarking of gaussian boson sampling on the titan supercomputer. arXiv preprint arXiv:1810.00900 (2018). Brajesh Gupt, Juan Miguel Arrazola, Nicol\u00e1s Quesada, and Thomas R Bromley. 2018. Classical benchmarking of gaussian boson sampling on the titan supercomputer. arXiv preprint arXiv:1810.00900 (2018)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.170501"},{"key":"e_1_2_1_19_1","volume-title":"Harrow and Ashley Montanaro","author":"Aram","year":"2017","unstructured":"Aram W. Harrow and Ashley Montanaro . 2017 . Quantum computational supremacy. Nature 549, 7671 (2017), 203. Aram W. Harrow and Ashley Montanaro. 2017. Quantum computational supremacy. Nature 549, 7671 (2017), 203."},{"key":"e_1_2_1_20_1","volume-title":"Johnson","author":"Horn Roger A.","year":"1990","unstructured":"Roger A. Horn , Roger A. Horn , and Charles R . Johnson . 1990 . Matrix Analysis. Cambridge University Press . Roger A. Horn, Roger A. Horn, and Charles R. Johnson. 1990. Matrix Analysis. Cambridge University Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1246\/bcsj.44.2332"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027227"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2007.01.013"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3929.3939"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-03-11-129"},{"key":"e_1_2_1_26_1","volume-title":"Seminumerical Algorithms","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming , Vol. 2 : Seminumerical Algorithms ( 3 rd ed.). Addison-Wesley . Donald E. Knuth. 1998. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.","edition":"3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_21"},{"key":"e_1_2_1_28_1","first-page":"29","article-title":"Non-commutative extensions of the MacMahon master theorem","volume":"2016","author":"Konvalinka Matja\u017e","year":"2006","unstructured":"Matja\u017e Konvalinka and Igor Pak . 2006 . Non-commutative extensions of the MacMahon master theorem . Advances in Mathematics 2016 , 1 (2007), 29 -- 61 . Matja\u017e Konvalinka and Igor Pak. 2006. Non-commutative extensions of the MacMahon master theorem. Advances in Mathematics 2016, 1 (2007), 29--61.","journal-title":"Advances in Mathematics"},{"key":"e_1_2_1_29_1","volume-title":"A detailed study of Gaussian boson sampling. arXiv preprint arXiv:1801.07488","author":"Kruse Regina","year":"2018","unstructured":"Regina Kruse , Craig S. Hamilton , Linda Sansoni , Sonja Barkhofen , Christine Silberhorn , and Igor Jex . 2018. A detailed study of Gaussian boson sampling. arXiv preprint arXiv:1801.07488 ( 2018 ). Regina Kruse, Craig S. Hamilton, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. 2018. A detailed study of Gaussian boson sampling. arXiv preprint arXiv:1801.07488 (2018)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0748"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"A. I. Lvovsky. 2015. Squeezed light. Photonics Volume 1: Fundamentals of Photonics and Physics. 121--164.  A. I. Lvovsky. 2015. Squeezed light. Photonics Volume 1: Fundamentals of Photonics and Physics. 121--164.","DOI":"10.1002\/9781119009719.ch5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157000000590"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys4270"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.5086387"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.98.062322"},{"key":"e_1_2_1_37_1","volume-title":"Symmetric Functionals on Random Matrices and Random Matchings Problems","author":"Rempala Grzegorz","unstructured":"Grzegorz Rempala and Jacek Wesolowski . 2007. Symmetric Functionals on Random Matrices and Random Matchings Problems . Vol. 147 . Springer Science 8 Business Media. Grzegorz Rempala and Jacek Wesolowski. 2007. Symmetric Functionals on Random Matrices and Random Matchings Problems. Vol. 147. Springer Science 8 Business Media."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1036"},{"key":"e_1_2_1_39_1","volume-title":"Combinatorial Mathematics. Number 14","author":"Ryser Herbert John","unstructured":"Herbert John Ryser . 1963. Combinatorial Mathematics. Number 14 . Mathematical Association of America and Wiley , New York, NY . Herbert John Ryser. 1963. Combinatorial Mathematics. Number 14. Mathematical Association of America and Wiley, New York, NY."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.696341"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/281508.281570"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.15803\/ijnc.7.2_227"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/nsr\/nwy079"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325111","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:24Z","timestamp":1750193244000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,11]]},"references-count":43,"alternative-id":["10.1145\/3325111"],"URL":"https:\/\/doi.org\/10.1145\/3325111","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,11]]}}}