Write, autoreview, editor, reviewer
3,129
edits
Fast Quantum Byzantine Agreement: Difference between revisions
m
no edit summary
mNo edit summary |
|||
| Line 2: | Line 2: | ||
'''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-resilient distributed computing | ||
| Line 10: | 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 modelled by giving a classical description of the state to the adversaries). Failures on the communication channels are not considered. | ||
==Outline== | ==Outline== | ||
| Line 39: | Line 39: | ||
*Network stage: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]] | *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. Summarising 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 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. | *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. | ||
| Line 53: | Line 53: | ||
==Pseudo Code== | ==Pseudo Code== | ||
See Algorithm 1 and Algorithm 2 in [[Quantum Byzantine Agreement#References|(1)]] for a precise | See Algorithm 1 and Algorithm 2 in [[Quantum Byzantine Agreement#References|(1)]] for a precise pseudo code. | ||
==Further Information== | ==Further Information== | ||