Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGACT News

Distributed quantum computing: a new frontier in distributed systems or science fiction?

Vasil S. Denchev, Gopal Pandurangan

Published Sep 1, 2008• 80 citations
Publisher

Abstract

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.

DOI
10.1145/1412700.1412718

Related papers

Distributed quantum computing models: Study of architectures and models for the distribution of quantum computing tasks across multiple quantum nodes

Akaash Vishal Hazarika, Mahak Shah

The exploration of distributed quantum computing (DQC) represents a significant frontier in quantum information science, aiming to harness the unique properties of quantum mechanics to solve complex computational problems effectively. This paper discusses the diverse architectures and models that facilitate the distribution of quantum computing tasks across multiple quantum nodes, thereby addressing the limitations inherent in single quantum devices. DQC systems exploit the principles of superposition and entanglement to enhance computational capabilities beyond what classical computing systems can achieve. We examine various DQC architectures, including both quantum-classical hybrid systems and fully quantum distributed systems, highlighting their respective benefits and challenges. Key issues such as coherence, communication overhead, and error correction are discussed in detail, and we analyze specific use cases where DQC demonstrates superior performance relative to classical computing approaches, including optimization problems in logistics and finance, as well as quantum simulations for material science. Furthermore, we identify future research directions aimed at overcoming existing barriers to the practical implementation of DQC systems. By assessing the current landscape and future possibilities of DQC, this paper underscores the transformative potential of distributed quantum computing in various fields, paving the way for realizing more complex quantum algorithms and applications.

International Journal of Science and Research Archive•Dec 30, 2024•9 citations

Quantum Computing: The Next Frontier in Technology

Aruna M. Jarju

Quantum computing represents a revolutionary leap in computational power, leveraging the principles of quantum mechanics to process information in fundamentally new ways. Unlike classical computers, which use bits to represent data as 0s or 1s, quantum computers use quantum bits or qubits, enabling the phenomena of superposition and entanglement to perform complex calculations more efficiently (Nielsen & Chuang, 2010). This article explores the basic principles of quantum computing, the different models and algorithms that have been developed, and the current state of quantum hardware. The power of quantum computing lies in its ability to solve certain types of problems exponentially faster than classical computers. For instance, Shor's algorithm can factorize large integers in polynomial time, posing a significant threat to classical encryption methods (Shor, 1997). Similarly, Grover's algorithm provides a quadratic speedup for unstructured search problems, showcasing the potential for dramatic improvements in database search capabilities (Grover, 1996). These algorithms exemplify how quantum computing can revolutionize fields that rely on complex computations. Quantum hardware, however, is still in its nascent stage, with significant challenges to be overcome. Current quantum computers, such as those developed by IBM and Google, have demonstrated quantum supremacy but are limited by issues of qubit coherence and error rates (Arute et al., 2019). Quantum error correction and the development of more stable qubit technologies are critical areas of ongoing research (Preskill, 2018). Despite these challenges, recent advancements in quantum hardware and algorithms continue to drive the field forward, promising transformative impacts on industries such as cryptography, drug discovery, and artificial intelligence. As quantum computing continues to advance, it holds the promise of solving problems that are currently intractable for classical computers, paving the way for unprecedented technological and scientific advancements (Shor, 1997; Grover, 1996). This article provides a comprehensive overview of the current landscape of quantum computing, discussing its foundational principles, key algorithms, hardware challenges, and potential applications. By understanding these aspects, we can better appreciate the profound implications of quantum computing for the future of technology and science.

•Aug 11, 2025•2 citations

Quantum Communication Advantage for Leader Election and Agreement

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies.

arXiv:2502.07416•ACM Symposium on Principles of Distributed Computing (PODC)•Jun 13, 2025•5 citations

Quantum Computing: Principles, Challenges, and Future Directions

Aayush Manish Chitnis

Quantum computing isn't merely another step forward in technology; it represents a leap into an entirely new paradigm for understanding information. By harnessing the strange but powerful principles of quantum mechanics, quantum computers use qubits that can exist in multiple states at once, connect instantly through entanglement, and solve certain problems far faster than any classical machine. This paper explores the fundamentals of quantum computing, from its theoretical roots to the breakthroughs and setbacks shaping its present. We examine the engineering and scientific challenges - from fragile qubits to daunting scalability issues - and the immense promise they hold for fields like cryptography, artificial intelligence, drug discovery, and materials science. Finally, we consider the future impact of this technology, both its opportunities and its risks, and how it may redefine industries, research methods, and even our approach to solving humanity's hardest problems. The purpose of this paper is to examine the fundamental principles, developmental trajectory, current challenges, and prospective impacts of quantum computing across scientific, industrial, and societal domains. Given its potential to reshape computational capabilities and address complex global challenges, this study holds significance for researchers, policymakers, and industry leaders seeking to understand and navigate the transition toward quantum technologies.

International Journal of Science and Research (IJSR)•Aug 18, 2025•0 citations

Computing on Anonymous Quantum Network

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

The anonymous network model was introduced by Angluin in [STOC '80, to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties.In this model, all parties with the same number of communication links are identical.When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party.It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication.This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed [TOCT, vol.4,no.1, article 1].The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty.This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election.The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.

arXiv:1001.5307•Chicago Journal of Theoretical Computer Science•Jan 1, 2014•8 citations

Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is $\tilde{O}(n)$ for leader election, broadcast, and MST, and $\tilde{O}(\sqrt{mn})$ for BFS ($n$ and $m$ are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of $\tilde{O}(\sqrt{mn})$ for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since $Ω(m)$ is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.

quant-pharXiv:2602.15529•Feb 18, 2026•2 citations
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.
The exploration of distributed quantum computing (DQC) represents a significant frontier in quantum information science, aiming to harness the unique properties of quantum mechanics to solve complex computational problems effectively. This paper discusses the diverse architectures and models that facilitate the distribution of quantum computing tasks across multiple quantum nodes, thereby addressing the limitations inherent in single quantum devices. DQC systems exploit the principles of superposition and entanglement to enhance computational capabilities beyond what classical computing systems can achieve. We examine various DQC architectures, including both quantum-classical hybrid systems and fully quantum distributed systems, highlighting their respective benefits and challenges. Key issues such as coherence, communication overhead, and error correction are discussed in detail, and we analyze specific use cases where DQC demonstrates superior performance relative to classical computing approaches, including optimization problems in logistics and finance, as well as quantum simulations for material science. Furthermore, we identify future research directions aimed at overcoming existing barriers to the practical implementation of DQC systems. By assessing the current landscape and future possibilities of DQC, this paper underscores the transformative potential of distributed quantum computing in various fields, paving the way for realizing more complex quantum algorithms and applications.
Quantum computing represents a revolutionary leap in computational power, leveraging the principles of quantum mechanics to process information in fundamentally new ways. Unlike classical computers, which use bits to represent data as 0s or 1s, quantum computers use quantum bits or qubits, enabling the phenomena of superposition and entanglement to perform complex calculations more efficiently (Nielsen & Chuang, 2010). This article explores the basic principles of quantum computing, the different models and algorithms that have been developed, and the current state of quantum hardware. The power of quantum computing lies in its ability to solve certain types of problems exponentially faster than classical computers. For instance, Shor's algorithm can factorize large integers in polynomial time, posing a significant threat to classical encryption methods (Shor, 1997). Similarly, Grover's algorithm provides a quadratic speedup for unstructured search problems, showcasing the potential for dramatic improvements in database search capabilities (Grover, 1996). These algorithms exemplify how quantum computing can revolutionize fields that rely on complex computations. Quantum hardware, however, is still in its nascent stage, with significant challenges to be overcome. Current quantum computers, such as those developed by IBM and Google, have demonstrated quantum supremacy but are limited by issues of qubit coherence and error rates (Arute et al., 2019). Quantum error correction and the development of more stable qubit technologies are critical areas of ongoing research (Preskill, 2018). Despite these challenges, recent advancements in quantum hardware and algorithms continue to drive the field forward, promising transformative impacts on industries such as cryptography, drug discovery, and artificial intelligence. As quantum computing continues to advance, it holds the promise of solving problems that are currently intractable for classical computers, paving the way for unprecedented technological and scientific advancements (Shor, 1997; Grover, 1996). This article provides a comprehensive overview of the current landscape of quantum computing, discussing its foundational principles, key algorithms, hardware challenges, and potential applications. By understanding these aspects, we can better appreciate the profound implications of quantum computing for the future of technology and science.
Quantum computing isn't merely another step forward in technology; it represents a leap into an entirely new paradigm for understanding information. By harnessing the strange but powerful principles of quantum mechanics, quantum computers use qubits that can exist in multiple states at once, connect instantly through entanglement, and solve certain problems far faster than any classical machine. This paper explores the fundamentals of quantum computing, from its theoretical roots to the breakthroughs and setbacks shaping its present. We examine the engineering and scientific challenges - from fragile qubits to daunting scalability issues - and the immense promise they hold for fields like cryptography, artificial intelligence, drug discovery, and materials science. Finally, we consider the future impact of this technology, both its opportunities and its risks, and how it may redefine industries, research methods, and even our approach to solving humanity's hardest problems. The purpose of this paper is to examine the fundamental principles, developmental trajectory, current challenges, and prospective impacts of quantum computing across scientific, industrial, and societal domains. Given its potential to reshape computational capabilities and address complex global challenges, this study holds significance for researchers, policymakers, and industry leaders seeking to understand and navigate the transition toward quantum technologies.
The anonymous network model was introduced by Angluin in [STOC '80, to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties.In this model, all parties with the same number of communication links are identical.When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party.It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication.This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed [TOCT, vol.4,no.1, article 1].The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty.This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election.The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is O~(n)\tilde{O}(n)O~(n) for leader election, broadcast, and MST, and O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for BFS (nnn and mmm are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since Ω(m)Ω(m)Ω(m) is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.