Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Frontiers in Optics

Experimental demonstration of quantum leader election in linear optics

Yuta Okubo, Xiang‐Bin Wang, Akihisa Tomita

Published Jan 1, 2007• 1 citation
Publisher

Abstract

We propose and demonstrate a new implementation of a quantum protocol which can operate deterministically only with linear optics. This protocol, which is called quantum leader election, exhibits the quantum advantages over classical protocol.
DOI
10.1364/fio.2007.jtua2

Related papers

Experimental demonstration of quantum leader election in linear optics

Yuta Okubo, Xiang‐Bin Wang, Yun-Kun Jiang +2 more

Linear optics is a promising candidate to enable the construction of quantum computers. A number of quantum protocols gates based on linear optics have been demonstrated. However, it is well known that these gates are nondeterministic and that higher order nonlinearity is necessary for deterministic operations. We found the quantum leader election protocol can be operated deterministically only with linear optics, and we have demonstrated the nearly deterministic operation which overcomes classical limit.

arXiv:0709.4314•Physical Review A•Mar 27, 2008•5 citations

Experimental demonstration of quantum advantage for NP verification

Federico Centrone, Niraj Kumar, Eleni Diamanti +1 more

We showcase the power of linear optics through the implementation of a quantum protocol with coherent states. Our work provides evidence for a computational quantum advantage in the interactive setting, drawing near potentially useful applications.

Conference on Lasers and Electro-Optics•Jan 1, 2021•0 citations

Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks

Sudebkumar Prasant Pal, Sudhir Kumar Singh, Kumar, Somesh

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(\log n)$ 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/\log n)$ of biased agents leads to a non-zero limiting probability of biased election of the leader, whereas, the presence of a smaller number $O(\log n)$ 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.

arXiv:quant-ph/0306195•Jun 29, 2003•16 citations

Quantum computation with coherent states

Alexei Gilchrist, Timothy C. Ralph, William J. Munro +1 more

We extend a previous proposal for performing deterministic quantum computation using coherent states and linear optics by examining a new version of one of the gates which offers several advantages.

•Jan 1, 2003•7 citations

Simpler Exact Leader Election via Quantum Reduction

Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

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.

Chicago Journal of Theoretical Computer Science•Jan 1, 2014•3 citations

Quantum communication with coherent states and linear optics

Juan Miguel Arrazola, Norbert Lütkenhaus

A general mapping of qubit-based quantum communication protocols to coherent-states-based protocols is introduced, which provides a framework for transforming quantum communication protocols into a form that allows implementation with current technology.

arXiv:1406.7189•Physical Review A•Oct 29, 2014•50 citations
Linear optics is a promising candidate to enable the construction of quantum computers. A number of quantum protocols gates based on linear optics have been demonstrated. However, it is well known that these gates are nondeterministic and that higher order nonlinearity is necessary for deterministic operations. We found the quantum leader election protocol can be operated deterministically only with linear optics, and we have demonstrated the nearly deterministic operation which overcomes classical limit.
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(log⁡n)O(\log n)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, nnn 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/log⁡n)O(n/\log n)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(log⁡n)O(\log n)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.
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.