Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1001.5307 · Chicago Journal of Theoretical Computer Science

Computing on Anonymous Quantum Network

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

Published Jan 1, 2014• 8 citations
arXivHTMLPDF

Abstract

The anonymous network model was introduced by Angluin in [STOC '80, 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.

DOI
10.4086/cjtcs.2014.010

Related papers

Simpler Exact Leader Election via Quantum Reduction

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

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.

Chicago Journal of Theoretical Computer Science•Jan 1, 2014•3 citations

Exact Quantum Algorithms for the Leader Election Problem

Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto

This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded.

arXiv:0712.4213•ACM Transactions on Computation Theory•Mar 1, 2012•74 citations

Brief announcement

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

This paper proves that, if quantum communication and computation are available and the number of parties is given, the leader election problem can exactly (i.e., without error in bounded time) be solved with at most the same complexity up to a constant factor as that of computing certain symmetric functions on an anonymous network of any unknown topology. Together with a novel quantum algorithm that computes a certain symmetric function, this characterization yields a quantum leader election algorithm that is more efficient than existing algorithms.

ACM Symposium on Principles of Distributed Computing (PODC)•Aug 10, 2009•4 citations

A fast exact quantum algorithm for solitude verification

Seiichiro Tani

Solitude verification is arguably one of the simplest fundamental problems in distributed computing, where the goal is to verify that there is a unique contender in a network. This paper devises a quantum algorithm that exactly solves the problem on an anonymous network, which is known as a network model with minimal assumptions [Angluin, STOC’80]. The algorithm runs in O(N) rounds if every party initially has the common knowledge of an upper bound N on the number of parties. This implies that all solvable problems can be solved in O(N) rounds on average without error (i.e., with zero-sided error) on the network. As a generalization, a quantum algorithm that works in O(N log_2 (max{k, 2})) rounds is obtained for the problem of exactly computing any symmetric Boolean function, over n distributed input bits, which is constant over all the n bits whose sum is larger than k for k belongs to {0, 1, . . . , N −1}. All these algorithms work with the bit complexities bounded by a polynomial in N.

arXiv:1612.05317•Quantum Information and Computation•Jan 1, 2017•3 citations

Quantum Leader Election

Maor Ganz

Leader election between n parties is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon in 2007, and recently published and simplified in Aharonov et al in 2016. A protocol with linear number of coin flipping rounds is quite simple to achieve; We further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009: many typos are corrected, proofs are more rigorous and accurate, and the analysis of complexity is significantly tightened which gives a stronger result in terms of efficiency; The first protocol with linear number of rounds, was achieved independently also by Aharon and Silman in 2010.

arXiv:0910.4952•Oct 26, 2009•16 citations

Distributed quantum computing: a new frontier in distributed systems or science fiction?

Vasil S. Denchev, Gopal Pandurangan

Quantum computing and distributed systems may enter a mutually beneficial partnership in the future. On the one hand, it is much easier to build a number of small quantum computers rather than a single large one. On the other hand, the best results concerning some of the fundamental problems in distributed computing can potentially be dramatically improved upon by taking advantage of the superior resources and processing power that quantum mechanics offers. This survey has the purpose to highlight both of these benefits. We first review the current results regarding the implementation of arbitrary quantum algorithms on distributed hardware. We then discuss existing proposals for quantum solutions of leader election - a fundamental problem from distributed computing. Quantum mechanics allows leader election to be solved with no communication, provided that certain pre-shared entanglement is already in place. Further, an impossibility result from classical distributed computing is circumvented by the quantum solution of anonymous leader election - a unique leader is elected in finite time with certainty. Finally, we discuss the viability of these proposals from a practical perspective. Although, theoretically, distributed quantum computing looks promising, it is still unclear how to build quantum hardware and how to create and maintain robust large-scale entangled states. Moreover, it is not clear whether the costs of creating entangled states and working with them are smaller than the costs of existing classical solutions.

ACM SIGACT News•Sep 1, 2008•80 citations
The anonymous network model was introduced by Angluin in [STOC '80, 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 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.
This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded.
This paper proves that, if quantum communication and computation are available and the number of parties is given, the leader election problem can exactly (i.e., without error in bounded time) be solved with at most the same complexity up to a constant factor as that of computing certain symmetric functions on an anonymous network of any unknown topology. Together with a novel quantum algorithm that computes a certain symmetric function, this characterization yields a quantum leader election algorithm that is more efficient than existing algorithms.
Solitude verification is arguably one of the simplest fundamental problems in distributed computing, where the goal is to verify that there is a unique contender in a network. This paper devises a quantum algorithm that exactly solves the problem on an anonymous network, which is known as a network model with minimal assumptions [Angluin, STOC’80]. The algorithm runs in O(N) rounds if every party initially has the common knowledge of an upper bound N on the number of parties. This implies that all solvable problems can be solved in O(N) rounds on average without error (i.e., with zero-sided error) on the network. As a generalization, a quantum algorithm that works in O(N log_2 (max{k, 2})) rounds is obtained for the problem of exactly computing any symmetric Boolean function, over n distributed input bits, which is constant over all the n bits whose sum is larger than k for k belongs to {0, 1, . . . , N −1}. All these algorithms work with the bit complexities bounded by a polynomial in N.
Leader election between n parties is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon in 2007, and recently published and simplified in Aharonov et al in 2016. A protocol with linear number of coin flipping rounds is quite simple to achieve; We further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009: many typos are corrected, proofs are more rigorous and accurate, and the analysis of complexity is significantly tightened which gives a stronger result in terms of efficiency; The first protocol with linear number of rounds, was achieved independently also by Aharon and Silman in 2010.
Quantum computing and distributed systems may enter a mutually beneficial partnership in the future. On the one hand, it is much easier to build a number of small quantum computers rather than a single large one. On the other hand, the best results concerning some of the fundamental problems in distributed computing can potentially be dramatically improved upon by taking advantage of the superior resources and processing power that quantum mechanics offers. This survey has the purpose to highlight both of these benefits. We first review the current results regarding the implementation of arbitrary quantum algorithms on distributed hardware. We then discuss existing proposals for quantum solutions of leader election - a fundamental problem from distributed computing. Quantum mechanics allows leader election to be solved with no communication, provided that certain pre-shared entanglement is already in place. Further, an impossibility result from classical distributed computing is circumvented by the quantum solution of anonymous leader election - a unique leader is elected in finite time with certainty. Finally, we discuss the viability of these proposals from a practical perspective. Although, theoretically, distributed quantum computing looks promising, it is still unclear how to build quantum hardware and how to create and maintain robust large-scale entangled states. Moreover, it is not clear whether the costs of creating entangled states and working with them are smaller than the costs of existing classical solutions.