Editing Practical Quantum Electronic Voting (section)

==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''
 
''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform '''UniqueIndex''' until each agent has a secret unique random index  <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until '''Voting''' is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> <!--NEEDS FORMATTING CHANGES-->
**** The agents perform '''LogicalOR''', where output 1 indicates '''Verification''' and output 0 indicates '''Voting'''. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If '''Verification''' is chosen, the agents perform '''RandomAgent''' and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if '''Verification''' outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform '''Voting'''. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform '''LogicalOR''' with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If '''LogicalOR''' outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.


===Protocol 2 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in '''LogicalOR''',<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform '''LogicalOR''' with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# [notification]  Everybody performs a '''LogicalOR''' with input 0, unless they received the index in this round, in which case they input 1.
# If the output of '''LogicalOR''' is 0, no index was assigned and we repeat from step 2.
# If the output of '''LogicalOR''' is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 3 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for '''RandomAgent'''.

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes '''RandomAgent''' to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\rangle] = [\frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta_j}|1\rangle), \frac{1}{\sqrt{2}}(|0\rangle - e^{i\theta_j}|1\rangle)]</math> and publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math>Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i </math> (mod 2)

===Protocol 4 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>

===Protocol 5 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math> 
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>

===Protocol 6 : RandomBit===
''Input'': Security parameter S to be used in '''LogicalOR''', ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform '''LogicalOR''' with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 7 : RandomAgent===

''Input'': Security parameter S to be used in '''RandomBit''', voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat '''RandomBit''' log2 N times.