Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks

ABSTRACT

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.

REFERENCES

• 1: Yehuda Afek, Elections in anonymous networks, Information and Computation, v.113 n.2, p.312-330, Sept. 1994 [doi>10.1006/inco.1994.1075]
• 2: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 3: Hagit Attiya , Marc Snir , Manfred K. Warmuth, Computing on an anonymous ring, Journal of the ACM (JACM), v.35 n.4, p.845-875, Oct. 1988 [doi>10.1145/48014.48247]
• 4: G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series vol. 305, pages 53--74. 2002.
• 5: Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002 [doi>10.1016/S0304-3975(02)00377-8]
• 6: Vasil S. Denchev , Gopal Pandurangan, Distributed quantum computing: a new frontier in distributed systems or science fiction?, ACM SIGACT News, v.39 n.3, September 2008 [doi>10.1145/1412700.1412718]
• 7: E. D'Hondt and P. Panangaden. The computational power of the W and GHZ states. Quantum Inf. Comput., 6(2):173---183, 2006.
• 8: C. Gavoille, A. Kosowski, and M. Markiewicz. What can be observed locally? Round-based models for quantum distributed computing. arXiv:0903.1133, 2009.
• 9: Alon Itai , Michael Rodeh, Symmetry breaking in distributive networks, Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, p.150-158, October 28-30, 1981
• 10: Alon Itai , Michael Rodeh, Symmetry breaking in distributed networks, Information and Computation, v.88 n.1, p.60-87, July 1990 [doi>10.1016/0890-5401(90)90004-2]
• 11: E. Kranakis and D. Krizanc. Distributed computing on cayley networks (extended abstract). In Proc. 4th IEEE SPDP, pages 222--229, 1992.
• 12: Evangelos Kranakis , Danny Krizanc, Distributed computing on anonymous hypercube networks, Journal of Algorithms, v.23 n.1, p.32-50, April 1997 [doi>10.1006/jagm.1996.0817]
• 13: Evangelos Kranakis , Danny Krizanc , Jacob van den Berg, Computing Boolean functions on anonymous networks, Information and Computation, v.114 n.2, p.214-236, Nov. 1, 1994 [doi>10.1006/inco.1994.1086]
• 14: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 15: S. P. Pal, S. K. Singh, and S. Kumar. Multi-partite quantum entanglement versus randomization: Fair and unbiased leader election in networks. arXiv:quant-ph/0306195, 2003.
• 16: S. Tani, H. Kobayashi, and K. Matsumoto. Exact quantum algorithms for the leader election problem. In Proc. 22nd STACS, LNCS vol. 3404, pages 581--592,2005. (Full version in arXiv:0712.4213).
• 17: Masafumi Yamashita , Tsunehiko Kameda, Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.69-89, January 1996 [doi>10.1109/71.481599]
• 18: Masafumi Yamashita , Tsunehiko Kameda, Computing on Anonymous Networks: Part II-Decision and Membership Problems, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.90-96, January 1996 [doi>10.1109/71.481600]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

General Terms:
Algorithms, Theory

Keywords:
anonymous networks, leader election, quantum computing