Quantum Leader Election
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.
- 1 Outline
- 2 Notation
- 3 Requirements
- 4 Knowledge Graph
- 5 Properties
- 6 Protocol Description
- 7 Further Information
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.
- : A weak balanced coin flipping protocol with an arbitrarily small bias of at most .
- : A weak unbalanced coin flipping protocol with an arbitrarily small bias of at most and one of the players having the probability of winning equal to .
- : Set of players participating in Leader election
- : Winner of the pair in the round.
- : number of rounds in a weak balanced coin flipping protocol .
- 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
- 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 , and rounds of coin flipping.
- It assumes the setting is sequential so the next coin flipping protocol starts after the previous one ends.
When is an integral power of 2
For , rounds are performed.
- The following pairs perform (balanced coin flipping):
with as the corresponding winners.
- The pairs: again perform (balanced coin flipping) to get the corresponding winners .
- This goes on for a total of rounds and the winner of the round is declared the leader.
When is not an integral power of 2
- The following steps are performed simultaneously:
- Players perform leader election for integral power of 2 number of players among themselves with to get the winner .
- Players recursively perform leader election for not an integral power of 2 number of players to get the winner .
- and perform .
The winner of this is the leader.