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
Japan
hirotada AT nii DOT ac DOT jp
Keiji Matsumoto
Principles of Informatics Research Division
National Institute of Informatics
Japan
keiji AT nii DOT ac DOT jp
and
Seiichiro Tani
NTT Communication Science Laboratories
NTT Corporation
Japan
tani DOT seiichiro AT ntt DOT lab DOT co DOT jp
December 16, 2014
Abstract
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.
- The article: PDF (383 KB)
- Source material: ZIP (108 KB)
- BibTeX entry for this article (269 bytes)
Submitted February 2, 2014, revised September 26, 2014, and in final form December 9, 2014, published December 16, 2014.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 9
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Volume 2015, Article 1
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2014
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License