{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:52:39Z","timestamp":1769316759682,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:p>Quantum computing and distributed systems may enter a mutually beneficial partnership in the future. On the one hand, it is much easier to build a number of small quantum computers rather than a single large one. On the other hand, the best results concerning some of the fundamental problems in distributed computing can potentially be dramatically improved upon by taking advantage of the superior resources and processing power that quantum mechanics offers. This survey has the purpose to highlight both of these benefits. We first review the current results regarding the implementation of arbitrary quantum algorithms on distributed hardware. We then discuss existing proposals for quantum solutions of leader election - a fundamental problem from distributed computing. Quantum mechanics allows leader election to be solved with no communication, provided that certain pre-shared entanglement is already in place. Further, an impossibility result from classical distributed computing is circumvented by the quantum solution of anonymous leader election - a unique leader is elected in finite time with certainty. Finally, we discuss the viability of these proposals from a practical perspective. Although, theoretically, distributed quantum computing looks promising, it is still unclear how to build quantum hardware and how to create and maintain robust large-scale entangled states. Moreover, it is not clear whether the costs of creating entangled states and working with them are smaller than the costs of existing classical solutions.<\/jats:p>","DOI":"10.1145\/1412700.1412718","type":"journal-article","created":{"date-parts":[[2008,9,23]],"date-time":"2008-09-23T13:37:59Z","timestamp":1222177079000},"page":"77-95","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Distributed quantum computing"],"prefix":"10.1145","volume":"39","author":[{"given":"Vasil S.","family":"Denchev","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]}],"member":"320","published-online":{"date-parts":[[2008,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.54.3824"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.63.012307"},{"key":"e_1_2_1_4_1","unstructured":"Brassard G. Hoyer P. Mosca M. and Tapp A. Quantum amplitude amplification and estimation 2000 quant-ph\/0005055.  Brassard G. Hoyer P. Mosca M. and Tapp A. Quantum amplitude amplification and estimation 2000 quant-ph\/0005055."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.037902"},{"key":"e_1_2_1_6_1","volume-title":"Vrije Universiteit Brussel","author":"D'Hondt E.","year":"2005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.26421\/QIC6.2-3","article-title":"The Computational Power of the W and GHZ states","volume":"6","author":"D'Hondt E.","year":"2006","journal-title":"Quantum Information and Computation"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.062314"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02728628"},{"key":"e_1_2_1_10_1","volume-title":"Institute for Algorithms and Cognitive Systems","author":"Eck M.","year":"2000"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.200403"},{"key":"e_1_2_1_12_1","volume-title":"Methuen and Co Ltd","author":"Einstein A.","year":"1916"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.47.777"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.052317"},{"key":"e_1_2_1_15_1","unstructured":"Ekert A. and Jozsa R. Quantum algorithms: Entanglement enhanced information processing. ArXiv Quantum Physics e-prints (1998) quant-ph\/9803072.  Ekert A. and Jozsa R. Quantum algorithms: Entanglement enhanced information processing. ArXiv Quantum Physics e-prints (1998) quant-ph\/9803072."},{"key":"e_1_2_1_16_1","first-page":"73","volume-title":"Kluwer Academic Press","author":"Greenberger D. M.","year":"1989"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_18_1","volume-title":"Eds","author":"Jozsa R.","year":"1998"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2002.1097"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.047901"},{"key":"e_1_2_1_21_1","volume-title":"Morgan Kaufmann Publishers","author":"Lynch N.","year":"1997"},{"key":"e_1_2_1_22_1","volume-title":"Keio University","author":"Meter III, R. D. V.","year":"2006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052308"},{"key":"e_1_2_1_24_1","volume-title":"Cambridge University Press","author":"Nielsen M.","year":"2000"},{"key":"e_1_2_1_25_1","unstructured":"Pal S. P. Singh S. K. and Kumar S. Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks. ArXiv Quantum Physics e-prints (June 2003) quantph\/ 0306195.  Pal S. P. Singh S. K. and Kumar S. Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks. ArXiv Quantum Physics e-prints (June 2003) quantph\/ 0306195."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.80.3891"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the International Symposium on Foundations of Quantum Mechanics","author":"Shimony A.","year":"1984"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_29_1","unstructured":"Singh S. K. Kumar S. and Pal S. P. Characterizing the combinatorics of distributed EPR pairs for multi-partite entanglement. ArXiv Quantum Physics e-prints (June 2003) quant-ph\/0306049.  Singh S. K. Kumar S. and Pal S. P. Characterizing the combinatorics of distributed EPR pairs for multi-partite entanglement. ArXiv Quantum Physics e-prints (June 2003) quant-ph\/0306049."},{"key":"e_1_2_1_30_1","volume-title":"University of Tokyo","author":"Tani S.","year":"2006"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_48"},{"key":"e_1_2_1_32_1","first-page":"11","volume-title":"Proceedings of ERATO conference on Quantum Information Science","author":"Tani S.","year":"2005"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/517021"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.64.010102"},{"key":"e_1_2_1_35_1","series-title":"Proceedings of Society of Photographic Instrumentation Engineers Conference","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1117\/12.546504","volume-title":"Quantum Information and Computation II (Aug.","author":"Yimsiriwattana A.","year":"2004"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Yimsiriwattana A. and Lomonaco Jr. S. J. Generalized GHZ States and Distributed Quantum Computing. ArXiv Quantum Physics e-prints (Feb. 2004) quant-ph\/0402148.  Yimsiriwattana A. and Lomonaco Jr. S. J. Generalized GHZ States and Distributed Quantum Computing. ArXiv Quantum Physics e-prints (Feb. 2004) quant-ph\/0402148.","DOI":"10.1090\/conm\/381\/07096"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412700.1412718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412700.1412718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412700.1412718"}},"subtitle":["a new frontier in distributed systems or science fiction?"],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1412700.1412718"],"URL":"https:\/\/doi.org\/10.1145\/1412700.1412718","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2008-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}