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• 0 citations

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, 20070 citations

Fast quantum byzantine agreement

Michael Ben-Or, Avinatan Hassidim

We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).

ACM Symposium on Theory of Computing (STOC)May 22, 2005120 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.10618Leibniz international proceedings in informaticsMay 18, 20232 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/0701112Jan 16, 20076 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, 20097 citations

Fault-Tolerant Quantum Communication over r-Robust Graph Topologies under Adversarial and Noisy Conditions

Suresh Kumar Jha, Siddhanta Kumar Singh, Aditya Narayan Hati

Abstract The realization of scalable quantum communication networks faces critical challenges from decoherence, noise, and adversarial attacks. This paper presents a comprehensive framework for fault-tolerant quantum communication using \textit{r}-robust graph topologies, which ensure strong connectivity and resilience in the presence of both random failures and Byzantine adversaries. We formalize \textit{r}-robustness in single-layer and multiplex quantum networks and derive theoretical bounds on fidelity, consensus success, and error propagation. A hybrid quantum-classical protocol is proposed that leverages multi-path entanglement and quantum certificate-based identity enforcement. Extensive simulations using Qiskit and NetworkX show that \textit{r}-robust networks improve average entanglement fidelity by up to 26\%, achieve over 95\% consensus success under 30\% adversarial nodes, and exponentially suppress error rates. Compared to ring, scale-free, and random graphs, \textit{r}-robust topologies provide superior robustness with moderate resource overhead. Our results establish a graph-theoretic foundation for constructing secure, resilient, and NISQ-compatible quantum networks capable of sustaining high-performance communication in noisy and adversarial environments.

Jan 8, 20260 citations