DAOrayaki DAO研究奖金池：
资助地址: DAOrayaki.eth
投票进展：DAO Reviewer 1/0 通 过
赏金总量：60 USD
研究种类：Quantum Computing，Byzantine Generals Algorithm
原文作者：Pierre Decoodt
创作者：skyh@DAOrayaki.org
审核者：Yofu@DAOrayaki.org
原文：Byzantine Generals Turn to Quantum
在四个将军时候，现在可以立刻揭开其中两个叛徒的面具
在谷歌搜索框中键入“ Byzantine generals”，在我撰写本文时，您将得到约27,000,000个结果。可以想象，这些条目中的大多数都不是关于拜占庭历史上的军事人员。事实上，正如1982年 Lamport et al 的开创性论文中所创造的“拜占庭将军问题”，在容错计算、分布式计算机系统、区块链、金融和加密货币等领域都有着广泛的应用。
莱斯利 · 兰波特对这个问题的定义如下:
我们想象拜占庭军队的几个师驻扎在敌人的城外，每个师由自己的将军指挥。将军们只能通过信使相互交流。观察敌人之后，他们必须制定一个共同的行动计划。然而，一些将军可能是叛徒，试图阻止忠诚的将军达成协议。
一个重要的结论是，任何传统的解决方案，只要少于3∙m+ 1的将军，都无法应付 m 个叛徒。
对于三个将军的问题，没有经典的解决方案，对于四个将军的问题，经典的解决方案只允许发现一个叛徒。
这个问题有很多种说法。让我们来处理最流行的一种，被称为可检测的拜占庭协议或可检测的广播，其中的解决方案在最后的决策过程必须满足两个条件:
1. 所有忠诚的将军都同意一个共同的行动计划。
2. 如果总司令是忠诚的，那么所有忠诚的将军都同意总司令的计划。
最近，Fitzi、Gisin和Maurer发表了一份基于 qutrit 的量子协议，解决了三位将军对付一个叛徒的情况下的问题。这可能要归功于量子物理学的怪异本质。在量子计算中，一个信息单位——量子位或者更奇异的量子位，是永远不可能被克隆的，不像经典计算中的对应物—— 比特或者三分位，它们可以无限制地复制。相反，隐形传态允许量子信息的远距离即时传输，最终在空间尺度的量子实验中演示了安全的密钥分配。
拜占庭协议的量子解决方案与量子密钥分配(QKD)之间有着鲜明的对应关系，量子密钥分配是一种已经处于商业状态的安全密码技术。这一点在Fitzi、Gisin和Maurer的文章中得到了明确的体现:
首先，量子状态“仅仅”被用于将具有特定相关性的经典私有随机变量分配给3个玩 家 (每个玩家一个三位元，每个都有不同的值，所有组合具有相同的概率)。这类似于量子力学只提供密钥分发的量子密码学公司。
基于物理量的量子计算系统在今天很少见。然而，使用物理量子位来模拟量子是可能的。四量子比特单重态是由 Adan Cabello 提出的，并用四光子纠缠进行了实验验证。最近，这种方法已经被使用开源的 Qiskit 软件包进行了模拟评估。
相似的解决方案可以被想象成四个不同的纠缠态。这种延伸到四名将军的做法的好处在于，现在这项协议是由三名中尉之间的多数共识达成的，而指挥将军是唯一的叛徒。
这里提出了一个五个量子位的解决方案，用于应对多达两个叛徒的四个将军问题，并在模拟器和 IBM 量子在线系统上进行了测试。
量子解决方案协议
让我们详细说明这四个阶段:
从左上到右下: 1。纠缠量子位通过量子信道分布。图2。双方使用经典的双向信道来检查纠缠是否被破坏。图3。指挥官通过传统的单向渠道向中尉发出命令和相应的核查清单。图4。中间人利用经典的双向通道达成协议。图片由作者提供。
1. 分发纠缠量子位
量子位之间的纠缠可以留给任何一方或外部代理人。这避免了不公平的裁判或臭名昭著的内部敌人的问题。这种方法有效是因为纠缠态在下一阶段得到了各方的验证，而下一阶段是量子密钥分配验证的对应阶段。
若干 m 的量子位五元组被生产出来，量子位处于以下量子状态:
对于每个五连体，前两个量子位(从方程式的左边开始计算)被分配给里指挥官爱丽丝将军，剩下的三个量子位分配给Bob、Carol和Dave中将。将军们用泡利 -z 基准来测量量子位。它们不共享任何结果，并为每个位字符串提供一个有序列表。
在一个理想的无噪声量子系统中，这四个列表是相互关联的，以下是给定的索引:
- 当爱丽丝拿到“00”时，所有中尉都拿到“1”。
- 当爱丽丝持有11，所有中尉持有0。
- 当爱丽丝拿到01时，一个中尉随机拿到1，其他两个拿到0。
- 当爱丽丝拿到10时，一个中尉随机拿到0，其他两个拿到1。
2. 检查纠缠
双方验证了纠缠是正确的，为此，他们通过经典的双向通道进行通信。
然后，每一方从约定的范围内选择一个任意的整数。它们相互传递这些整数。在本地，它们从列表中绘制 M-N 位字符串，使用四个整数之和作为种子。然后他们把这些测试列表放在一个共同的寄存器中。
四方检查测试列表是否始终与纠缠保持关联。
如果是这样的话，有噪声的情况下他们会估算在未来的量子系统游戏中的预期的误差率。这些比例是针对每一对可能的中尉的。对于一个特定的中尉，如果她/他是一个叛徒，他们的军衔会更高。
最后，由测试后剩余的位字符串组成的列表被转换成长度为 n 的整数列表:
- 在 Alice 的列表中，“00”变成0(“撤退”) ，“11”变成1(“攻击”)。位字符串“01”和“10”变成2(“ trap”)。
- 在中尉的名单中，1变成1,0变成0。
正如 Cabello 提出的三个通用协议一样，这四个列表中的每一个都是随机的，与其他三个列表相关联，每一方只知道自己的列表。作为量子的独特之处，在协议基础上的纠缠态确保了每个普通量子的情况确实如此。
3. 发送命令
从这里开始，量子世界结束了。
爱丽丝分开并秘密地向中尉们发出命令，要么“撤退”(0) ，要么“攻击”(1) ，以及相应的索引列表。命令是一样的，除非爱丽丝是个叛徒。
每个中尉确定每个索引的条目是否错误地与顺序匹配。如果他们看到许多匹配，他们会认为 Alice 的命令不一致，并且不采取任何行动: 这打破了没有达成一致的协议。请注意，当任何中尉收到一个长度不合理地限制在 n/3之间的列表时，该协议也被放弃。
4. 达成一致
中尉们互相通知收到的命令。他们检查它们是否完全相同。如果是这样，他们遵循爱丽丝的命令，实现了可检测的广播。
否则，将军中至少有一个叛徒。当两个副官报告不同的命令时，每个人都必须证明自己所说的话。为此，他们都开始了一个回合制的游戏。玩两个游戏是因为所有的游戏场景包括了发送不同命令给对方的两部分。
对于每一场比赛，球员抽签谁先开始。他们轮流发送一个索引，该索引在对手列表中的相应条目必须与他们声称收到的顺序相反。每个球员计算其中的错误，但是没有索引可以被使用两次。当一个玩家发出一个停止标志表示他/她的匹配索引列表已用尽时，游戏就结束。而且它仍然在预先约定的回合次数之后结束(这就证明了相比于一下子交换列表，轮流才是合理的)。
关于这个追捕叛徒行动的细节可以在我的解释性的 Jupyter 笔记本中找到，还有 Python 代码为三位和四位将军收集了解决方案。
每个方案都实现了可检测的广播。
那么更现实的噪声量子系统的情况又如何呢？
在游戏结束时，每个中尉将对手犯错的次数 x 与期望值进行比较。知道了子弹的数量 r，无论对手是否是叛徒他们都使用超几何分布来计算观察 x 的概率。或者，他们也可以使用 x/r 和两个期望值之间的距离(欧氏距离的平方和Jensen-Shannon 距离是很好的候选者)来比较。
因此，可侦测的广播也可以在嘈杂的系统中获得，但需要更长的列表。
在 Qiskit 测试协议 :
建立量子电路
这在 Qiskit 是小菜一碟！在下面的代码片段中，首先定义了与纠缠相对应的状态向量，然后根据这个矢量初始化一个由五个量子位组成的电路。在Pauli-z 基础下的测量结果与五个经典寄存器的结果一致。
import numpy as np
from qiskit import QuantumCircuit
# define the state vector
init_list = np.array( [0., 0., 0., 0., 0., 0., 0., 6.**.5,
0., +1., +1., 0., +1., 0., 0., 0.,
0., 0., 0., +1., 0., +1., +1., 0.,
6.**.5, 0., 0., 0., 0., 0., 0., 0.]) / np.sqrt(18)
# create the circuit
circuit = QuantumCircuit(5)
circuit.initialize(init_list, circuit.qubits)
# add Pauli-Z measurements and draw the circuit
circuit.measure_active()
circuit.draw(output='mpl')
模拟器测试:
设备后端噪音模型模拟是 Qiskit 的一大特色，它可以用来测试这种解决方案是否适用于 IBM Quantum 的在线设备。该协议书在所有可能的情况下都通过了对 FakeSydney 的测试。
一个叛徒的场景:
两个叛徒的情景:
硬件测试:
该协议已在5量子位在线系统上进行了测试。然而，由于缺少辅助量子位，量子电路的深度增加了。因此，在同一纠缠分布的所有可能情况下，叛逆者检测的成功并不总是有保证的。游戏中的最大可能轮数经常被减少，而且叛逆者和非叛逆者的错误率差别很小。
例如，在下面的 ibmq-manila 实验中，检测在两个场景中正确执行，每个场景中有两个叛徒。尽管出错率比忠诚的副手要低一些，但叛徒可以被揭露出来。判断标准是根据一个球员是否是叛徒而预期的错误率的差异。
展望
在量子计算的硬件和软件方面的不断进步使得在具体情况下使用该协议成为可能。我们可以想象一个更高效的专用系统，包括足够数量的量子比特，包括辅助设备，以及具有明智连接的布局。
然而，通向现实世界应用程序的道路需要解决一些问题和测试选项。讨论为什么和如何超出了本文的范围。应考虑采取缓解措施，以纠正高噪音设备中的结果。例如，在这里测试的协议中，翻转列表中具有偶数索引的每个位字符串可以有效地平衡错误率。另一个重点是在整个过程中保持安全传输。
总结
Qiskit，这一协议的证明不仅仅是一个简单的思想实验。实验是在经典计算机和在线量子系统上进行的。然而，实现现实生活中的应用程序将是一个重大的技术挑战。
这个四大拜占庭协议的量子解决方案告诉我们，除了避开窃听者Eva，基于量子的方法可以帮助我们所有人，Alice、Bob、Carol、Dave和其他人，验证信息，同时保证内部可能的敌人的安全。这种量子方法在一个信息以分散的方式日益共享的世界中是有价值的，例如在有区块链担保的交易中。
参考链接：
1.Lamport et al 的开创性论文：
https://lamport.azurewebsites.net/pubs/byz.pdf
2.基于 qutrit 的量子协议：
https://arxiv.org/pdf/quant-ph/0107127v1.pdf
3.远距离即时传输：
https://en.wikipedia.org/wiki/Quantum_teleportation
4.空间尺度的量子实验：
https://en.wikipedia.org/wiki/Quantum_Experiments_at_Space_Scale
5.量子密钥分配：
https://en.wikipedia.org/wiki/Quantum_key_distributionv
6.在今天很少见：
https://medium.com/rigetti/beyond-qubits-unlocking-the-third-state-in-quantum-processors-12d2f84133c4
7.四量子比特单重态：https://arxiv.org/pdf/quant-ph/0210079.pdf
8.实验验证：
https://arxiv.org/pdf/0710.0290v2.pdf
9.Qiskit：https://qiskit.org/
10.模拟评估：
https://2021.qcrypt.net/posters/QCrypt2021Poster200Guba.pdf
11.三个通用协议：https://arxiv.org/pdf/quant-ph/0210079.pdf
12.Jupyter 笔记本：https://github.com/pdc-quantum/byzantine-generals-in-qiskit/blob/main/game-scenarios-byzantine-agreement.ipynb
13.超几何分布：
https://docs.scipy.org/doc/scipy/tutorial/stats/discrete_hypergeom.html
14.距离：
https://docs.scipy.org/doc/scipy/reference/spatial.distance.html
通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！
Media：https://media.daorayaki.org
Discord server: https://discord.gg/wNUPmsGsa4
Medium: https://medium.com/@daorayaki
Email: daorayaki@dorafactory.org
Twitter: @daorayaki_
微信助手：DAOrayaki-Media
小宇宙：DAOrayaki
详情请参考：
Dora Factory支持去中心化DAO研究组织DAOrayaki
DAOrayaki ｜DAOrayaki 开启去中心化治理2.0时代
DAOrayaki ｜风险投资的范式转移：无限主义基金和无限游戏
DAOrayaki ｜DAOrayaki dGov 模型：基于Futarchy的正和游戏
更多关于DAO的文章，关注Dorafactory，查看往期文章。
