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).
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).
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.
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to O(n) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to Ω(n⋅log3n) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).
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) for leader election, broadcast, and MST, and O~(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 O~(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.
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.
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel N and any quantum fault tolerance schemes against i.i.d. noise modeled by N, we prove a lower bound of max{Q(N)−1n,αNlogT} on the number of physical qubits, for circuits of length T and width n. Here, Q(N) denotes the quantum capacity of N and αN>0 is a constant only depending on the channel N. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).