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

Quantum Information Processing

Quantum Byzantine Agreement for Any Number of Dishonest Parties

Vicent Cholvi

Published Apr 1, 2022• 9 citations
Publisher

Abstract

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.

DOI
10.1007/s11128-022-03492-y

Related papers

Detectable Quantum Byzantine Agreement for Any Arbitrary Number of Dishonest Parties

Vicent Cholvi

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$ 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•Dec 17, 2021•0 citations

Quantum Clock Synchronization with a Single Qudit

Armin Tavakoli, Adán Cabello, Marek Żukowski +1 more

Clock synchronization for nonfaulty processes in multiprocess networks is indispensable for a variety of technologies. A reliable system must be able to resynchronize the nonfaulty processes upon some components failing causing the distribution of incorrect or conflicting information in the network. The task of synchronizing such networks is related to detectable Byzantine agreement (DBA), which can classically be solved using recursive algorithms if and only if less than one-third of the processes are faulty. Here we introduce a nonrecursive quantum algorithm that solves the DBA and achieves clock synchronization in the presence of arbitrary many faulty processes by using only a single quantum system.

arXiv:1501.05758•Jan 23, 2015•0 citations

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•19 citations

Beating the Fault-Tolerance Bound and Security Loopholes for Byzantine Agreement with a Quantum Solution

Chen-Xun Weng, Rui-Qi Gao, Yu Bao +6 more

Byzantine agreement, the underlying core of blockchain, aims to make every node in a decentralized network reach consensus. Classical Byzantine agreements unavoidably face two major problems. One is 1/3 fault-tolerance bound, which means that the system to tolerate f malicious players requires at least 3 f + 1 players. The other is the security loopholes from its classical cryptography methods. Here, we propose a Byzantine agreement framework with unconditional security to break this bound with nearly 1/2 fault tolerance due to multiparty correlation provided by quantum digital signatures. It is intriguing that quantum entanglement is not necessary to break the 1/3 fault-tolerance bound, and we show that weaker correlation, such as asymmetric relationship of quantum digital signature, can also work. Our work strictly obeys two Byzantine conditions and can be extended to any number of players without requirements for multiparticle entanglement. We experimentally demonstrate three-party and five-party consensus for a digital ledger. Our work indicates the quantum advantage in terms of consensus problems and suggests an important avenue for quantum blockchain and quantum consensus networks.

arXiv:2206.09159•Research•Jan 1, 2023•39 citations

Quantum Clock Synchronization with a Single Qudit

Armin Tavakoli, Adán Cabello, Marek Żukowski +1 more

Clock synchronization for nonfaulty processes in multiprocess networks is indispensable for a variety of technologies. A reliable system must be able to resynchronize the nonfaulty processes upon some components failing causing the distribution of incorrect or conflicting information in the network. The task of synchronizing such networks is related to Byzantine agreement (BA), which can classically be solved using recursive algorithms if and only if less than one-third of the processes are faulty. Here we introduce a nonrecursive quantum algorithm, based on a quantum solution of the detectable BA, which achieves clock synchronization in the presence of arbitrary many faulty processes by using only a single quantum system.

Scientific Reports•Jan 23, 2015•25 citations

Entangled state testing in the quantum Byzantine agreement

Heng-yue JIA Xia WU, Heng-yue JIA, Jian-ming ZHU

In distributed computing,Byzantine agreement is a practical method to solve its fault-tolerance problem.There is a variation of the Byzantine agreement which is called detectable Byzantine agreement.This kind of protocol is unsolvable by classical means,but can be solved using quantum resources——quantum entangled states.A typical quantum detectable Byzantine agreement is the GBKCW protocol.The part with the generation and distribution of the lists in the GBKCW protocol was dealed with.In order to keep the GBKCW protocol from the intercept-and-resend strategy,the property of the determination of entangled states were employed to test the sharing state between the parties.

•Nov 1, 2016•0 citations
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.
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 QQQ-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 rounds (where mmm 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.
Clock synchronization for nonfaulty processes in multiprocess networks is indispensable for a variety of technologies. A reliable system must be able to resynchronize the nonfaulty processes upon some components failing causing the distribution of incorrect or conflicting information in the network. The task of synchronizing such networks is related to detectable Byzantine agreement (DBA), which can classically be solved using recursive algorithms if and only if less than one-third of the processes are faulty. Here we introduce a nonrecursive quantum algorithm that solves the DBA and achieves clock synchronization in the presence of arbitrary many faulty processes by using only a single quantum system.
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.
Byzantine agreement, the underlying core of blockchain, aims to make every node in a decentralized network reach consensus. Classical Byzantine agreements unavoidably face two major problems. One is 1/3 fault-tolerance bound, which means that the system to tolerate f malicious players requires at least 3 f + 1 players. The other is the security loopholes from its classical cryptography methods. Here, we propose a Byzantine agreement framework with unconditional security to break this bound with nearly 1/2 fault tolerance due to multiparty correlation provided by quantum digital signatures. It is intriguing that quantum entanglement is not necessary to break the 1/3 fault-tolerance bound, and we show that weaker correlation, such as asymmetric relationship of quantum digital signature, can also work. Our work strictly obeys two Byzantine conditions and can be extended to any number of players without requirements for multiparticle entanglement. We experimentally demonstrate three-party and five-party consensus for a digital ledger. Our work indicates the quantum advantage in terms of consensus problems and suggests an important avenue for quantum blockchain and quantum consensus networks.
Clock synchronization for nonfaulty processes in multiprocess networks is indispensable for a variety of technologies. A reliable system must be able to resynchronize the nonfaulty processes upon some components failing causing the distribution of incorrect or conflicting information in the network. The task of synchronizing such networks is related to Byzantine agreement (BA), which can classically be solved using recursive algorithms if and only if less than one-third of the processes are faulty. Here we introduce a nonrecursive quantum algorithm, based on a quantum solution of the detectable BA, which achieves clock synchronization in the presence of arbitrary many faulty processes by using only a single quantum system.
In distributed computing,Byzantine agreement is a practical method to solve its fault-tolerance problem.There is a variation of the Byzantine agreement which is called detectable Byzantine agreement.This kind of protocol is unsolvable by classical means,but can be solved using quantum resources——quantum entangled states.A typical quantum detectable Byzantine agreement is the GBKCW protocol.The part with the generation and distribution of the lists in the GBKCW protocol was dealed with.In order to keep the GBKCW protocol from the intercept-and-resend strategy,the property of the determination of entangled states were employed to test the sharing state between the parties.