Fast Quantum Byzantine Agreement: Difference between revisions

Fast Quantum Byzantine Agreement (edit)

Revision as of 05:09, 18 April 2019

994 bytes added , 18 April 2019

→‎Outline

Shraddha

Write, autoreview, editor, reviewer

3,129

edits

@@ Line 11: / Line 11: @@
 ==Outline==
-In this protocol, there are three main stages. The first stage is a preparation stage. we prepare two ancillary states with special coefficients which will lead to the desired flow of the information between copied states. The original state will not be engaged at this stage. At the second stage the cloner circuit will act on all the three states (the original and two other states) and at the second stage the two copied state will appear at two of the outputs and one of the outputs should be discarded. The Procedure will be as following:
+Here we will sketch the outline of the protocol by Ben-Or [Quantum Byzantine Agreement#References|(3)] that solve Byzantine Agreement using quantum resources. A very nice summary of this protocol is also presented in [Quantum Byzantine Agreement#References|(1)]. The main idea of this protocol is for each player to classically send its proposed value/decision (a valid message) to every other player and then collaborate to determine what a majority of honest players proposed. In the case where adversaries make this difficult, a `good-enough' random coin is globally flipped (protocol for random coin flip using quantum resources explained below), which is then classically post-processed to reach agreement among the honest parties. More precisely, the protocol is outlined as follows. Each round consists of the following steps:
-* Prepare two blank states and then perform a transformation taking these two states to a new state with pre-selected coefficients in such a way that the information distribution between two final states will be the desired.[[File:Asymmetriccloner.jpg|right|thumb|1000px| Graphical representation of the network for the asymmetric cloner. The CNOT gates are shown in the cloner section with control qubit (denoted as <math>\bullet</math> ) and a target qubit (denoted as <math>\circ</math> ). We separate the preparation of the quantum copier from the cloning process itself.]]
-*Perform the cloner circuit. the cloner circuit consists of four CNOT gate acting in all the three input qubits.  For every CNOT gate, we have a control qubit (which indicates whether or not the CNOT should act) and a target qubit (which is the qubit that CNOT gate acts on it and flips it).
+* Each player transmits its input to every other player. If one player receives more than 2/3 of the same values from the other players (including his own), then he changes his input also to this value (if that player already did not have the same choice). Otherwise, the same player executes a Quantum Oblivious Common Coin subroutine and sets his input to the outcome of this routine.
-* The two asymmetric clones will appear at two of the outputs (depending on the preparation stage) and the other output should be discarded.
+* Then each player sequentially executes two classical subroutines to bias the agreement value towards <math>0</math> or <math>1</math> (outcomes of a coin flip). This guarantees that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value <math>d</math> (not an outcome of coin flip).
+</br>
+'''Quantum Oblivious Common Coin subroutine:''' The heart of this protocol comes from the quantum enhanced [[Oblivious Common Coin]]. At the end of this subroutine, each player outputs a random bit, such that with at least probability $p$  (called the fairness) $v_i = x$ for all players $i$ and all $x \in \{0,1\}$. Intuitively, this subroutines tosses a common coin, where all players get either heads or tails with probability at least $p$ each, but there may be executions (which occur with at most probability $1-2p$) where all players do not get the same output and no common coin is actually tossed. Since the players do not know whether the outcomes are all equal or not, this type of coin tossing is referred to as oblivious common coin tossing. In particular, using quantum resources, this task can be achieved in constant rounds (in the defined model). The implementation of this subroutine makes use of a weakened version of Verifiable Quantum Secret Sharing.
 ==Notations Used==
 **<math>|\psi\rangle_{in}:</math>The original input state