Fast Quantum Byzantine Agreement: Difference between revisions

Fast Quantum Byzantine Agreement (edit)

Revision as of 09:00, 18 April 2019

629 bytes added , 18 April 2019

→‎Properties

Shraddha

Write, autoreview, editor, reviewer

3,129

edits

@@ Line 25: / Line 25: @@
 **<math>b_i:</math> input bit of player <math>i</math>
 **<math>d:</math> the agreement value at the end of the protocol
+==Hardware Requirements==
+Network stage: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]]
+Relevant 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. 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 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==
-*The protocol assumes that the original input qubit is unknown and the protocol is independent of the original input state (universality).
+The protocol-
-*The output copies are not identical and we are able to control the likelihood (fidelity) of the output copies to the original state by pre-preparing the ancillary states with special coefficients.
+* solves the problem in <math>O(1)</math> expected number of rounds, in particular independent of <math>n</math> and <math>t</math>, whereas classically a lower bound of <math>\Omega(\sqrt{n / \log(n)})</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]];
-*Claims for General case:
+* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures;
-**Following inequality holds between the scaling factors <math>s_0</math> and <math>s_1</math></br>
+* reaches ''agreement'' (each player outputs the same bit) under the ''validity'' condition (the agreement value was proposed by at least one player) and is guaranteed to ''terminate eventually'' (infinite executions occur almost never - i.e. have probability measure zero).
-<math>s_0^2 + s_1^2 + s_0 s_1 - s_0 - s_1 \leq 0</math>
-**This elliptic inequality shows the possible value of the scaling parameters.
-**Trade-off inequality between the fidelities of the clones:</br>
-<math>\sqrt{(1 - F_a)(1 - F_b)} \geq \frac{1}{2} - (1 - F_a) - (1 - F_b)</math>
-**Optimality is provided when the fidelities of two clones, <math>F_a</math> and <math>F_b</math>, saturate the above inequality
-*Claims for Special case with bell state:
-**Following ellipse equation holds between the scaling factors <math>a</math> and <math>b</math></br>
-<math>a^2 + b^2 + ab = 1</math>
-**Following equations holds for fidelities of the clones:
-<math>F_a = 1 - \frac{b^2}{2},	F_b = 1 - \frac{a^2}{2}</math>
 ==Pseudo Code==