Editing Fast Quantum Byzantine Agreement
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
Fast Quantum Byzantine Agreement [[Quantum Byzantine Agreement#References|(3)]] is an efficient quantum protocol that solves the classical task of [[Byzantine Agreement]] [[Quantum Byzantine Agreement#References|(8)]]. The protocol allows <math>n</math> players in a network to reach agreement in the presence of <math>t</math> faulty players. The protocol solves the task in the strongest possible failure model (Byzantine failures). The quantum protocol is provably faster than any classical protocol. | |||
'''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], consensus task, failure- | '''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], consensus task, failure-resillient distributed computing | ||
Line 11: | Line 10: | ||
* '''Message size:''' The size of messages (quantum and classical) are unbounded. | * '''Message size:''' The size of messages (quantum and classical) are unbounded. | ||
* '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations. | * '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations. | ||
* '''Failure:''' At most <math>t < n/3</math> (synchronous) or <math>t < n/4</math> (asynchronous) players show Byzantine failures. The Byzantine failed players are allowed to behave arbitrarily and collude to try and prevent the honest players from reaching agreement. The most severe model is used: Byzantine failures are adaptive, computationally unbounded and have full-information (full information of quantum states is | * '''Failure:''' At most <math>t < n/3</math> (synchronous) or <math>t < n/4</math> (asynchronous) players show Byzantine failures. The Byzantine failed players are allowed to behave arbitrarily and collude to try and prevent the honest players from reaching agreement. The most severe model is used: Byzantine failures are adaptive, computationally unbounded and have full-information (full information of quantum states is modeled by giving a classical description of the state to the adversaries). Failures on the communication channels are not considered. | ||
==Outline== | ==Outline== | ||
Line 21: | Line 20: | ||
* Each player transmits its current decision bit to every other player. If a player receives the same bit value from more than 2/3 of the players (including his own), then it sets his decision bit to this majority bit value. Otherwise, that player initiates a Quantum Oblivious Common Coin subroutine with all other players and sets his decision bit to the outcome of this subroutine. | * Each player transmits its current decision bit to every other player. If a player receives the same bit value from more than 2/3 of the players (including his own), then it sets his decision bit to this majority bit value. Otherwise, that player initiates a Quantum Oblivious Common Coin subroutine with all other players and sets his decision bit to the outcome of this subroutine. | ||
* Then each player sequentially executes two classical subroutines to bias the decision value towards <math>0</math> or <math>1</math> respectively. These subroutines guarantee that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value. | * Then each player sequentially executes two classical subroutines to bias the decision value towards <math>0</math> or <math>1</math> respectively. These subroutines guarantee that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value <math>d</math>. | ||
</br> | </br> | ||
Line 35: | Line 34: | ||
*<math>k:</math> security parameter of the VQSS scheme used to implement the Oblivious Common Coin | *<math>k:</math> security parameter of the VQSS scheme used to implement the Oblivious Common Coin | ||
*<math>b_i:</math> input bit of player <math>i</math> | *<math>b_i:</math> input bit of player <math>i</math> | ||
*<math>d:</math> the agreement value at the end of the protocol | *<math>d:</math> the agreement value at the end of the protocol | ||
==Requirements== | ==Hardware Requirements== | ||
*Network stage: [[:Category: | *Network stage: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]] | ||
*Relevant network stage parameters: Required number of qubits <math>q</math>. | *Relevant network stage parameters: Required number of qubits <math>q</math>. | ||
*Benchmark values: The number of qubits <math>q</math> required is precisely known for a finite instance of the protocol. This is calculated in [[Quantum Byzantine Agreement#References|(1)]] for <math>n = 5</math>. They pick the smallest possible security parameter <math>k = 2</math> (of the VQSS scheme) and start calculating the required resources. | *Benchmark values: The number of qubits <math>q</math> required is precisely known for a finite instance of the protocol. This is calculated in [[Quantum Byzantine Agreement#References|(1)]] for <math>n = 5</math>. They pick the smallest possible security parameter <math>k = 2</math> (of the VQSS scheme) and start calculating the required resources. Summarizing they find that each node requires <math>\sim 200</math> operational qubits, on which quantum circuits of depth <math>\sim 2000</math> must be run. The consumed number of Bell pairs is 648 and the total classical communication cost is 21240 bits. It is not entirely clear if these are the expected costs or the cost per round. | ||
*In | *In more asymptotic sense it is known that the required number of qubits per node grows rapidly with the number of nodes <math>n</math>, making it therefore, demanding on qubit requirements. | ||
==Properties== | ==Properties== | ||
Line 58: | Line 52: | ||
Also note that the fairness <math>p</math> of the Quantum Oblivious Common Coin is not a parameter, but rather a result of the specific implementation of the protocol. The global Byzantine Agreement protocol can then tolerate up to <math>t < \left \lfloor{pn}\right \rfloor </math> failures. The Quantum Oblivious Common Coin subroutine proposed by [[Quantum Byzantine Agreement#References|(3)]] has <math>p > 1/3</math> (synchronous case, <math>p > 1/4</math> asynchronous case). | Also note that the fairness <math>p</math> of the Quantum Oblivious Common Coin is not a parameter, but rather a result of the specific implementation of the protocol. The global Byzantine Agreement protocol can then tolerate up to <math>t < \left \lfloor{pn}\right \rfloor </math> failures. The Quantum Oblivious Common Coin subroutine proposed by [[Quantum Byzantine Agreement#References|(3)]] has <math>p > 1/3</math> (synchronous case, <math>p > 1/4</math> asynchronous case). | ||
== | ==Pseudo Code== | ||
See Algorithm 1 and Algorithm 2 in [[Quantum Byzantine Agreement#References|(1)]] for a precise pseudocode. | |||
==Further Information== | ==Further Information== | ||
Line 100: | Line 63: | ||
==References== | ==References== | ||
# [https:// | # [https://iopscience.iop.org/article/10.1088/2058-9565/aa9bb1/meta TNM (2017)] | ||
# [https://link.springer.com/book/10.1007%2F978-3-642-15763-9 LS (2010)] | # [https://link.springer.com/book/10.1007%2F978-3-642-15763-9 LS (2010)] | ||
# [https://dl.acm.org/citation.cfm?doid=1060590.1060662 BH (2005)] | # [https://dl.acm.org/citation.cfm?doid=1060590.1060662 BH (2005)] |