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

arXiv:0810.5317 · ACM SIGACT News

Can quantum mechanics help distributed computing?

Anne Broadbent, Alain Tapp

Published Sep 1, 2008• 28 citations
arXivHTMLPDF

Abstract

We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.

DOI
10.1145/1412700.1412717

Related papers

CAN QUANTUM MECHANICS HELP DISTRIBUTED COMPUTING?

Anne Broadbent, Alain Tapp

We present a brief survey of results where quantum information processing is useful for performing distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.

International Journal of Quantum Information•Feb 1, 2010•1 citation

Distributed quantum information processing: a review of recent progress

Johannes Knörzer, Xiaoyu Liu, Benjamin F. Schiffer +1 more

Distributed quantum information processing seeks to overcome the scalability limitations of monolithic quantum devices by interconnecting multiple quantum processing nodes via classical and quantum communication. This approach extends the capabilities of individual devices, enabling access to larger problem instances and novel algorithmic techniques. Beyond increasing qubit counts, it also enables qualitatively new capabilities, such as joint measurements on multiple copies of high-dimensional quantum states. The distinction between single-copy and multi-copy access reveals important differences in task complexity and helps identify which computational problems stand to benefit from distributed quantum resources. At the same time, it highlights trade-offs between classical and quantum communication models and the practical challenges involved in realizing them experimentally. In this review, we contextualize recent developments by surveying the theoretical foundations of distributed quantum protocols and examining the experimental platforms and algorithmic applications that realize them in practice.

arXiv:2510.15630•Reports on Progress in Physics•May 29, 2026•5 citations

Distributed quantum computing

Vasil S. Denchev, Gopal Pandurangan

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.

ACM SIGACT News•Sep 1, 2008•73 citations

Nonlocality and communication complexity

Harry Buhrman, Richard Cleve, Serge Massar +1 more

Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary $k$-bit messages cannot be compressed into messages of $k\ensuremath{-}1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.

arXiv:0907.3584•Reviews of Modern Physics•Mar 11, 2010•622 citations

Preprint arXiv:2510.15630 Submitted on 17 Oct 2025

Johannes Knörzer, X. Liu, B. Schiffer +1 more

Distributed quantum information processing seeks to overcome the scalability limitations of monolithic quantum devices by interconnecting multiple quantum processing nodes via classical and quantum communication. This approach extends the capabilities of individual devices, enabling access to larger problem instances and novel algorithmic techniques. Beyond increasing qubit counts, it also enables qualitatively new capabilities, such as joint measurements on multiple copies of high-dimensional quantum states. The distinction between single-copy and multi-copy access reveals important differences in task complexity and helps identify which computational problems stand to benefit from distributed quantum resources. At the same time, it highlights trade-offs between classical and quantum communication models and the practical challenges involved in realizing them experimentally. In this review, we contextualize recent developments by surveying the theoretical foundations of distributed quantum protocols and examining the experimental platforms and algorithmic applications that realize them in practice.

•Oct 20, 2025•0 citations

Can quantum communication speed up distributed computation?

Michael Elkin, Hartmut Klauck, Danupon Nanongkai +1 more

The focus of this paper is on quantum distributed computation, where we investigate whether quantum communication can help in speeding up distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication does not help in substantially speeding up distributed algorithms for these problems compared to the classical setting.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 15, 2014•39 citations
We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.
Distributed quantum information processing seeks to overcome the scalability limitations of monolithic quantum devices by interconnecting multiple quantum processing nodes via classical and quantum communication. This approach extends the capabilities of individual devices, enabling access to larger problem instances and novel algorithmic techniques. Beyond increasing qubit counts, it also enables qualitatively new capabilities, such as joint measurements on multiple copies of high-dimensional quantum states. The distinction between single-copy and multi-copy access reveals important differences in task complexity and helps identify which computational problems stand to benefit from distributed quantum resources. At the same time, it highlights trade-offs between classical and quantum communication models and the practical challenges involved in realizing them experimentally. In this review, we contextualize recent developments by surveying the theoretical foundations of distributed quantum protocols and examining the experimental platforms and algorithmic applications that realize them in practice.
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.
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary kkk-bit messages cannot be compressed into messages of $k\ensuremath{-}1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.
Distributed quantum information processing seeks to overcome the scalability limitations of monolithic quantum devices by interconnecting multiple quantum processing nodes via classical and quantum communication. This approach extends the capabilities of individual devices, enabling access to larger problem instances and novel algorithmic techniques. Beyond increasing qubit counts, it also enables qualitatively new capabilities, such as joint measurements on multiple copies of high-dimensional quantum states. The distinction between single-copy and multi-copy access reveals important differences in task complexity and helps identify which computational problems stand to benefit from distributed quantum resources. At the same time, it highlights trade-offs between classical and quantum communication models and the practical challenges involved in realizing them experimentally. In this review, we contextualize recent developments by surveying the theoretical foundations of distributed quantum protocols and examining the experimental platforms and algorithmic applications that realize them in practice.