We provide the first quantum (exact) protocol for the Dining Philosophers problem (DP), a central problem in distributed algorithms. It is well known that the problem cannot be solved exactly in the classical setting. We then use our DP protocol to provide a new quantum protocol for the tightly related problem of exact leader election (LE) on a ring, improving significantly in both time and memory complexity over the known LE protocol by Tani et. al. To do this, we show that in some sense the exact DP and exact LE problems are equivalent; interestingly, in the classical non-exact setting they are not. Hopefully, the results will lead to exact quantum protocols for other important distributed algorithmic questions; in particular, we discuss interesting connections to the ring size problem, as well as to a physically motivated question of breaking symmetry in 1D translationally invariant systems.
We provide the first quantum (exact) protocol for the Dining Philosophers problem (DP), a central problem in distributed algorithms. It is well known that the problem cannot be solved exactly in the classical setting. We then use our DP protocol to provide a new quantum protocol for the tightly related problem of exact leader election (LE) on a ring, improving significantly in both time and memory complexity over the known LE protocol by Tani et. al. To do this, we show that in some sense the exact DP and exact LE problems are equivalent; interestingly, in the classical non-exact setting they are not. Hopefully, the results will lead to exact quantum protocols for other important distributed algorithmic questions; in particular, we discuss interesting connections to the ring size problem, as well as to a physically motivated question of breaking symmetry in 1D translationally invariant systems.
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.
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is O~(n) for leader election, broadcast, and MST, and O~(mn) for BFS (n and m are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds.
Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of O~(mn) for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since Ω(m) is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems.
A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.
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.
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 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.
In this paper we show that sufficient multi-partite quantum entanglement helps in fair and unbiased election of a leader in a distributed network of processors with only linear classical communication complexity. We show that a total of O(logn) distinct multi-partite maximally entanglement sets (ebits) are capable of supporting such a protocol in the presence of nodes that may lie and thus be biased. Here, n is the number of nodes in the network. We also demonstrate the difficulty of performing unbiased and fair election of a leader with linear classical communication complexity in the absence of quantum entanglement even if all nodes have perfect random bit generators. We show that the presence of a sufficient number O(n/logn) of biased agents leads to a non-zero limiting probability of biased election of the leader, whereas, the presence of a smaller number O(logn) of biased agents matters little. We define two new related complexity classes motivated by the our leader election problem and discuss a few open questions.