学习论文：

题目：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。目前，我们只需要理解在三个将军的情况下，只要叛徒策略得当，从忠诚的将军视角看其他两个将军的行为并无差异。并且理论上来讲，忠诚的将军们也就无法辨别出到底谁是叛徒。

　　根据这一结论进一步推导可以得出一个更通用的结论，如果存在 m 个叛徒将军，那么当将军总数小于或等于 3m 时（n <= 3m，m代表叛徒将军个数)，叛徒便无法被发现，整个系统的一致性也就无法达成。

当忠臣的个数为 2m + 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接收不同消息的可能结果是检测谁在撒谎或者谁在放弃。

　　两个特定纠缠态的性质为解决DBA问题提出了两种不同的方法。第一种方法的灵感来自于三量子单重态【three-qutrit singlet state】性，它基于六个数字组合的列表[4]，这样的列表也可以使用两个量子密钥分发协议来分发[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]中观察到了这种状态。该协议利用了这种态的两个性质，即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，三方中的每一方在两组投影测量基中随机选择，即他们中的每一个要么在中测，要么在中测，并用他的结果制作一张清单。为了提取结果【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