Coordination

Consensus

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

Algorithms

Algorithm for quantum byzantine agreement

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

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

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

Simulations / physical realization

Netsquid-based:

Resource-aware System Architectural Model for Implementation of QBA

Proposes specific circuit implementation for the Ben-Or's algorithm

Detectable Byzantine agreement (DBA)

NB Apparently, for DBA no one needs to maintain quantum state, hence the size and decoherence time of quantum memory are irrelevant.

Classical presentation is given in Detectable Byzantine Agreement Secure Against Faulty Majorities:

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

Further problem decomposition is presented in Detectable Byzantine Agreement Secure Against Faulty Majorities 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

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

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:

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

trusted quantum source
States: $\sum_{j} ∣ j ⟩ \otimes ∣ j + i_{1} mod d ⟩ \otimes ...∣ 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

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

Protocols based on quantum signatures

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

Beating the fault-tolerance bound for byzantine agreement

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

Simulations / physical realization

Beating the fault-tolerance bound for byzantine agreement
- 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"
Noise-Aware Detectable Byzantine Agreement for Consensus-based Distributed Quantum Computing
- focus is on the epr algorithm (TODO: double check)
- filter batches of EPR-pairs testing fidelity and dropping those with the fidelity below the threshold
- noise-mitigation techniques

Other works

Quantum Distributed Consensus: not quite a "consensus" as the outcome is _always random

Simulations / physical realization

Benchmarking of Quantum Protocols: 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 signatures

Quantum Digital Signatures

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}$
Quantum Digital Signatures without Quantum Memory

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 Secure Multi-party Quantum Computation.

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

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

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.

Coordination in Quantum Networks

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