Chicago Journal of Theoretical Computer Science

Volume 2014

Article 10

Published by the Department of Computer Science, The University of Chicago.

Simpler Exact Leader Election via Quantum Reduction

Hirotada Kobayashi
Principles of Informatics Research Division
National Institute of Informatics
hirotada AT nii DOT ac DOT jp

Keiji Matsumoto
Principles of Informatics Research Division
National Institute of Informatics
keiji AT nii DOT ac DOT jp


Seiichiro Tani
NTT Communication Science Laboratories
NTT Corporation
tani DOT seiichiro AT ntt DOT lab DOT co DOT jp

December 16, 2014


The anonymous network model was introduced by Angluin in [STOC '80, pages 82-93] to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties. In this model, all parties with the same number of communication links are identical. When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party. It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication. This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed [TOCT, vol.4, no.1, article 1]. The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty. This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election. The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.

Submitted February 2, 2014, revised September 26, 2014, and in final form December 9, 2014, published December 16, 2014.

DOI: 10.4086/cjtcs.2014.010

[] Article 9 [] Volume 2015, Article 1
[back] Volume 2014 [back] Published articles
[CJCTS home]