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.
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.
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 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.
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.
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.