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

Distributed Computing Model: Classical vs. Quantum vs. Post-Quantum

Sutapa Saha, Tamal Guha, Some Sankar Bhattacharya, Manik Banik

Published Dec 10, 2020• 2 citations
OpenAlex

Abstract

Computation refers to an algorithmic process of producing outputs from a given set of inputs. We consider a particular model of computation where the computing device is comprised of several components/ports placed at different spacetime locations -- the inputs are distributed among different ports, whereas the output is to be assessed by some other port. Importantly, communications among the different ports are limited as the physical systems allowed to be transmitted among the different ports are constrained with information theoretic restrictions. Interestingly, this limited communication distributed computing prototype provides an efficient modus operandi to compare the computational strength of different mathematical models used to describe those physical systems. We come up with computing tasks where quantum theory outperforms its classical counterpart. More surprisingly, a broader class of operational theories with state or/and effect space structures more exotic than quantum theory turns out to be suboptimal in performing some distributed computing tasks. We characterize the computations that can be perfectly accomplished in quantum theory but not in other theories. The proposed computing model thus provides a new approach to single out quantum theory in the theory space and promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.

Related papers

Quantum theory is exclusive: a distributed computing setup

Sutapa Saha, Tamal Guha, Some Sankar Bhattacharya +1 more

The framework of distributed computing, consisting of several spatially separated input-output servers, has immense importance in distant data manipulation. One of the most challenging parts of this setting is to optimize the use of information transmission lines among distant servers. In this work, we have modeled such a physically motivated distributed computing setup for which quantum communication outperforms its classical counterpart, in terms of a limited usage of noiseless transmission lines. Moreover, a broader class of communication entities, that allow state-effect description more exotic than quantum and are described within the framework of generalized probabilistic theory, also fail to meet the strength of quantum theory. The computational strength of quantum communication has further been justified in terms of a stronger version of this task, namely the delayed-choice distributed computation. The proposed task thus provides a new approach to operationally single out quantum theory in the theory-space and hence promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.

arXiv:2012.05781•Dec 10, 2020•6 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•662 citations

On the Limits of Distributed Quantum Computing

Francesco d’Amore

Quantum advantage is well-established in centralized computing, where quantum algorithms can solve certain problems exponentially faster than classical ones. In the distributed setting, significant progress has been made in bandwidth-limited networks, where quantum distributed networks have shown computational advantages over classical counterparts. However, the potential of quantum computing in networks that are constrained only by large distances is not yet understood. We focus on the LOCAL model of computation (Linial, FOCS 1987), a distributed computational model where computational power and communication bandwidth are unconstrained, and its quantum generalization. In this brief survey, we summarize recent progress on the quantum-LOCAL model outlining its limitations with respect to its classical counterpart: we discuss emerging techniques, and highlight open research questions that could guide future efforts in the field.

arXiv:2503.11394•Mar 14, 2025•0 citations

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

RECEIVER DESIGN FOR QUANTUM COMMUNICATION

Nicola Dalla Pozza

Born about a century ago, Quantum Mechanics has revolutionized the description and the interpretation of Physics at sub-microscopic level. In the last decades, due to the influence of mathematical and engineering research fields, Quantum Mechanics has given birth to related research areas like Quantum Computation, Quantum Information and Quantum Communication. With the discovery of the laser, and later the development of fiber optics and satellite networks, Quantum Communication and Quantum Optics seems to have a natural field of application in Communication Systems. Despite this, the interest in this technology and studies for communication purpose has been overshadowed by the great results in communication networks achieved in the last decades with classical paradigms. However, due to the increasing demand of communication data rate, system designers are now looking at Quantum Mechanics for new and more performanting solutions in communication purposes. Early theoretical studies on Quantum Discrimination Theory and Quantum Information predict better performance for Communication Systems that take advantage of the quantum laws. In addition, Quantum Mechanics provides the deepest description of the physical phenomena, and there are scenarios where a quantum model fits best, as in in deep space communications, where the received signal is really weak, or in a satellite networks, where we are interested in strongly reducing the power of transmitted signals, possibly without sacrificing performance significantly. However, if on one side Quantum Communication Theory promises great gains in the performance of communication systems, on the other hand it fails to describe how to implement physical devices that reach these ultimate limits. So far, only a few architectures achieving these performances are known, and only for simple modulation formats. We are interested in the scenario of optical communications, where the message transmitted is encoded in a sequence of coherent states. Transmitter devices for coherent modulation are well known and consist in laser pulse generators. Instead, receiver implementations working at the quantum limit performance limit are yet to be found. In this Thesis I deal with different topics in the quantum transmission scenario. First, I review existing classical (suboptimal) and quantum (suboptimal and optimal) receiver schemes for the binary coherent modulation. I present a new formulation of the optimal scheme known as Dolinar Receiver with the multiple copies problem, focusing on the information gained during the measurement. Second, I analyze the binary communication in a noisy environment, studying the error probability and the capacity of the binary channel induced. Given the description of the quantum channel, I optimize both the transmitted quantum states and the measurement operators employed in the communication. Third, I consider the Pulse Position Modulation, that is particularly suitable for space and satellite communication due to its simplicity of implementation and high capacity. I review some known suboptimal receivers, and I propose a receiver scheme which approaches the limit performance predicted with quantum theory outperforming the existing schemes. To sum up the results of this Thesis, in order to approach the limit performance predicted by Quantum Mechanics, an optimization is always necessary to exceed the classical effects and trigger the quantum phenomena. In particular, the information gained during the measurement plays an important role, for example in the definition of adaptive receivers. In this Thesis both these aspects have been deeply investigated.

•Jul 24, 2013•0 citations

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

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•80 citations
Computation refers to an algorithmic process of producing outputs from a given set of inputs. We consider a particular model of computation where the computing device is comprised of several components/ports placed at different spacetime locations -- the inputs are distributed among different ports, whereas the output is to be assessed by some other port. Importantly, communications among the different ports are limited as the physical systems allowed to be transmitted among the different ports are constrained with information theoretic restrictions. Interestingly, this limited communication distributed computing prototype provides an efficient modus operandi to compare the computational strength of different mathematical models used to describe those physical systems. We come up with computing tasks where quantum theory outperforms its classical counterpart. More surprisingly, a broader class of operational theories with state or/and effect space structures more exotic than quantum theory turns out to be suboptimal in performing some distributed computing tasks. We characterize the computations that can be perfectly accomplished in quantum theory but not in other theories. The proposed computing model thus provides a new approach to single out quantum theory in the theory space and promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.
The framework of distributed computing, consisting of several spatially separated input-output servers, has immense importance in distant data manipulation. One of the most challenging parts of this setting is to optimize the use of information transmission lines among distant servers. In this work, we have modeled such a physically motivated distributed computing setup for which quantum communication outperforms its classical counterpart, in terms of a limited usage of noiseless transmission lines. Moreover, a broader class of communication entities, that allow state-effect description more exotic than quantum and are described within the framework of generalized probabilistic theory, also fail to meet the strength of quantum theory. The computational strength of quantum communication has further been justified in terms of a stronger version of this task, namely the delayed-choice distributed computation. The proposed task thus provides a new approach to operationally single out quantum theory in the theory-space and hence promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.
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.
Quantum advantage is well-established in centralized computing, where quantum algorithms can solve certain problems exponentially faster than classical ones. In the distributed setting, significant progress has been made in bandwidth-limited networks, where quantum distributed networks have shown computational advantages over classical counterparts. However, the potential of quantum computing in networks that are constrained only by large distances is not yet understood. We focus on the LOCAL model of computation (Linial, FOCS 1987), a distributed computational model where computational power and communication bandwidth are unconstrained, and its quantum generalization. In this brief survey, we summarize recent progress on the quantum-LOCAL model outlining its limitations with respect to its classical counterpart: we discuss emerging techniques, and highlight open research questions that could guide future efforts in the field.
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.
Born about a century ago, Quantum Mechanics has revolutionized the description and the interpretation of Physics at sub-microscopic level. In the last decades, due to the influence of mathematical and engineering research fields, Quantum Mechanics has given birth to related research areas like Quantum Computation, Quantum Information and Quantum Communication. With the discovery of the laser, and later the development of fiber optics and satellite networks, Quantum Communication and Quantum Optics seems to have a natural field of application in Communication Systems. Despite this, the interest in this technology and studies for communication purpose has been overshadowed by the great results in communication networks achieved in the last decades with classical paradigms. However, due to the increasing demand of communication data rate, system designers are now looking at Quantum Mechanics for new and more performanting solutions in communication purposes. Early theoretical studies on Quantum Discrimination Theory and Quantum Information predict better performance for Communication Systems that take advantage of the quantum laws. In addition, Quantum Mechanics provides the deepest description of the physical phenomena, and there are scenarios where a quantum model fits best, as in in deep space communications, where the received signal is really weak, or in a satellite networks, where we are interested in strongly reducing the power of transmitted signals, possibly without sacrificing performance significantly. However, if on one side Quantum Communication Theory promises great gains in the performance of communication systems, on the other hand it fails to describe how to implement physical devices that reach these ultimate limits. So far, only a few architectures achieving these performances are known, and only for simple modulation formats. We are interested in the scenario of optical communications, where the message transmitted is encoded in a sequence of coherent states. Transmitter devices for coherent modulation are well known and consist in laser pulse generators. Instead, receiver implementations working at the quantum limit performance limit are yet to be found. In this Thesis I deal with different topics in the quantum transmission scenario. First, I review existing classical (suboptimal) and quantum (suboptimal and optimal) receiver schemes for the binary coherent modulation. I present a new formulation of the optimal scheme known as Dolinar Receiver with the multiple copies problem, focusing on the information gained during the measurement. Second, I analyze the binary communication in a noisy environment, studying the error probability and the capacity of the binary channel induced. Given the description of the quantum channel, I optimize both the transmitted quantum states and the measurement operators employed in the communication. Third, I consider the Pulse Position Modulation, that is particularly suitable for space and satellite communication due to its simplicity of implementation and high capacity. I review some known suboptimal receivers, and I propose a receiver scheme which approaches the limit performance predicted with quantum theory outperforming the existing schemes. To sum up the results of this Thesis, in order to approach the limit performance predicted by Quantum Mechanics, an optimization is always necessary to exceed the classical effects and trigger the quantum phenomena. In particular, the information gained during the measurement plays an important role, for example in the definition of adaptive receivers. In this Thesis both these aspects have been deeply investigated.
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.