Editing Fast Quantum Byzantine Agreement
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 62: | Line 62: | ||
====Fast Byzantine Agreement==== | ====Fast Byzantine Agreement==== | ||
'''Input:''' Each player starts with an input bit <math>b_i</math> and the number of players <math>n | '''Input:''' Each player starts with an input bit <math>b_i</math> and the number of players <math>n</math>. <br> | ||
'''Output:''' Each player outputs a bit <math>d_i</math>. With high probability, <math>d_i = d</math> for all players <math>i</math> (agreement) and some <math>d \in \{b_i\}_i</math> (validity). | '''Output:''' Each player outputs a bit <math>d_i</math>. With high probability, <math>d_i = d</math> for all players <math>i</math> (agreement) and some <math>d \in \{b_i\}_i</math> (validity). | ||
'''Repeat''' forever (until something is returned): | '''Repeat''' forever (until something is returned): | ||
# ''Subroutine <math>P_r(b_i)</math>:'' (this flips the oblivious common coin if no 2/3 majority is reached) | # ''Subroutine <math>P_r(b_i)</math>:'' (this flips the oblivious common coin if no 2/3 majority is reached) | ||
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players; | ## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players; | ||
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = QOCC(n | ## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = QOCC(n)</math> '''end'''; | ||
# ''Subroutine <math>P_0(b_i)</math>:'' (classical routine - biases towards 0 and finishes if 0 is the agreement value) | # ''Subroutine <math>P_0(b_i)</math>:'' (classical routine - biases towards 0 and finishes if 0 is the agreement value) | ||
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players; | ## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players; | ||
Line 80: | Line 78: | ||
====Quantum Oblivious Common Coin (QOCC)==== | ====Quantum Oblivious Common Coin (QOCC)==== | ||
'''Input:''' Each player starts with the number of players <math>n | '''Input:''' Each player starts with the number of players <math>n</math>. <br> | ||
'''Output:''' Each player outputs a random bit <math> | '''Output:''' Each player outputs a random bit <math>r_i</math>. With high probability, <math>d_i = d</math> for all players <math>i</math> (agreement) and some <math>d \in \{b_i\}_i</math> (validity). | ||
==Further Information== | ==Further Information== |