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

arXiv:1408.1540 · Physical Review A

Quantum Byzantine agreement via Hardy correlations and entanglement swapping

Ramij Rahaman, Marcin Wieśniak, Marek Żukowski

Published Oct 1, 2015• 23 citations
arXivHTMLPDF

Abstract

We present a device-independent quantum scheme for the Byzantine generals problem. The protocol is for three parties. Party $C$ is to send two identical one-bit messages to parties $A$ and $B$. The receivers $A$ and $B$ may exchange two one-bit messages informing the other party on the message received from $C$. A bit-flipping error in one of the transmissions does not allow the receiving parties to establish what was the message of $C$. Our quantum protocol is based on Hardy's argument, which uses a set of conditions impossible for classical systems, but satisfied by predictions for a unique two-qubit state. The scheme has the feature that if the messages of the Byzantine protocol are readable (that is give an unambiguous bit value for any of the receivers), then any error by $C$ (cheating by one of the commanding generals) is impossible. $A$ and $B$ do not have to exchange protocol messages to be sure of this.

DOI
10.1103/physreva.92.042302

Related papers

Multi-Party Quantum Byzantine Agreement without Entanglement

Xin Sun, Piotr Kulicki, Mirek Sopek

In this paper, we propose a protocol of quantum communication to achieve Byzantine agreement among multiple parties. Our protocol's striking feature compared to the existing protocols is that we do not use entanglement to achieve the agreement. The role played by entangled states in other protocols is replaced in our protocol by a group of semi-honest list distributors. Such a replacement makes the implementation of our protocol more feasible. Moreover, our protocol is efficient in the sense that it achieves agreement in only three rounds which is a significant improvement with respect to the alternative agreement protocol not using entanglement. In the first round, a list of numbers that satisfies some special properties is distributed to every participant by list distributors via quantum secure communication. Then, in the second and third rounds, those participants exchange some information to reach an agreement.

arXiv:2003.09120•Entropy•Oct 14, 2020•23 citations

Quantum Byzantine Agreement for Any Number of Dishonest Parties

Vicent Cholvi

Abstract Reaching agreement in the presence of arbitrary faults is a fundamental problem in distributed computation, which has been shown to be unsolvable if one-third of the processes can fail, unless signed messages are used. In this paper, we propose a solution to a variation of the original BA problem, called Detectable Byzantine Agreement (DBA), that does not need to use signed messages. The proposed algorithm uses what we call Q-correlated lists, which are generated by a quantum source device. Once each process has one of these lists, they use them to reach the agreement in a classical manner. Although, in general, the agreement is reached by using $$m+1$$ m + 1 rounds (where m is the number of processes that can fail), if less than one-third of the processes fail it only needs one round to reach the agreement.

arXiv:2112.09437•Quantum Information Processing•Apr 1, 2022•11 citations

A New Solution to Detectable Byzantine Agreement Problem

Qin Su-Juan, Wen Qiao-yan, Luoming Meng +1 more

We present a new quantum protocol for solving detectable Byzantine agreement problem between three parties by employing one quantum key distribution protocol. The protocol is suggested by a special four-qubit entangled state instead of singlet states, which shows that singlet states are not necessary to achieve detectable Byzantine agreement.

Communications in Theoretical Physics•Dec 1, 2009•0 citations

Quantum Byzantine Agreement Against Full-Information Adversary

Longcheng Li, Xiaoming Sun, Jiadong Zhu

We exhibit that, when given a classical Byzantine agreement protocol designed in the private-channel model, it is feasible to construct a quantum agreement protocol that can effectively handle a full-information adversary. Notably, both protocols have equivalent levels of resilience, round complexity, and communication complexity. In the classical private-channel scenario, participating players are limited to exchanging classical bits, with the adversary lacking knowledge of the exchanged messages. In contrast, in the quantum full-information setting, participating players can exchange qubits, while the adversary possesses comprehensive and accurate visibility into the system's state and messages. By showcasing the reduction from quantum to classical frameworks, this paper demonstrates the strength and flexibility of quantum protocols in addressing security challenges posed by adversaries with increased visibility. It underscores the potential of leveraging quantum principles to improve security measures without compromising on efficiency or resilience. By applying our reduction, we demonstrate quantum advantages in the round complexity of asynchronous Byzantine agreement protocols in the full-information model. It is well known that in the full-information model, any classical protocol requires $Ω(n)$ rounds to solve Byzantine agreement with probability one even against Fail-stop adversary when resilience $t=Θ(n)$. We show that quantum protocols can achieve $O(1)$ rounds (i) with resilience $t0$, therefore surpassing the classical lower bound.

arXiv:2409.01707•Leibniz international proceedings in informatics•Jan 1, 2024•5 citations

Secure quantum dialogue using entanglement swapping

Mosayeb Naseri

In this study, a protocol for secure quantum dialogue using entanglement swapping was proposed. The protocol employs two independent communication channels, a classical channel and a quantum channel. In this scheme, the legitimate communicators Alice and Bob can pass the authentication by the classical trusted channel. Afterwards, a quantum channel sequence is provided for them, on which Alice and Bob can communicate with each other directly and privately by virtue of some encoding operations. The first advantage of our protocol is that different from the previews protocols, in the proposed protocol, the server of the quantum channel, Charlie, is not necessarily trusted. The other highlight of our protocol is that in the presented scheme, one party is able to first read the message received from the other party before sending another message back in reply.   Key words: Quantum secure direct communication, entanglement swapping, quantum dialogue.

International Journal of the Physical Sciences•Jul 12, 2012•0 citations

Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication

Jan Olkowski

We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to $t\le(1/3-\varepsilon)n$ processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability $1$. It uses $O(\log^4 n)$ rounds, $O(n\log^8 n)$ qubits, and $O(n^2\log^8 n)$ classical bits in expectation, with constants depending on $\varepsilon$. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves $O(1)$ expected rounds but whose Byzantine coin implementation requires $Ω(n^4\log n)$ qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an $Ω(t^2)$ lower bound on worst-case expected total communication. For $t=Θ(n)$, the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.

arXiv:2611.05598•Nov 3, 2026•0 citations
We present a device-independent quantum scheme for the Byzantine generals problem. The protocol is for three parties. Party CCC is to send two identical one-bit messages to parties AAA and BBB. The receivers AAA and BBB may exchange two one-bit messages informing the other party on the message received from CCC. A bit-flipping error in one of the transmissions does not allow the receiving parties to establish what was the message of CCC. Our quantum protocol is based on Hardy's argument, which uses a set of conditions impossible for classical systems, but satisfied by predictions for a unique two-qubit state. The scheme has the feature that if the messages of the Byzantine protocol are readable (that is give an unambiguous bit value for any of the receivers), then any error by CCC (cheating by one of the commanding generals) is impossible. AAA and BBB do not have to exchange protocol messages to be sure of this.
In this paper, we propose a protocol of quantum communication to achieve Byzantine agreement among multiple parties. Our protocol's striking feature compared to the existing protocols is that we do not use entanglement to achieve the agreement. The role played by entangled states in other protocols is replaced in our protocol by a group of semi-honest list distributors. Such a replacement makes the implementation of our protocol more feasible. Moreover, our protocol is efficient in the sense that it achieves agreement in only three rounds which is a significant improvement with respect to the alternative agreement protocol not using entanglement. In the first round, a list of numbers that satisfies some special properties is distributed to every participant by list distributors via quantum secure communication. Then, in the second and third rounds, those participants exchange some information to reach an agreement.
Abstract Reaching agreement in the presence of arbitrary faults is a fundamental problem in distributed computation, which has been shown to be unsolvable if one-third of the processes can fail, unless signed messages are used. In this paper, we propose a solution to a variation of the original BA problem, called Detectable Byzantine Agreement (DBA), that does not need to use signed messages. The proposed algorithm uses what we call Q-correlated lists, which are generated by a quantum source device. Once each process has one of these lists, they use them to reach the agreement in a classical manner. Although, in general, the agreement is reached by using m+1m+1m+1 m + 1 rounds (where m is the number of processes that can fail), if less than one-third of the processes fail it only needs one round to reach the agreement.
We exhibit that, when given a classical Byzantine agreement protocol designed in the private-channel model, it is feasible to construct a quantum agreement protocol that can effectively handle a full-information adversary. Notably, both protocols have equivalent levels of resilience, round complexity, and communication complexity. In the classical private-channel scenario, participating players are limited to exchanging classical bits, with the adversary lacking knowledge of the exchanged messages. In contrast, in the quantum full-information setting, participating players can exchange qubits, while the adversary possesses comprehensive and accurate visibility into the system's state and messages. By showcasing the reduction from quantum to classical frameworks, this paper demonstrates the strength and flexibility of quantum protocols in addressing security challenges posed by adversaries with increased visibility. It underscores the potential of leveraging quantum principles to improve security measures without compromising on efficiency or resilience. By applying our reduction, we demonstrate quantum advantages in the round complexity of asynchronous Byzantine agreement protocols in the full-information model. It is well known that in the full-information model, any classical protocol requires Ω(n)Ω(n)Ω(n) rounds to solve Byzantine agreement with probability one even against Fail-stop adversary when resilience t=Θ(n)t=Θ(n)t=Θ(n). We show that quantum protocols can achieve O(1)O(1)O(1) rounds (i) with resilience t0t0t0, therefore surpassing the classical lower bound.
In this study, a protocol for secure quantum dialogue using entanglement swapping was proposed. The protocol employs two independent communication channels, a classical channel and a quantum channel. In this scheme, the legitimate communicators Alice and Bob can pass the authentication by the classical trusted channel. Afterwards, a quantum channel sequence is provided for them, on which Alice and Bob can communicate with each other directly and privately by virtue of some encoding operations. The first advantage of our protocol is that different from the previews protocols, in the proposed protocol, the server of the quantum channel, Charlie, is not necessarily trusted. The other highlight of our protocol is that in the presented scheme, one party is able to first read the message received from the other party before sending another message back in reply.   Key words: Quantum secure direct communication, entanglement swapping, quantum dialogue.
We consider synchronous binary Byzantine agreement among nnn processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to t≤(1/3−ε)nt\le(1/3-\varepsilon)nt≤(1/3−ε)n processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability 111. It uses O(log⁡4n)O(\log^4 n)O(log4n) rounds, O(nlog⁡8n)O(n\log^8 n)O(nlog8n) qubits, and O(n2log⁡8n)O(n^2\log^8 n)O(n2log8n) classical bits in expectation, with constants depending on ε\varepsilonε. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves O(1)O(1)O(1) expected rounds but whose Byzantine coin implementation requires Ω(n4log⁡n)Ω(n^4\log n)Ω(n4logn) qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an Ω(t2)Ω(t^2)Ω(t2) lower bound on worst-case expected total communication. For t=Θ(n)t=Θ(n)t=Θ(n), the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.