Fast Quantum Byzantine Agreement: Difference between revisions

Fast Quantum Byzantine Agreement (edit)

597 bytes removed , 25 April 2019

Write

262

edits

@@ Line 13: / Line 13: @@
 ==Outline==
-[[File:ByzantineAgreementFig.PNG|frame|Schematic representation of an execution of a Byzantine Agreement protocol with <math>n = 5</math> nodes and <math>t = 1</math> Byzantine failure. The red bits indicate the input value of each node, whereas the green bit represents the output. The solution shown satisfies the ''agreement'' and ''validity'' properties. The quantum Byzantine agreement protocol in the strongest possible failure model requires <math>{O}(1)</math> expected number of rounds, whereas a classical lower bound of <math>{\Omega}\left(\sqrt{n / \log(n)}\right)</math> is known.]]
 Here we will sketch the outline of the Fast Quantum Byzantine Agreement protocol by Ben-Or [[Quantum Byzantine Agreement#References|(3)]] that solves Byzantine Agreement using quantum resources. A very nice summary of this protocol is also presented in [[Quantum Byzantine Agreement#References|(1)]].
 The main idea of this protocol is for each player to classically send its proposed input bit <math>b_i</math> to every other player in the network and then collaborate to determine what bit is proposed by a majority of honest players. In the case where failed players make this difficult, a 'good-enough' random coin is globally flipped  (using quantum resources, explained below), which is then classically post-processed to reach agreement among the honest parties. Let us make this more precise.