---
author:
- |
    [ $\mbox{\bf Seiichiro Tani}^{\ast\dagger}$ ]{}\
    [tani@theory.brl.ntt.co.jp]{}
- |
    [ $\mbox{\bf Hirotada Kobayashi}^{\ddagger}$ ]{}\
    [hirotada@nii.ac.jp]{}
- |
    [ $\mbox{\bf Keiji Matsumoto}^{\ddagger \dagger}$ ]{}\
    [keiji@nii.ac.jp]{}
title: |
     Exact Quantum Algorithms\
    for the Leader Election Problem[^1] 
---

${}^{\ast}$NTT Communication Science Laboratories, NTT Corporation\
${}^{\dagger}$Quantum Computation and Information Project, ERATO-SORST, JST\
${}^{\ddagger}$Principles of Informatics Research Division, National Institute of Informatics

[10]{}

Yehuda Afek and Yossi Matias. Elections in anonymous networks. , 113(2):312–330, 1994.

Masami Amano and Kazuo Iwama. Undecidability on quantum finite automata. In [*Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing*]{}, pages 368–375, 1999.

Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. , 68(2):398–416, 2004.

Andris Ambainis. Quantum walk algorithm for element distinctness. In [*Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science*]{}, pages 22–31, 2004.

Andris Ambainis, Harry M. Buhrman, Yevgeniy Dodis, and Hein Röhrig. Multiparty quantum coin flipping. In [*Proceedings of the Nineteenth Annual [IEEE]{} Conference on Computational Complexity*]{}, pages 250–259, 2004.

Andris Ambainis and Rusins Freivalds. 1-way quantum finite automata: Strengths, weaknesses and generalizations. In [*Proceedings of the Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science*]{}, pages 332–341, 1998.

Andris Ambainis and John Watrous. Two-way finite automata with quantum and classical state. , 287(1):299–311, 2002.

Dana Angluin. Local and global properties in networks of processors (extended abstract). In [*Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing*]{}, pages 82–93, 1980.

Ziv Bar-Yossef, Thathachar S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In [*Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing*]{}, pages 128–137, 2004.

Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam D. Smith, and Alain Tapp. Authentication of quantum messages. In [*Proceedings of the Forty-Third Annual IEEE Symposium on Foundations of Computer Science*]{}, pages 449–458, 2002.

Michael Ben-[O]{}r and Avinatan Hassidim. Fast quantum [B]{}yzantine agreement. In [*Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing*]{}, pages 481–485, 2005.

Charles H. Bennett. Quantum cryptography using any two nonorthogonal states. , 68(21):3121–3124, 1992.

Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In [*Proceedings of IEEE International Conference on Computers, Systems and Signal Processing*]{}, pages 175–179, 1984.

Gilles Brassard, Peter H[ø]{}yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In [*Quantum Computation and Quantum Information: A Millennium Volume*]{}, volume 305 of [*AMS Contemporary Mathematics Series*]{}, pages 53–74. 2002.

Randal E. Bryant. Graph-based algorithms for [Boolean]{} function manipulation. , 35(8):677–691, 1986.

Harry M. Buhrman, Richard E. Cleve, John H. Watrous, and Ronald de Wolf. Quantum fingerprinting. , 87(16):167902, 2001.

Harry M. Buhrman, Richard E. Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In [*Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing*]{}, pages 63–68, 1998.

A. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman. Exponential algorithmic speedup by quantum walk. In [*Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing*]{}, pages 59–68, 2003. quant-ph/0209131.

Claude Crépeau, Daniel Gottesman, and Adam D. Smith. Secure multi-party quantum computation. In [*Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing*]{}, pages 643–652, 2002.

Claude Crépeau, Frédéric Légaré, and Louis Salvail. How to convert the flavor of a quantum bit commitment. In [*Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT 2001)*]{}, volume 2045 of [*Lecture Notes in Computer Science*]{}, pages 60–77, 2001.

Ellie D’Hondt and Prakash Panangaden. The computational power of the w and ghz states. , 6(2), 2006.

Danny Dolev, Maria M. Klawe, and Michael Rodeh. An [$O(n\log n)$]{} unidirectional distributed algorithm for extrema finding in a circle. , 3(3):245–260, 1982.

Paul Dumais, Dominic Mayers, and Louis Salvail. Perfectly concealing quantum bit commitment from any quantum one-way permutation. In [*Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT 2000)*]{}, volume 1807 of [*Lecture Notes in Computer Science*]{}, pages 300–315, 2000.

Greg N. Frederickson and Nancy A. Lynch. Electing a leader in a synchronous ring. , 34(1):98–115, 1987.

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. , 5(1):66–77, 1983.

Lov. K. Grover. A fast quantum mechanical algorithm for database search. In [*Proceedings of the Twenty-Eighth Annual [ACM]{} Symposium on Theory of Computing*]{}, pages 212–219, 1996.

Alon Itai and Michael Rodeh. Symmetry breaking in distributive networks. In [*Proceedings of the Twenty-Second Annual IEEE Symposium on Foundations of Computer Science*]{}, pages 150–158, 1981.

Alon Itai and Michael Rodeh. Symmetry breaking in distributed networks. , 88(1):60–87, 1990.

Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. , volume 47 of [*Graduate Studies in Mathematics*]{}. AMS, 2002.

Evangelos Kranakis, Danny Krizanc, and Jacob van den Berg. Computing [B]{}oolean functions on anonymous networks. , 114(2):214–236, 1994.

Nancy A. Lynch. . Morgan Kaufman Publishers, 1996.

Dominic Mayers. Unconditional security in quantum cryptography. , 48(3):351–406, 2001.

Michael A. Nielsen and Isaac L. Chuang. . Cambridge University Press, 2000.

Nancy Norris. Universal covers of graphs: Isomorphism to depth n-1 implies isomorphism to all depths. , 56(1):61–74, 1995.

M. Mosca P. H[ø]{}yer and R. de Wolf. Quantum search on bounded-error inputs. In [*Proceedings of the Thirtieth International Colloquium on Automata, Languages and Programming(ICALP’03)*]{}, volume 2719 of [*Lecture Notes in Computer Science*]{}, pages 291–299. Springer, 2003.

Gary L. Peterson. An [$O(n \log n)$]{} unidirectional algorithm for the circular extrema problem. , 4(4):758–762, 1982.

Ran Raz. Exponential separation of quantum and classical communication complexity. In [*Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing*]{}, pages 358–367, 1999.

Baruch Schieber and Marc Snir. Calling names on nameless networks. , 113(1):80–101, 1994.

Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. , 26(5):1484–1509, 1997.

Peter W. Shor and John Preskill. Simple proof of security of the [BB84]{} quantum key distribution protocol. , 85(2):441–444, 2000.

Kiyoshi Tamaki, Masato Koashi, and Nobuyuki Imoto. Security of the [Bennett]{} 1992 quantum-key distribution protocol against individual attack over a realistic channel. , 67(3):032310, 2003.

Kiyoshi Tamaki, Masato Koashi, and Nobuyuki Imoto. Unconditionally secure key distribution based on two nonorthogonal states. , 90(16):167904, 2003.

Kiyoshi Tamaki and Norbert Lütkenhaus. Unconditional security of the [Bennett]{} 1992 quantum key-distribution protocol over a lossy and noisy channel. , 69(3):032316, 2004.

Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact quantum algorithms for the leader election problem. In [*Proceedings of the Twenty-Second Symposium on Theoretical Aspects of Computer Science (STACS 2005)*]{}, volume 3404 of [*Lecture Notes in Computer Science*]{}, pages 581–592. Springer, 2005.

Jan van Leeuwen and Richard B. Tan. An improved upperbound for distributed election in bidirectional rings of processors. , 2(3):149–160, 1987.

Tomohiro Yamasaki, Hirotada Kobayashi, and Hiroshi Imai. Quantum versus deterministic counter automata. , 334(1-3):275–297, 2005.

Tomohiro Yamasaki, Hirotada Kobayashi, Yuuki Tokunaga, and Hiroshi Imai. One-way probabilistic reversible and quantum one-counter automata. , 289(2):963–976, 2002.

Masafumi Yamashita and Tsunehiko Kameda. Computing on anonymous networks: Part [I]{} – characterizing the solvable cases. , 7(1):69–89, 1996.

Masafumi Yamashita and Tsunehiko Kameda. Computing on anonymous networks: Part [II]{} – decision and membership problems. , 7(1):90–96, 1996.

Masafumi Yamashita and Tsunehiko Kameda. Leader election problem on networks in which processor identity numbers are not distinct. , 10(9):878–887, 1999.

[^1]: A preliminary version of this paper appeared in [@TanKobMatSTACS05].
