This example protocol allows multiple remote participants to select a leader among them randomly. The parties do not trust each other and can use both classical and quantum channels to communicate. It is an extension of the coin tossing problem to multiple players.

## Outline

### When the number of players is an integral power of 2:

The leader election protocol, in this case, is similar to a knockout tournament. In the first round, every team pairs up with the other team and they perform a balanced coin flip to determine the winner. In subsequent rounds, winners from the previous round team up with another winner and perform balanced coin flip to determine the winners of this round. The winner of the final round is declared the leader.

### When the number of players is not an integral power of 2:

In this case, the leader election protocol uses the 'power of 2' scenario and also recursively calls itself to select the leader. Players continue till the index of the power of 2 which is just less than the total number of players perform leader election in an aforementioned manner to decide a winner. Leader election protocol is then used recursively for the remaining participants to decide another winner. Both the winners now perform an unbalanced quantum coin flipping to decide the final winner which is the leader.

## Notation

• ${\displaystyle P_{\epsilon }}$: A weak balanced coin flipping protocol with an arbitrarily small bias of at most ${\displaystyle \epsilon }$.
• ${\displaystyle P_{q,\epsilon }}$: A weak unbalanced coin flipping protocol with an arbitrarily small bias of at most ${\displaystyle \epsilon }$ and one of the players having the probability of winning equal to ${\displaystyle q}$.
• ${\displaystyle \{A_{1},...,A_{n}\}}$: Set of players participating in Leader election
• ${\displaystyle w_{j}^{i}}$: Winner of the ${\displaystyle j^{th}}$ pair in the ${\displaystyle i^{th}}$ round.
• ${\displaystyle N_{\epsilon }}$: number of rounds in a weak balanced coin flipping protocol ${\displaystyle P_{\epsilon }}$.

## Requirements

• Network Stage: Fully Quantum Computing Network Stage
• Resources to perform weak (balanced and unbalanced) quantum coin tossing.
• Authenticated Quantum channel capable of sending a pair of qubits
• Authenticated Classical channel to send multiple bits
• Quantum memory for both parties to store qubits
• Measurement Devices for each party
• Random bit generator for each party

## Properties

• The protocol uses as a black box the quantum solution to the coin tossing protocol (both balanced and unbalanced).
• The protocol has a running time of ${\displaystyle O(N_{\epsilon /4}\log {n}\log {1/\epsilon })}$, and ${\displaystyle O(\log {n})}$ rounds of coin flipping.
• It assumes the setting is sequential so the next coin flipping protocol starts after the previous one ends.

## Protocol Description

### When ${\displaystyle n}$ is an integral power of 2

For ${\displaystyle n=2^{k}}$, ${\displaystyle k}$ rounds are performed.

1. The following pairs perform ${\displaystyle P_{\epsilon }}$ (balanced coin flipping):
${\displaystyle (A_{1},A_{2}),(A_{3},A_{4}),...,(A_{n-1},A_{n})}$ with ${\displaystyle w_{1}^{1},w_{2}^{1},...,w_{n/2}^{1}}$ as the corresponding winners.
2. The pairs: ${\displaystyle (w_{1}^{1},w_{2}^{1}),(w_{3}^{1},w_{4}^{1}),...,(w_{n/2-1}^{1},w_{n/2}^{1})}$ again perform ${\displaystyle P_{\epsilon }}$ (balanced coin flipping) to get the corresponding winners ${\displaystyle w_{1}^{2},w_{2}^{2},...,w_{n/4}^{2}}$.
3. This goes on for a total of ${\displaystyle k}$ rounds and the winner of the ${\displaystyle k^{th}}$ round ${\displaystyle w_{1}^{k}}$ is declared the leader.

### When ${\displaystyle n}$ is not an integral power of 2

For ${\displaystyle 2^{k},

1. The following steps are performed simultaneously:
• Players ${\displaystyle A_{1},A_{2},...,A_{2^{k}}}$ perform leader election for integral power of 2 number of players among themselves with ${\displaystyle P_{\frac {\epsilon }{2}}}$ to get the winner ${\displaystyle w_{1}}$.
• Players ${\displaystyle A_{2^{k}+1},...,A_{n}}$ recursively perform leader election for not an integral power of 2 number of players to get the winner ${\displaystyle w_{2}}$.
2. ${\displaystyle w_{1}}$ and ${\displaystyle w_{2}}$ perform ${\displaystyle P_{{\frac {2^{k}}{n}},{\frac {\epsilon }{2}}}}$.

The winner of this is the leader.

## Further Information

*contributed by Natansh Mathur