Coordination

Leader election

Main difference compared to classical seems to be lifting computational assumptions.

Definition a bit inferred from combining [leader_election] and [bit_escrow]

each party $i$ decides $d_{i} \in [n] \cup {err}$
if all honest:
- $P r (d_{i} = err) = 0$
- $P r (d_{i} = i) = \frac{1}{n}$
if player $i$ (NB in [bit_escrow] there are only two) is honest
- $P r (d_{i} = i) \leq \frac{1}{n} + ϵ$

In [exact_leader_election] the outcomes are binary (i.e., me or not me), which may make more sense compared to [leader_election] as it doesn’t need to coordinate necessarily.

Note

Uniqueness of the leader with cheaters seems to be swept under the rug in [leader_election].

Quantum Leader Election

[leader_election]

Idea:

use tournament with weak quantum coin (e.g., [bit_escrow])
NB I’m not sure how they ensure tournament consistency

[FairAndUnbiasedLE]

Consensus

In the Byzantine setting the focus is often on detectable agreement.

See secret sharing.

Algorithm for quantum byzantine agreement

[FastBFT]

constant expected number of rounds compared for the randomized (adaptive adversary)
Assumptions:
- adaptive full information adversary
- failure models: Byzantine / crash faults
States: $\sum_{a = 1}^{n^{3}} ∣ a, \dots, a ⟩$
Byzantine needs verifiable (can agree that secret can be recovered) secret sharing for random numbers

Improved consensus in quantum networks

[ImprovedConsensusFull]

Assumptions:
- adaptive full information adversary
- failure models: Byzantine / crash faults
requires fewer Bell pairs by using some kind of gossip protocol

Note

The arity of entanglement is still $O (n)$

Algorithms based on quantum signatures

Quantum signatures are to a large degree also based on correlated lists):

Beating the fault-tolerance bound for byzantine agreement

[Beating]

Recusrive algorithm, similar to the one in LSP
Unlike LSP, signatures cannot be verified by all the parties
N > 2 f

Simulations / physical realization

Netsquid-based:

Resource-aware System Architectural Model for Implementation of QBA [ResourceQBA]

Proposes specific circuit implementation for the Ben-Or’s algorithm
[Beating]
- The algorithm is from the same paper
- All the quantum part is done in a lab using “four-intensity decoy-state BB84 key generation process”

Lower bounds

number of faults:
- according to [DBAMajorities], $f < n /3$ holds for quantum channels and private coins
- [EasyImpossibility]: impossibility proofs for classical synchronous consensus
  
  Note
  
  Probabilistic Byzantine agreement (Crusader agreement) also requires $f < n /3$ , see decentralized-thoughts
- [MinimalPrimitives]:
  - $f < n /3$ also for randomized algorithms
  - seems to give different bounds based on the number of nodes that a given primitive affects
- [BcastAndPseudoSigs]
number of rounds:
- [LowerBoundRandom]: $Θ (t / n log n)$

Detectable Byzantine agreement (DBA)

Note

Apparently, for DBA none of the algorithms below maintain quantum state, hence the size and decoherence time of quantum memory are irrelevant.

As per [DBAMajorities]:

Correctness all honest players commonly accept or reject the protocol. If all accept, then the protocol achieves broadcast
Completeness if no player is corrupted, all accept
Fairness if any honest player rejects, then the adversary gets no information about the sender’s input

As per [QDBAEPR]:

Correctness If all generals are loyal, protocol achieves Byzantine Agreement
Consistency All loyal generals either follow the same order or abort.
Validity If the commanding general is loyal, then either of the two:
- all loyal lieutenants follow the commander’s order
- all loyal lieutenants abort

Further problem decomposition is presented in [DBAMajorities] introducing

Detectable Precomputation:

Correctness: all honest players commonly accept or reject the protocol. If all accept, then strong broadcast will be achievable
Completeness if no player is corrupted, all accept
Independence any honest player’s input value need not be known

Protocols based on correlated lists

A Quantum solution to the Byzantine agreement problem

[QuantumSolution]

for weak agreement (or detectable broadcast), where a single faulty player may force everyone to abort
States: $∣ A ⟩ = ∣0, 1, 2 ⟩ + ∣1, 2, 0 ⟩ + ∣2, 0, 1 ⟩ - ∣0, 2, 1 ⟩ - ∣1, 0, 2 ⟩ - ∣2, 1, 0 ⟩$ (Aharonov tri-partite qutrit states)
N = 3, f = 1

Experimental demonstration of a quantum protocol for Byzantine agreement and liar detection

[ExperimentalBA]

Explicitly says that the key is to construct secret and correlated lists

Based on the list $l_{A}$ , $l_{B}$ , and $l_{C}$ that are correlated and are produced from 4-qubit entangled states
States: $∣ Ψ^{(4)} ⟩_{abcd} = 2∣0011 ⟩ - ∣0101 ⟩ - ∣0110 ⟩ - ∣1001 ⟩ - ∣1010 ⟩ + 2∣1100 ⟩$
N = 3, f = 1

Quantum detectable Byzantine agreement for distributed data trust management in blockchain:

[QDBABlockchain]

a lot of pairwise interaction among the lieutenants and the general
States: $∣000 ⟩ \pm ∣111 ⟩$ , $∣010 ⟩ \pm ∣101 ⟩$ , $∣011 ⟩ \pm ∣100 ⟩$ (GHZ-like)
N > f + 1

Quantum Byzantine agreement for any number of dishonest parties

[QBADishonest]

trusted quantum source
States: $\sum_{j} ∣ j ⟩ \otimes ∣ j + i_{1} mod d ⟩ \otimes \dots∣ j + i_{n} mod d ⟩$ (multi-partite qudits)
N > f + 1
gives counterexamples for two other works (not listed here) to be incorrect

A quantum detectable Byzantine agreement protocol using only EPR pairs

[QDBAEPR]

States: $∣00 ⟩ + ∣11 ⟩$ (EPR pairs)
N > f + 1

Note

Completeness (see above) is probabilistic here

Simulations / physical realization

[NoiseAwareDBA]:
- filter batches of EPR-pairs testing fidelity and dropping those with the fidelity below the threshold
- noise-mitigation techniques
[InSilicoDBA]:
- uses proprietary simulator
- focus is on the epr algorithm

Oblivious transfer

Quantum case

[EfficientQOT]

[QBCImpossibility]

[FlexibleQuantumQueries]

Other works

[QDC]: not quite a “consensus” as the outcome is _always random
[CompPowerWvsGHZ]: Computational power of W vs. GHZ states in anonymous setting

Simulations / physical realization

[BenchmarkingProtocols] evaluating the following algorithms with NetSquid:
- quantum coin (i.e., smth that can be emitted and later verified)
- anonymous qubit transmission via $W$ -state
- verifiable blind quantum computation
- quantum digital signature
Common sources of noise:
- noisy operations
- noisy memory
- noisy channels

They have implementation.

Cryptography

Digital (pseudo) signatures

Definition of pseudo signatures

Taken from [complete_pseudo_signatures]:

Three parties:

Alice (sender), has input $b \in {0, 1}$ ,
Bob (receiver 1), has output $b_{B} \in {0, 1, ⊥}$ , and
Charlie (receiver 2), has output $b_{C} \in {0, 1, ⊥}$

Two phases:

signature phase where Bot outputs $b_{B}$ and if $b_{B} \neq = ⊥$ proceed to
transfer phase where Charlie outputs $b_{C}$

Properties:

Correctness: if Alice and Bob are honest, $b_{B} = b$ with high probability
Unforgeability: if Alice and Charlie are honest, then probability of $b_{C} \in / {b, ⊥}$ is small
Transferability: if Bob and Charlie are honest then the probability of having both $b_{B} \neq = ⊥$ and $b_{C} \neq = b_{B}$ is small
Secrecy (optional?): Charlie’s view in the signing phase is almost independent from $b$

Quantum algorithms

[QDS]

Consider a set of sufficiently orthogonal (but not orthogonal) functions: $F = ∣ f_{1} ⟩, ∣ f_{2} ⟩, \dots, ∣ f_{N} ⟩$ ,

NB $N$ is much higher than $2^{n}$ , where $n$ is the number of qubits
- public key: generate $k_{0}$ and $k_{1}$ and set public key as $(F, (0, f_{k_{0}^{1}}), (1, f_{k_{1}^{2}}), \dots, (0, f_{k_{0}^{l}}), (1, f_{k_{1}^{l}}))$
- signing: $b \mapsto (b, k_{b}^{1}, \dots, k_{b}^{l})$
- verifying: reverse test checking that all the functions computed right plus two thresholds: $c_{1}$ and $c_{2}$
[QDSNoMemory]

There’re coherent states $∣ α ⟨$ and $∣ - α ⟨$ , s.t. it’s efficient to:
- check they’re the same (null-port must be zero)
- symmetrize two states (giving $∣ (α + β) /2 ⟨$ )
- identify what’s the symmetrized state is
The protocol (Alice is sending to Bob and Charlie):
- private key are random sequences of signs $P K^{k} = (b_{1}^{k}, \dots, b_{L}^{k})$ for $k \in {0, 1}$ and $b \in {- 1, 1}$
- public key are the two sequences of quantum states $∣ b_{l}^{k} α ⟨$
- preparation:
  - Bob and Charlie use QDS multiport to a) check if they get the same state b) symmetrize input
  - Bob and Charlie measure output from multiport to identify what was the sign
- signature: Alice releases $(b, P K^{b})$
- verification:
  - check that there’s equivocation is unlikely (occurrences of null-port being non-zero is low)
  - check that there’s an expected number of unambiguous measurement outcomes (when doing the second step)
  - number of mismatches with the private key should not be too large
    
    NB thresholds for this step are different for Charlie and Bob, which is necessary if Alice tries to make one accept and another reject

See [QMPC]

Simulators

NetSquid
- discrete-time event processing engine
- sparse state representation: ket vector / density matrix / stabilizer state
QuISP
- discrete-time event processing engine
- error-basis representation
- very limited (if existent) support for application-level logic

Quantum Networks

From the point of view of quantum coordination the most crucial services of a quantum network are:

EPR-pair distribution
multi-partite state distribution

Multi-partite state distribution

Distributing Graph States Across Quantum Networks

[GraphStates]

Graph state:

$G = (V, E)$ , where vertices are qubits
Initially all qubits are in $∣ + ⟩$ state, followed by the controlled $Z$ operation (phase flip)

Role of graph states:

any quantum computation can be done in a “one-way” fashion:
1. prepare a graph state
2. perform measurements
3. perform single qubit operations based on 2

Protocols for Creating and Distilling Multipartite GHZ States With Bell Pairs

[GHZ]

Setting:

to correct and track errors it is necessary to perform joint measurements
joint measurements in a distributed quantum computing are enabled by GHZ states
quantum networks should provide this states

Goal: produce GHZ states that at fast rate and with high fidelity

Challenges:

if GHZ states is produced by fusing Bell pairs, the fidelity degrades exponentially
distillation or purification

Approach:

Some form of dynamic programming.

Bibliography

[complete_pseudo_signatures] - Narayanan, Varunand Prabhakaran, Vinod M. and Sangwan, Nehaand Watanabe, Shun - Complete Characterization of Broadcast and Pseudo-signatures from Correlations. - 2023. -

Summary/Abstract

Unconditionally secure broadcast is feasible among parties connected by pairwise secure links only if there is a strict two-thirds majority of honest parties when no additional resources are available. This limitation may be circumvented when the parties have recourse to additional resources such as correlated randomness. Fitzi, Wolf, and Wullschleger (CRYPTO 2004) attempted to characterize the conditions on correlated randomness shared among three parties which would enable them to realize broadcast. Due to a gap in their impossibility argument, it turns out that their characterization is incorrect. Using a novel construction we show that broadcast is feasible under a considerably larger class of correlations. In fact, we realize pseudo-signatures, which are information theoretic counterparts of digital signatures using which unconditionally secure broadcast may be obtained. We also obtain a matching impossibility result thereby characterizing the class of correlations on which three-party broadcast (and pseudo-signatures) can be based. Our impossibility proof, which extends the well-know argument of Fischer, Lynch and Merritt (Distr. Comp., 1986) to the case where parties observe correlated randomness, maybe of independent interest.

[QDC] - Helm, Louis K. - Quantum distributed consensus. - 2008. -

Summary/Abstract

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.

[FastBFT] - Ben-Or, Michael and Hassidim, Avinatan - Fast quantum byzantine agreement. - 2005. -

Summary/Abstract

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).

[ExperimentalBA] - Gaertner, Sascha and Bourennane, Mohamed and Kurtsiefer, Christian and Cabello, Ad\'an and Weinfurter, Harald - Experimental Demonstration of a Quantum Protocol for Byzantine Agreement and Liar Detection. - 2008. -

Summary/Abstract

N/A

[QDBAEPR] - Andronikos, Theodore and Sirokofskich, Alla - A Quantum Detectable Byzantine Agreement Protocol Using Only EPR Pairs. - 2023. -

Summary/Abstract

In this paper, we introduce a new quantum protocol for Detectable Byzantine Agreement. What distinguishes the proposed protocol among similar quantum protocols, is the fact that it uses only EPR pairs, and, in particular, |Ψ+⟩ pairs. There are many sophisticated quantum protocols that guarantee Detectable Byzantine Agreement, but they do not easily lend themselves to practical implementations, due to present-day technological limitations. For a large number n of players, |GHZ⟩n-tuples, or other more exotic entangled states, are not easy to produce, a fact which might complicate the scalability of such protocols. In contrast, Bell states are, undoubtedly, the easiest to generate among maximally entangled states. This will, hopefully, facilitate the scalability of the proposed protocol, as only EPR pairs are required, irrespective of the number n of players. Finally, we mention that, even for arbitrary many players n, our protocol always completes in a constant number of rounds, namely 4.

[QBADishonest] - Cholvi, Vicent - Quantum Byzantine Agreement for Any Number of Dishonest Parties. - 2022. -

Summary/Abstract

Reaching agreement in the presence of arbitrary faults is a fundamental problem in distributed computation, which has been shown to be unsolvable if one-third of the processes can fail, unless signed messages are used. In this paper, we propose a solution to a variation of the original BA problem, called Detectable Byzantine Agreement (DBA), that does not need to use signed messages. The proposed algorithm uses what we call Q-correlated lists, which are generated by a quantum source device. Once each process has one of these lists, they use them to reach the agreement in a classical manner. Although, in general, the agreement is reached by using {\$}{\$}m+1{\$}{\$}rounds (where m is the number of processes that can fail), if less than one-third of the processes fail it only needs one round to reach the agreement.

[ImprovedConsensusFull] - MohammadTaghi Hajiaghayi and Dariusz R. Kowalski and Jan Olkowski - Fault-Tolerant Consensus in Quantum Networks. - 2023. -

Summary/Abstract

N/A

[BenchmarkingProtocols] - Liao, Chin-Teand Bahrani, Simaand da Silva, Francisco Ferreiraand Kashefi, Elham - Benchmarking of quantum protocols. - 2022. -

Summary/Abstract

Quantum network protocols offer new functionalities such as enhanced security to communication and computational systems. Despite the rapid progress in quantum hardware, it has not yet reached a level of maturity that enables execution of many quantum protocols in practical settings. To develop quantum protocols in real world, it is necessary to examine their performance considering the imperfections in their practical implementation using simulation platforms. In this paper, we consider several quantum protocols that enable promising functionalities and services in near-future quantum networks. The protocols are chosen from both areas of quantum communication and quantum computation as follows: quantum money, W-state based anonymous transmission, verifiable blind quantum computation, and quantum digital signature. We use NetSquid simulation platform to evaluate the effect of various sources of noise on the performance of these protocols, considering different figures of merit. We find that to enable quantum money protocol, the decoherence time constant of the quantum memory must be at least three times the storage time of qubits. Furthermore, our simulation results for the w-state based anonymous transmission protocol show that to achieve an average fidelity above 0.8 in this protocol, the storage time of sender's and receiver's particles in the quantum memory must be less than half of the decoherence time constant of the quantum memory. We have also investigated the effect of gate imperfections on the performance of verifiable blind quantum computation. We find that with our chosen parameters, if the depolarizing probability of quantum gates is equal to or greater than 0.05, the security of the protocol cannot be guaranteed. Lastly, our simulation results for quantum digital signature protocol show that channel loss has a significant effect on the probability of repudiation.

[ResourceQBA] - Taherkhani, Mohammand Amin and Navi, Keivan and Meter, Rodney Van - Resource-aware system architecture model for implementation of quantum aided Byzantine agreement on quantum repeater networks. - 2017. -

Summary/Abstract

Quantum aided Byzantine agreement is an important distributed quantum algorithm with unique features in comparison to classical deterministic and randomized algorithms, requiring only a constant expected number of rounds in addition to giving a higher level of security. In this paper, we analyze details of the high level multi-party algorithm, and propose elements of the design for the quantum architecture and circuits required at each node to run the algorithm on a quantum repeater network (QRN). Our optimization techniques have reduced the quantum circuit depth by 44% and the number of qubits in each node by 20% for a minimum five-node setup compared to the design based on the standard arithmetic circuits. These improvements lead to a quantum system architecture with 160 qubits per node, space-time product (an estimate of the required fidelity) per node and error threshold for the total nodes in the network. The evaluation of the designed architecture shows that to execute the algorithm once on the minimum setup, we need to successfully distribute a total of 648 Bell pairs across the network, spread evenly between all pairs of nodes. This framework can be considered a starting point for establishing a road-map for light-weight demonstration of a distributed quantum application on QRNs.

[bit_escrow] - Aharonov, Dorit and Ta-Shma, Amnon and Vazirani, Umesh V. and Yao, Andrew C. - Quantum bit escrow. - 2000. -

Summary/Abstract

N/A

[leader_election] - Ganz, Maor - Quantum leader election. - 2017. -

Summary/Abstract

A group of n individuals {\$}{\$}A{\_}{\{}1{\}},{\backslash}ldots A{\_}{\{}n{\}}{\$}{\$}who do not trust each other and are located far away from each other, want to select a leader. This is the leader election problem, a natural extension of the coin flipping problem to n players. We want a protocol which will guarantee that an honest player will have at least {\$}{\$}{\backslash}frac{\{}1{\}}{\{}n{\}}-{\backslash}epsilon {\$}{\$}chance of winning ({\$}{\$}{\backslash}forall {\backslash}epsilon >0{\$}{\$}), regardless of what the other players do (whether they are honest, cheating alone or in groups). It is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon (Quantum weak coin flipping with arbitrarily small bias, arXiv:0711.4114, 2000) in 2007, and recently published and simplified in Aharonov et al. (SIAM J Comput, 2016). A protocol with linear number of coin flipping rounds is quite simple to achieve; we further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009; the first protocol with linear number of rounds was achieved independently also by Aharon and Silman (New J Phys 12:033027, 2010) around the same time.

[exact_leader_election] - Tani, Seiichiro and Kobayashi, Hirotada and Matsumoto, Keiji - Exact Quantum Algorithms for the Leader Election Problem. - 2012. -

Summary/Abstract

This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded.

[GHZ] - de Bone, Sebastian and Ouyang, Runsheng and Goodenough, Kenneth and Elkouss, David - Protocols for Creating and Distilling Multipartite GHZ States With Bell Pairs. - 2020. -

Summary/Abstract

The distribution of high-quality Greenberger-Horne-Zeilinger (GHZ) states is at the heart of many quantum communication tasks, ranging from extending the baseline of telescopes to secret sharing. They also play an important role in error-correction architectures for distributed quantum computation, where Bell pairs can be leveraged to create an entangled network of quantum computers. We investigate the creation and distillation of GHZ states out of nonperfect Bell pairs over quantum networks. In particular, we introduce a heuristic dynamic programming algorithm to optimize over a large class of protocols that create and purify GHZ states. All protocols considered use a common framework based on measurements of nonlocal stabilizer operators of the target state (i.e., the GHZ state), where each nonlocal measurement consumes another (nonperfect) entangled state as a resource. The new protocols outperform previous proposals for scenarios without decoherence and local gate noise. Furthermore, the algorithms can be applied for finding protocols for any number of parties and any number of entangled pairs involved.

[GraphStates] - Fischer, Alex and Towsley, Don - Distributing Graph States Across Quantum Networks. - 2021. -

Summary/Abstract

Graph states form an important class of multipartite entangled quantum states. We propose a new approach for distributing graph states across a quantum network. We consider a quantum network consisting of nodes—quantum computers within which local operations are free—and EPR pairs shared between nodes that can continually be generated. We prove upper bounds for our approach on the number of EPR pairs consumed, completion time, and amount of classical communication required, all of which are equal to or better than that of prior work [10]. We also reduce the problem of minimizing the completion time to distribute a graph state using our approach to a network flow problem having polynomial time complexity.

[DBAMajorities] - Fitzi, Matthias and Gottesman, Daniel and Hirt, Martin and Holenstein, Thomas and Smith, Adam - Detectable byzantine agreement secure against faulty majorities. - 2002. -

Summary/Abstract

It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty (honest), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a detectable Firing Squad protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.

[InSilicoDBA] - Mayank Bhatia and Shaan Doshi and Daniel Winton and Brian Doolittle and Bruno Abreu and Santiago Núñez-Corrales - \textit{In Silico} Benchmarking of Detectable Byzantine Agreement in Noisy Quantum Networks. - 2025. -

Summary/Abstract

N/A

[NoiseAwareDBA] - Chen, Kuan-Cheng and Prest, Matthew and Burt, Felix and Yu, Shang and Leung, Kin K. - Noise-Aware Detectable Byzantine Agreement for Consensus-based Distributed Quantum Computing. - 2025. -

Summary/Abstract

N/A

[QuantumSolution] - Fitzi, Matthias and Gisin, Nicolas and Maurer, Ueli - Quantum Solution to the Byzantine Agreement Problem. - 2001. -

Summary/Abstract

N/A

[Beating] - Chen-Xun Weng and Rui-Qi Gao and Yu Bao and Bing-Hong Li and Wen-Bo Liu and Yuan-Mei Xie and Yu-Shuo Lu and Hua-Lei Yin and Zeng-Bing Chen - Beating the Fault-Tolerance Bound and Security Loopholes for Byzantine Agreement with a Quantum Solution. - 2023. -

Summary/Abstract

Byzantine agreement, the underlying core of blockchain, aims to make every node in a decentralized network reach consensus. Classical Byzantine agreements unavoidably face two major problems. One is 1/3 fault-tolerance bound, which means that the system to tolerate f malicious players requires at least 3f\ +\ 1 players. The other is the security loopholes from its classical cryptography methods. Here, we propose a Byzantine agreement framework with unconditional security to break this bound with nearly 1/2 fault tolerance due to multiparty correlation provided by quantum digital signatures. It is intriguing that quantum entanglement is not necessary to break the 1/3 fault-tolerance bound, and we show that weaker correlation, such as asymmetric relationship of quantum digital signature, can also work. Our work strictly obeys two Byzantine conditions and can be extended to any number of players without requirements for multiparticle entanglement. We experimentally demonstrate three-party and five-party consensus for a digital ledger. Our work indicates the quantum advantage in terms of consensus problems and suggests an important avenue for quantum blockchain and quantum consensus networks.

[QMPC] - Cr\'{e}peau, Claude and Gottesman, Daniel and Smith, Adam - Secure multi-party quantum computation. - 2002. -

Summary/Abstract

Secure multi-party computing, also called secure function evaluation, has been extensively studied in classical cryptography. We consider the extension of this task to computation with quantum inputs and circuits. Our protocols are information-theoretically secure, i.e. no assumptions are made on the computational power of the adversary. For the weaker task of verifiable quantum secret sharing, we give a protocol which tolerates any t ξ n/4 cheating parties (out of n). This is shown to be optimal. We use this new tool to show how to perform any multi-party quantum computation as long as the number of dishonest players is less than n/6.

[QDS] - Daniel Gottesman and Isaac Chuang - Quantum Digital Signatures. - 2001. -

Summary/Abstract

N/A

[QDSNoMemory] - Dunjko, Vedran and Wallden, Petros and Andersson, Erika - Quantum Digital Signatures without Quantum Memory. - 2014. -

Summary/Abstract

N/A

[QDBABlockchain] - Zhiguo Qu and Zhexi Zhang and Bo Liu and Prayag Tiwari and Xin Ning and Khan Muhammad - Quantum detectable Byzantine agreement for distributed data trust management in blockchain. - 2023. -

Summary/Abstract

No system entity within a contemporary distributed cyber system can be entirely trusted. Hence, the classic centralized trust management method cannot be directly applied to it. Blockchain technology is essential to achieving decentralized trust management, its consensus mechanism is useful in addressing large-scale data sharing and data consensus challenges. Herein, an n-party quantum detectable Byzantine agreement (DBA) based on the GHZ state to realize the data consensus in a quantum blockchain is proposed, considering the threat posed by the growth of quantum information technology on the traditional blockchain. Relying on the nonlocality of the GHZ state, the proposed protocol detects the honesty of nodes by allocating the entanglement resources between different nodes. The GHZ state is notably simpler to prepare than other multi-particle entangled states, thus reducing preparation consumption and increasing practicality. When the number of network nodes increases, the proposed protocol provides better scalability and stronger practicability than the current quantum DBA. In addition, the proposed protocol has the optimal fault-tolerant found and does not rely on any other presumptions. A consensus can be reached even when there are n−2 traitors. The performance analysis confirms viability and effectiveness through exemplification. The security analysis also demonstrates that the quantum DBA protocol is unconditionally secure, effectively ensuring the security of data and realizing data consistency in the quantum blockchain.

[LowerBoundRandom] - Bar-Joseph, Ziv and Ben-Or, Michael - A tight lower bound for randomized synchronous consensus. - 1998. -

Summary/Abstract

N/A

[MinimalPrimitives] - Fitzi, Matthias and Garay, Juan A. and Maurer, Ueli and Ostrovsky, Rafail - Minimal Complete Primitives for Secure Multi-Party Computation. - 2005. -

Summary/Abstract

The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives for the case of two players has been thoroughly studied. However, in the multi-party setting, when there are n > 2 players and t of them are corrupted, the question of what are the simplest complete primitives remained open for t n/3. (A primitive is called complete if any computation can be carried out by the players having access only to the primitive and local computation.) In this paper we consider this question, and introduce complete primitives of minimal cardinality for secure multi-party computation. The cardinality issue (number of players accessing the primitive) is essential in settings where primitives are implemented by some other means, and the simpler the primitive the easier it is to realize. We show that our primitives are complete and of minimal cardinality possible for most cases.

[EasyImpossibility] - Fischer, Michael J. and Lynch, Nancy A. and Merritt, Michael - Easy impossibility proofs for distributed consensus problems. - 1985. -

Summary/Abstract

N/A

[EfficientQOT] - Sushmita Sarkar and Vikas Srivastava and Tapaswini Mohanty and Sumit Kumar Debnath and Sihem Mesnager - An Efficient Quantum Oblivious Transfer Protocol. - 2025. -

Summary/Abstract

N/A

[RabinOT] - Rabin, Michael - How To Exchange Secrets with Oblivious Transfer.. - 2005. -

Summary/Abstract

N/A

[QBCImpossibility] - Mayers, Dominic - Unconditionally Secure Quantum Bit Commitment is Impossible. - 1997. -

Summary/Abstract

N/A

[FlexibleQuantumQueries] - Gao, Fei and Liu, Bin and Wen, Qiao-Yan and Chen, Hui - Flexible quantum private queries based on quantum key distribution. - 2012. -

Summary/Abstract

N/A

[CompPowerWvsGHZ] - Ellie D'Hondt and Prakash Panangaden - The Computational Power of the W and GHZ states. - 2006. -

Summary/Abstract

N/A

[FairAndUnbiasedLE] - Sudebkumar Prasant Pal and Sudhir Kumar Singh and Somesh Kumar - Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks. - 2003. -

Summary/Abstract

N/A

[BcastAndPseudoSigs] - Narayanan, Varun and Prabhakaran, Vinod M. and Sangwan, Neha and Watanabe, Shun - Complete Characterization of Broadcast and Pseudo-signatures from Correlations. - 2023. -

Keyboard shortcuts

Coordination in Quantum Networks

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract

Summary/Abstract