拜占庭协议书和测谎难题的量子科技协议书的试验证实

学习培训毕业论文：

题型：Solving the liar detection problem using the four-qubit singlet state

创作者：Ad´an Cabelloc

最先，先了解一下拜占庭难题

全文

拜占庭难题

难题来历？

　　拜占庭坐落于现如今的土尔其的伊斯坦布尔，是东罗马帝国的北京首都。因为那时候拜占庭古罗马帝国土地广阔，为了更好地做到防御力目地，每一个部队都隔开很远，大将与大将中间只能依靠信差传信息。在战事的情况下，拜占庭部队内全部大将和副官务必达成一致的的共识，决策是不是有赢的机遇才去进攻对手的势力。可是，在部队内有可能存在内奸和敌方的特工，上下大将们的决策又搅乱总体部队的纪律。在开展的共识时，結果并不意味着大部分人的建议。此刻，在已经知道有组员造反的状况下，其他忠实的大将在没有受内奸的危害下怎样达成一致的协议书，拜占庭难题从此产生。

说到底是：一致性难题

宣布明确提出：

题型：The Byzantine Generals Problem

年代：1982

来源于：ACM Transactions on Programming Languages and Systems

创作者：LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEAS

实际详细介绍

　　实际上，在拜占庭三个大将中发生一个内奸，而且内奸能够随意仿冒信息的状况下，只需内奸保持清醒，他就自始至终没法被发觉，乃至还能导致全部系统软件的舆论压力。

　　理论上的证实，能够参照另一篇毕业论文Reaching agreement in the presence of faults。现阶段，大家只必须了解在三个大将的状况下，只需内奸对策恰当，从忠实的大将角度看别的2个大将的个人行为并无差别。而且理论上而言，忠实的大将们也就没法鉴别出究竟 谁是叛徒。

　　依据这一结果进一步计算能够得到一个更通用性的结果，假如存有 m 个内奸大将，那麼当大将数量小于或等于 3M 时（n <= 3M，m意味着内奸大将数量)，内奸便没法被发觉，全部系统软件的一致性也就没法达到。

当贤臣的数量为 两米 1 时，她们能够忍受 m 个内奸造成的毁坏。

因此，BA难题是不能解的！

如何解决？

现阶段早已拥有许多 完善的解决方法，例如：Raft、Paxos、ZAB 、PBFT等优化算法

参照[2]

能解，除非是：

文中协议书

BA难题：拜占庭难题

DBA难题：可检验的拜占庭难题

如今，将难题再进一步简单化，暂不用考虑到全部网络投票的全过程，只必须考虑到一个大将向别的三个大将各推送了一条指令，忠实大将能不能对这一指令达成一致的状况，为了更好地区别推送指令的将大将和接受信息的大将，大家将推送指令的大将称之为总司令，将接受指令的大将称之为大将

难题

1、B和C是对称性的，意思是？

A是发布者，B和C全是接受者，人物角色一致。

2、$l_a$和$l_{AB}$和$m_{AB}$有什么关系？

3、怎样证实数据信息是一致的？

4、按哪种标准精确测量四量子科技？

毕业论文学习培训 

文中关键研究方向：应用量子技术去处理拜占庭难题，即在三大将中找到内奸或是忠实的大将协商一致，确保战事不容易不成功。

关键分成三一部分：

1、拜占庭难题的详细介绍

2、协议书的设计过程

3、协议书第一步中目录是怎样转化成和派发的？

4、怎样制取这一四量子比特态？

下边详细介绍拜占庭难题

拜占庭难题

　　大家明确提出了一种新的量子科技协议书来处理三方中间的可检验拜占庭协议书(也称之为可检验广播节目)，并解决了可检验的测谎难题。该协议书是由四量子比特纠缠态【four-qubit entangled state】的特性明确提出的，而且协议书的經典一部分比之前的计划方案更简易。除此之外，大家还得出了一个运用四光量子纠缠不清【four-photon entanglement】完成该协议书的实验方案。

　　分布式计算的一个基本上总体目标是在一些分布式系统过程不成功的状况下完成融洽。这必须没有问题部件【nonfaulty components】达到一个协议书。解决这种每日任务的难题被抽象地描述为拜占庭将军难题，也被称作拜占庭协约(BA)。

　　拜占庭部队有三个师，每一个师都由自身的大将指引，已经围堵一座敌城。三个大将A、B和C只有根据太阳龙宝宝互相通讯(即根据成对验证的无差错經典无线信道)。她们务必制订一个一同的计划，要不是0，要不是1(比如，攻击或撤离)。A大将决策制订一个方案，并想将该方案传送给B大将和C大将，根据将信息m_AB （0或是1）发给B，将信息m_AC （0或是1）发给C，随后，B根据向C推送信息m_BC来将方案传输给C，而C根据向B推送信息m_CB来将方案传输给B。殊不知，在其中一位大将(包含A)可能是内奸，尝试阻拦忠实的大将们将方案达成一致。BA难题是设计方案一个协议书，在其中(i)：全部忠实的大将都遵照同样的方案，及其(ii)：假如A是忠实的，那麼每一个忠实的大将都遵照A决策的方案。从忠实的C从A和B接到不一样信息的视角看来，BA难题相当于测谎难题【liar detection problem】，在其中C的每日任务是明确谁在说谎，A或是B。 

　　BA难题已被证实是不能解的，除非是每一个大将都有着一个别的大将不清楚数据目录，该目录但与别的大将的名册目录有关系。因而，处理BA难题能够归纳为处理这种目录的转化成和安全性派发难题。因而，处理BA难题能够归纳为处理这种目录的转化成和安全性派发难题。量子科技协议书使大家可以检测派发的安全系数；殊不知，在产生进攻的状况下，沒有安全性的密秘目录是可以用的，而且全部通讯务必中断。因此，在这类状况下，称之为可检验的拜占庭协议书(DBA)或可检验广播节目的BA难题能够被处理。在DBA难题中，标准(i)和(ii)被放开，促使(i)中全部忠实的大将要不实行同样的行動，要不所有舍弃；(ii)中假如A是忠实的，那麼每一个忠实的大将要不听从A的指令，要不舍弃。因而，我们可以界定用以处理“可检验的测谎难题”议，在该协议书中，忠实的C从A和B接受不一样信息的很有可能結果是检验谁在说谎或是谁在舍弃。

　　2个特殊纠缠态的特性为处理DBA难题明确提出了二种不一样的方式。第一种方式的设计灵感来自于三量子科技单重态【three-qutrit singlet state】性，它根据六个数字组合的目录[4]，那样的目录还可以应用2个量子科技密匙派发协议书来派发[7]。第二种方式是依据四量比特犬纠缠态【four-qubit entangled state】的特性明确提出的，它根据四个数字组合的目录[6]。

　　在这篇毕业论文中，大家详细介绍了一种处理DBA难题的新协议书。它应用的目录比参考文献[4,7]中的目录更简易，应用高效率也比参考文献[6]中的高些。与参考文献[7]对比，它容许与此同时转化成全部目录。除此之外，大家还得出了第一个用以DBA的量子科技协议书的试验演试，及其根据四光量子纠缠不清【four-photon entanglement】来检验说谎的人

协议书详细介绍

　　该协议书由两一部分构成。第一部分的总体目标是运用特殊的四光量子光的偏振纠缠态的特点来转化成和派发三个目录，A的l_A、B的l_B和C的l_C，并查验该派发的安全系数。一旦多方拥有这种明细，在该商议的第二一部分，她们就根据一对經典无线信道应用他们，以达成共识【图一】。中断选择项将仅在派发构件中应用。自此，该协议书开启彻底BA。

 图文解说：可检验拜占庭协议书的量子科技协议书

三位大将A(司令员)、B和C根据两组验证的无差错經典无线信道联接。在协议书的第一部分，在情况下提前准备的四个量子比特被分派给多方，而且在历经一次传送【classical discussion】以后，要不(a)计划方案：每一个大将都获得一个目录l_i，要不(b)计划方案：全部忠实的大将都愿意舍弃。假如挑选(a)计划方案，则在协议书的第二一部分中，A向B(C)推送信息m_AB(m_AC)和一个目录l_AB(l_AC)，而且B(C)向C(B)推送信息m_BC(m_CB)和目录l_BC(l_CB)

详尽点说，目录l_A，l_B，l_C 有下列特性：

（1）这三个目录具备同样的长短L。l_A的原素是任意的三进制(即0、1或2)。l_B和l_C的原素是任意比特犬(即0或1)。

（2）在这儿目录中的第j个原素，大家寻找组成000（即）、111、201、210，每一种几率同样。

（3）除开能够从自身的目录和特性（1）和（2）中推断外，每一方都不可以了解别的方的目录。

第一部分的結果可能是：(a)全部监管方都愿意她们有恰当的明细，而且能够逐渐协议书中的第二一部分，或是(b)愿意停止它。

为了更好地简单化对协议书第二一部分的探讨，一定要注意B和C的人物角色是对称性的，因而大家常说的有关B的全部內容都适用C，相反也是。协议书一部分以下：

(i)当A推送m_AB时，此信息务必附加别的数据信息，这种数据信息务必与信息自身有关，与此同时在任何时刻仅有A了解。因此，A还向B推送一个目录l_AB，即值m_AB发生在l_A中的全部部位。在哪以后，假如A是忠实的，B会遵照自身的方案。

比如：假如A是忠实的，那麼信息是，A的目录是，随后A也务必推送。 

当B接受到m_AB和l_AB时，只很有可能产生下列二种状况之一：

(ia)假如l_AB是适度的长短【依据(1)的特性，大概为L/3】，而且m_AB、l_AB和l_B的确达到(2)，则大家将说数据信息(即m_AB、l_AB和l_B)是一致的。假如数据信息一致，则B将遵照m_AB方案，除非是C在协议书的下一步里能证实A是内奸【见(2)】。

(ib)若m_AB、l_AB和l_B不是一致的，那麼B就能明确A是内奸，B不容易遵照一切方案，直至他在下一步协议书中与C达成共识【见（2）】

比如：若B接到信息内容及其目录，这时候B的目录是I_B= 那麼B接到的数据信息不是一致的。这种数据信息往往不是一致的，是由于I_A在部位5和6上沒有0。

(ii)、信息m_BC不但能够是1或0，还能够是，意为“我收到了不一致的数据信息”。若信息是1或0，则务必随着别的的数据信息来证实信息m_BC 是与B从A那接到的信息是同样的，即B的信息仅有在m_BC=m_AB的状况下才可以从A中得到。因此，B务必向C推送一个目录I_BC，该目录和B从A那接到的目录I_AB同样。

当C接到m_BC和I_BC时，他早已拥有m_AC和I_AC了，随后下边的六种状况很有可能会产生：

(iia)、若m_AC，I_AC和I_C是一致的，m_BC，I_BC和I_C也是一致的，及其m_AC=m_BC，那麼C会按照计划m_AC=m_BC做事。

(iib)、若m_AC，I_AC和I_C是一致的，m_BC，I_BC和I_C也是一致的，可是C从A和B接到互相矛盾的信息内容(0或1)，随后C能明确A是内奸，B是忠实的，由于A是唯一能够向B和C推送一致数据信息的人。因为B和C的人物角色是对称性的，因此B也可以明确A是内奸，C是忠实的。随后C和B将遵照此前明确的方案，比如0。

(iic)、若m_AC，I_AC和I_C是一致的，C接到，随后C将遵照m_AC方案。一定要注意，在这类状况下，B没有办法让坚信C的，由于他事实上从A那边收到了不一致的信息内容。因而，遵照m_AC方案(即便A是内奸)是与另一个忠实的一方达成共识的唯一挑选。

(iid)、若m_AC，I_AC和I_C是一致的，但m_BC，I_BC和I_C不是一致的，随后C明确B是内奸，A是忠实的。随后C将遵照m_AC方案。

(iie)、若m_AC，I_AC和I_C不是一致的，但m_BC，I_BC和I_C是一致的，那麼A便是内奸。随后，与 (iic)状况一样，她们将遵照m_BC方案。

(iif)若m_AC，I_AC和I_C不是一致的，C接到，这代表着C和B都了解A是内奸。那麼C和B将遵照此前决策的计划方案0。

下边详细介绍第一步中的目录是怎样转化成和派发的：

目录转化成和派发

具备特性(1)、(2)和(3)的目录的转化成和派发是根据在多方中间分派的某一特殊情况下提前准备的四个量子比特来完成，随后对四个量子比特开展部分单量子比特精确测量，随后检测(应用成双的經典安全通道)这种精确测量結果是不是表明出所需的关联性。

在大家的协议书中应用的是四量子比特态：

　　在近期的试验[10，11]中观查到这类情况。该协议书运用了这类态的2个特性，即1：四个量子比特（）的同一么正转换下是不会改变的，在其中U是功效在一个量子比特上的一切么正计算；2：是四个量子比特上的投射精确测量結果中间表明出极致的关系【危害】。具体地说，假如A精确测量量子比特(a)和(b)，B精确测量量子比特(c)，及其C精确测量量子比特(d)，而且他们都是在同样的基本上精确测量，那麼：假如量子比特(a)和(b)上的精确测量結果都是1 (A将纪录为单独0)-这将以几率1/3发生，则量子比特(c)上的精确测量結果一定是0 (B将纪录为0)，而且量子比特(d)上的精确测量結果一定是0(C将纪录为0)；假如量子比特(a)和(b)的精确测量結果都为0 (A将纪录为单独1)，则量子比特(c)的精确测量結果务必为1 (B将纪录为1)，而量子比特(d)的精确测量結果务必为1 (C将纪录为1)。最终，假如量子比特(a)和(b)的精确测量結果为0和1，或是1和0 (A将纪录为单独2)，则量子比特(c)和(d)的精确测量結果能够是0和1，或是1和0。

该协议书的派发和检测一部分包含下列流程：

(1)、一个源在情况下发送很多的四量子比特系统软件【four-qubit systems】，针对每一个四量子比特系统软件j，量子比特(a)和(b)被发送至A，量子比特(c)被发送至B，量子比特(d)被发送至C。

(2)、于每一个四量子比特系统软件j，三方中的每一方在2组投射精确测量基中任意挑选，即她们中的每一个要不在中测，要不在中测，并且用他的結果制做一张明细。为了更好地获取結果【the correlated fourfold coincidences】，她们实行下列实际操作。

下边不明白太懂!

在前三分之一的试验中，C告知A和B不论什么时候用这种基检验他们的量子比特 (50%的状况下，A先检验，在此外50%的状况下，B先检验)。随后，C告知A和B什么事情应当被拒绝；

在第二个三分之一的试验中，C和B交换人物角色；

后面三分之一的试验中，A和B交换人物角色。根据交换人物角色，她们保证没有一个大将能在没有被发觉的状况下仿冒一部分协议书。在这里一步以后，每一方都是有一个目录。这种目录【list】的长短全是一样。A有一个三进制目录l_A，而且B和C中的每一个各自具备目录l_B和l_C。

(3) 、C从他的目录l_C中任意挑选一个部位K_c ，规定A和B根据成双的經典无线信道告之她们在同样部位K_c上的結果，假如多方都是在同样的基下精确测量，则她们的結果一定是有关系的，在这里流程后，多方丢掉目录中用以检测的内容。    

(4)、多方互换她们的人物角色；即，B从他的目录中任意挑选一个新部位k_B，并反复流程(3)，随后A挑选新部位k_A，这些。C从头开始该全过程，直至实行了很多检测。

　　协议书的这一部分仅有二种很有可能的結果：在于观察到的量子科技误差(QER)【界定为不正确的精确测量事情与全部的精确测量事情的比例】，随后忠实的大将决策舍弃或应用目录l_A、l_B和l_C来达成共识。

下边详细介绍怎样制取这一四量子比特态！

制取四量子纠缠态

下列省去，不明白！

表1：一部分目录l_A、l_B和l_C是根据试验得到的。斜体字数据是在理想化状况下不应该发生的事情：

　　为了更好地转化成这种目录，多方在17钟头内开展了48 184次精确测量。为了更好地获取每一个周期时间中的【fourfold coincidences】，每一方在检验到光量子时都是会了解别的方。在删掉这些沒有申请注册光量子的内容后，她们得到了目录具备12043个条目地目录l_A、l_B和l_C，该目录包括3000个bits或trits，QER为5.47%。针对协议书的第一部分，每一方都从他的目录中任意挑选了1000个内容。为了更好地查验她们的結果是不是彻底有关，每一方都测算这些挑选出的彻底有关的条目地QER。A的QER为3.32%，B为4.64%，C为5.40%(QER在于任意挑选的非空子集)。针对协议书的第二一部分，多方应用分别目录中剩下的有关内容。表1中表明了这种目录的非空子集。

汇总

　　总而言之，大家引进了一种新的量子科技协议书来处理容错机制分布式计算和数据库查询拷贝中的一个基本上难题。大家的协议书应用更简易的目录，或是比之前的协议书更合理地应用他们，而且容许与此同时转化成全部目录。除此之外，大家还初次明确提出了根据四量子比特纠缠不清来检验DBA和说谎的人的量子科技协议书。尽管一样的难题能够根据联接好几个量子科技密匙派发协议书来处理，但大家的结果显示，在目前技术性下，必须更细微方式的纠缠不清的更实际、更优质的量子科技解决方法是行得通的。

参照

1、拜占庭将军：分布式系统行业的鬼魂

2、动漫漫画：什么叫拜占庭将军难题？

3、全文：Solving the liar detection problem using the four-qubit singlet state