Exact Quantum Algorithms for the Leader Election Problem

DOI10.1145/2141938.2141939MaRDI QIDQ2947561zbMATH OpenOpenAlexWikidataFDO

Authors Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.4213

zbMATH Keywords

distributed computingquantum algorithmsquantum communication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: This paper gives the first separation of quantum and classical pure (i.e., non-cryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of a celebrated unsolvable problem in classical distributed computing, the ``leader election problem on anonymous networks. The goal of the leader election problem is to elect a unique leader from among distributed parties. The paper considers this problem for anonymous networks, in which each party has the same identifier. It is well-known that no classical algorithm can solve exactly (i.e., in bounded time without error) the leader election problem in anonymous networks, even if it is given the number of parties. This paper gives two quantum algorithms that, given the number of parties, can exactly solve the problem for any network topology in polynomial rounds and polynomial communication/time complexity with respect to the number of parties, when the parties are connected by quantum communication links.

Recommendations

• STACS 2005
• Simpler exact leader election via quantum reduction
• Quantum leader election
• An exact quantum algorithm for the 2-junta problem
• An exact quantum algorithm for a restricted subtraction game
• Quantum algorithms for the subset-sum problem
• Superlinear advantage for exact quantum algorithms
• Superlinear advantage for exact quantum algorithms
• Quantum algorithms for fixed points and invariant subgroups

Cited in

(17)

• Model checking quantum Markov chains
• A proof system for disjoint parallel quantum programs
• On the power of quantum distributed proofs
• Simpler exact leader election via quantum reduction
• Distinguishing views in symmetric networks: a tight lower bound
• Deriving the correctness of quantum protocols in the probabilistic logic for quantum programs
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• Distributed quantum proofs for replicated data
• scientific article; zbMATH DE number 7559158 (Why is no real title available?)
• Quantum temporal logic and reachability problems of matrix semigroups
• STACS 2005
• Brief Announcement: Improved Consensus in Quantum Networks
• Distributed fast crash-tolerant consensus with nearly-linear quantum communication
• Reconciling quantum theory and process equivalence via physically admissible schedulers
• An exact quantum algorithm for a restricted subtraction game
• Quantum leader election
• Toward automatic verification of quantum programs

This page was built for publication: Exact Quantum Algorithms for the Leader Election Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947561)