text: 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 @math rounds if every party initially has the common knowledge of an upper bound @math on the number of parties. This implies that all solvable problems can be solved in @math rounds on average without error (i.e., with zero-sided error) on the network. As a generalization, a quantum algorithm that works in @math rounds is obtained for the problem of exactly computing any symmetric Boolean function, over @math distributed input bits, which is constant over all the @math bits whose sum is larger than @math for @math . All these algorithms work with the bit complexities bounded by a polynomial in @math .
  @cite_30: We introduce a new quantum protocol for solving detectable Byzantine agreement (also called detectable broadcast) between three parties, and also for solving the detectable liar detection problem. The protocol is suggested by the properties of a four-qubit entangled state, and the classical part of the protocol is simpler than that of previous proposals. In addition, we present an experimental implementation of the protocol using four-photon entanglement.
  @cite_8: We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures.
  @cite_28: 
  @cite_21: The problem of quantum dice rolling (DR)—a generalization of the problem of quantum coin flipping (CF) to more than two outcomes and parties—is studied in both its weak and strong variants. We prove by construction that quantum mechanics allows for (i) weak N-sided DR admitting arbitrarily small bias for any N and (ii) two-party strong N-sided DR saturating Kitaev's bound for any N. To derive (ii) we also prove by construction that quantum mechanics allows for (iii) strong imbalanced CF saturating Kitaev's bound for any degree of imbalance. Furthermore, as a corollary of (ii) we introduce a family of optimal 2m-party strong nm-sided DR protocols for any pair m and n.
  @cite_6: It is well understood that the use of quantum entanglement significantly enhances the computational power of systems. Much of the attention has focused on Bell states and their multipartite generalizations. However, in the multipartite case it is known that there are several inequivalent classes of states, such as those represented by the W-state and the GHZ-state. Our main contribution is a demonstration of the special computational power of these states in the context of paradigmatic problems from classical distributed computing. Concretely, we show that the W-state is the only pure state that can be used to exactly solve the problem of leader election in anonymous quantum networks. Similarly we show that the GHZ-state is the only one that can be used to solve the problem of distributed consensus when no classical post-processing is considered. These results generalize to a family of W- and GHZ-like states. At the heart of the proofs of these impossibility results lie symmetry arguments.
  @cite_3: 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 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.
  @cite_19: 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 @math 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, @math 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 @math of biased agents leads to a non-zero limiting probability of biased election of the leader, whereas, the presence of a smaller number @math 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.
  @cite_15: 
  @cite_13: 
  @cite_17: We consider the question of locality in distributed computing in the context of quantum information. Specifically, we focus on the round complexity of quantum distributed algorithms, with no bounds imposed on local computational power or on the bit size of messages. Linial's LOCAL model of a distributed system is augmented through two types of quantum extensions: (1) initialization of the system in a quantum entangled state, and or (2) application of quantum communication channels. For both types of extensions, we discuss proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects. Nevertheless, we show that even such quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call "physical locality" (φ-LOCAL). While this is strictly weaker than the "computational locality" of the classical LOCAL model, it nevertheless leads to a generic view-based analysis technique for constructing lower bounds on round complexity. It turns out that the best currently known lower time bounds for many distributed combinatorial optimization problems, such as Maximal Independent Set, bounds cannot be broken by applying quantum processing, in any conceivable way.
summary: Pal, Singh, and Kumar @cite_19 and D'Hondt and Panangaden @cite_6 dealt with @math and the GHZ-state sharing problem in a different setting, where pre-shared entanglement is assumed but only classical communication is allowed. The relation between several network models that differ in available quantum resources has been discussed by Gavoille, Kosowski, and Markiewicz @cite_17 . Recently, @cite_13 proved that quantum communication cannot substantially speed up algorithms for some fundamental problems, such as the minimum spanning tree, compared to the classical setting. For fault-tolerant distributed quantum computing, the Byzantine agreement problem and the consensus problem were studied by Ben-Or and Hassidim @cite_28 and Chlebus, Kowalski, and Strojnowski @cite_8 , respectively. In the cryptographic context where there are cheating parties, Refs. @cite_21 @cite_15 devises quantum algorithms that elect a unique leader with a small bias. Some quantum distributed protocols were experimentally demonstrated by @cite_30 and @cite_3 .