文章基本信息

标题：Simpler Exact Leader Election via Quantum Reduction
本地全文：下载
作者：Hirotada Kobayashi ; Keiji Matsumoto ; Seiichiro Tani 等
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2014
卷号：2014
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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