Quantum Leader Election

Quantum Leader Election allows multiple remote participants to select a leader among them randomly. The parties do not trust each other and can only use 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 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.

Notations

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

Requirements

• 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 $O(N_{\epsilon /4}\log {n}\log {1/\epsilon })$, and $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.

Pseudo Code

When $n$ is an integral power of 2

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

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

When $n$ is not an integral power of 2

For $2^{k}<n<2^{k+1}$,

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

The winner of this is the leader.

Further Information

*contributed by Natansh Mathur