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 Symposium on Principles of Distributed Computing (PODC)

Brief Announcement: Improved Consensus in Quantum Networks

MohammadTaghi Hajiaghayi, Dariusz Rafal Kowalski, Jan Olkowski

Published Jun 16, 2023• 2 citations
Publisher

Abstract

Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.

DOI
10.1145/3583668.3594600

Related papers

Quantum Distributed Consensus

Louie Helm, Christine Julien

Distributed consensus is possible for asynchronous communication networks when assisted by quantum mechanical effects. Previous results are extended to show that consensus is possible even in the presence of byzantine process failures. This result directly contradicts the FLP impossibility result which states that distributed consensus is impossible when even one faulty networked process exists in the group. PODC’08, August 18–21, 2008, p445, Toronto, Ontario, Canada. ACM 978-1-59593-9890/08/08. 1. DISTRIBUTED COMPUTING IS PHYSICAL Distributed computing is concerned with what can be accomplished using systems of networked processors. As with all information processing devices, these systems are necessarily physical and ultimately bound by the laws of physics[Land88]. Therefore, when proving impossibility results and bounds on algorithmic efficiency, it only makes sense to consider the possibilities offered, not only by classical information processing, but also the effects of quantum mechanics[NC00]. Recent results have shown that shared quantum resources make problems like anonymous leader election and distributed consensus possible under conditions where no classical algorithm could perform the same tasks[DP06]. These results are extended here to show that shared quantum resources allow fault-tolerant consensus in direct contradiction of previous impossibility results[FLP85]. Although this research is largely self-contained, a basic understanding of distributed computing is assumed of the reader along with a passing understanding of linear algebra which is necessary to understand the reasoning behind the algorithm detailed in section 4. A thorough understanding of quantum mechanics is recommended, although a reference of the specific quantum mechanical notation required to follow later reasoning in section 4 is detailed in section 3. A computer scientist unfamiliar with quantum mechanics would be well served to reference chapter 2 of [NC00] in order to gain a deeper understanding of the notation covered in section 3 of this paper. Likewise, a quantum physicist would be well served to reference chapter 15 of [Garg04] to more deeply understand the fault modeling of distributed computing covered in section 2 and section 5.

•Jan 1, 2007•0 citations

Fault-Tolerant Quantum Computation

Daniel Gottesman

I give a brief overview of fault-tolerant quantum computation, with an emphasis on recent work and open questions.

arXiv:quant-ph/0701112•Jan 16, 2007•19 citations

Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication

MohammadTaghi Hajiaghayi, Dariusz Rafal Kowalski, Jan Olkowski

Fault-tolerant Consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound Ω(√{n/log n}) on expected time complexity of Consensus in any classical (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the Ω(√{n/log n}) barrier for consensus in the classical (deterministic and randomized) networks by enhancing the model with quantum channels. In such networks, quantum communication between every pair of processes participating in the protocol is also allowed. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3. In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound Ω(√{n/log n}) for the classical computation models).

arXiv:2305.10618•Leibniz international proceedings in informatics•May 18, 2023•5 citations

Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication

Jan Olkowski

We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to $t\le(1/3-\varepsilon)n$ processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability $1$. It uses $O(\log^4 n)$ rounds, $O(n\log^8 n)$ qubits, and $O(n^2\log^8 n)$ classical bits in expectation, with constants depending on $\varepsilon$. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves $O(1)$ expected rounds but whose Byzantine coin implementation requires $Ω(n^4\log n)$ qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an $Ω(t^2)$ lower bound on worst-case expected total communication. For $t=Θ(n)$, the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.

arXiv:2611.05598•Nov 3, 2026•0 citations

The idiots guide to Quantum Error Correction

Simon J. Devitt, Kae Nemoto, William J. Munro

Contents Quantum Error Correction and fault-tolerant quantum computation represent arguably the most vital theoretical aspect of quantum information processing. It was well known from the early developments of this exciting field that the fragility of coherent quantum systems would be a catastrophic obstacle to the development of large scale quantum computers. The introduction of

•May 18, 2009•7 citations

Quantum distributed consensus

Louis K. Helm

Distributed consensus can be achieved on asynchronous communication networks when assisted by quantum mechanics. This contradicts the FLP impossibility result by achieving consensus in the presence of faults.

ACM Symposium on Principles of Distributed Computing (PODC)•Aug 18, 2008•6 citations
Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.
Distributed consensus is possible for asynchronous communication networks when assisted by quantum mechanical effects. Previous results are extended to show that consensus is possible even in the presence of byzantine process failures. This result directly contradicts the FLP impossibility result which states that distributed consensus is impossible when even one faulty networked process exists in the group. PODC’08, August 18–21, 2008, p445, Toronto, Ontario, Canada. ACM 978-1-59593-9890/08/08. 1. DISTRIBUTED COMPUTING IS PHYSICAL Distributed computing is concerned with what can be accomplished using systems of networked processors. As with all information processing devices, these systems are necessarily physical and ultimately bound by the laws of physics[Land88]. Therefore, when proving impossibility results and bounds on algorithmic efficiency, it only makes sense to consider the possibilities offered, not only by classical information processing, but also the effects of quantum mechanics[NC00]. Recent results have shown that shared quantum resources make problems like anonymous leader election and distributed consensus possible under conditions where no classical algorithm could perform the same tasks[DP06]. These results are extended here to show that shared quantum resources allow fault-tolerant consensus in direct contradiction of previous impossibility results[FLP85]. Although this research is largely self-contained, a basic understanding of distributed computing is assumed of the reader along with a passing understanding of linear algebra which is necessary to understand the reasoning behind the algorithm detailed in section 4. A thorough understanding of quantum mechanics is recommended, although a reference of the specific quantum mechanical notation required to follow later reasoning in section 4 is detailed in section 3. A computer scientist unfamiliar with quantum mechanics would be well served to reference chapter 2 of [NC00] in order to gain a deeper understanding of the notation covered in section 3 of this paper. Likewise, a quantum physicist would be well served to reference chapter 15 of [Garg04] to more deeply understand the fault modeling of distributed computing covered in section 2 and section 5.
Fault-tolerant Consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound Ω(√{n/log n}) on expected time complexity of Consensus in any classical (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the Ω(√{n/log n}) barrier for consensus in the classical (deterministic and randomized) networks by enhancing the model with quantum channels. In such networks, quantum communication between every pair of processes participating in the protocol is also allowed. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3. In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound Ω(√{n/log n}) for the classical computation models).
We consider synchronous binary Byzantine agreement among nnn processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to t≤(1/3−ε)nt\le(1/3-\varepsilon)nt≤(1/3−ε)n processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability 111. It uses O(log⁡4n)O(\log^4 n)O(log4n) rounds, O(nlog⁡8n)O(n\log^8 n)O(nlog8n) qubits, and O(n2log⁡8n)O(n^2\log^8 n)O(n2log8n) classical bits in expectation, with constants depending on ε\varepsilonε. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves O(1)O(1)O(1) expected rounds but whose Byzantine coin implementation requires Ω(n4log⁡n)Ω(n^4\log n)Ω(n4logn) qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an Ω(t2)Ω(t^2)Ω(t2) lower bound on worst-case expected total communication. For t=Θ(n)t=Θ(n)t=Θ(n), the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.