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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{q,\epsilon}} : A weak unbalanced coin flipping protocol with an arbitrarily small bias of at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} and one of the players having the probability of winning equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.

Pseudo Code

When $n$ is an integral power of 2

For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^1_1, w^1_2, ..., w^1_{n/2}} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_\epsilon} (balanced coin flipping) to get the corresponding winners Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^2_1, w^2_2, ..., w^2_{n/4}} .
3. This goes on for a total of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} rounds and the winner of the $k^{th}$ round Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^k_1} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 $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