6.7 CoinFlip算法¶
6.7.1 CoinFlip算法介绍¶
问题描述：¶
E.D.Schell在1945年1月版的美国数学月刊上提出了假币问题，初始问题是给定一定数量的硬币，其中一枚假币的质量和其他真币的质量不一样（外形一样，但质量轻），给定一个天平，可用来确定哪一枚是假币（通过天平的倾斜与否来判断重量差异）。
理解问题：（以下是帮助理解规则）¶
假设给定10枚硬币，其中一枚硬币是假的，质量比真硬币轻。
第一步，将10枚硬币均分为两组，每一组包含5个硬币：
第二步，使用天平来判断：
第三步：根据倾斜程度，可以判断假币在哪一个分组里，如下图，假硬币在左侧。
第四步，将包含假币的5枚硬币拿出来。
第五步，将5枚硬币划分为2组2枚的，外加单独1枚。
第六步，把2组硬币放入天平，查看天平倾斜情况。如果天平，持平，则额外的哪一枚是假币。
第七步，判断天平倾斜情况，如果是下面的情况，表明左侧包含了假币。
第八步，判断可能包含假币的两枚，分别放入天平两侧，一次性就可以判断出真假。
如上问题是对十个硬币的判断。（如上参考维基百科）
当然，该问题在不同的参考文献里有不同的版本，本实验算法里假设：
- 真币的重量均等，假币的质量也均等，假币的质量比真币轻。
- 天平只给我们提供两个信息，平衡（两组币的重量相同）或倾斜。
策略：¶
本实验算法主要是Berstein 和 Vazirani 奇偶校验问题的一个应用，在经典策略里面，每次测量只能有一次，左右两边相同数的硬币数判断。而量子算法是通过构建叠加态从而对经典策略基础上的改进，我们可以同时查询叠加的左右两边状态。
量子策略模型简述：¶
在该问题里，平衡的天平模型可以用一个Oracle来刻画。简称B-Oracle(Balance Oracle)，它是一个N位的寄存器： \(x_1 x_2…x_N∈\{0,1\}^N\)，为了检索这些值，我们需要做一个查询（Query）,查询字符 \(q_1 q_2…q_n∈\{0,1,-1\}^N\),其中包括相同数量的1和-1（数量定义为L）。该Oracle返回1位的答案X，定义如下：
考虑 \(x_1 x_2…x_N\) 表示N个硬币，而且0表示硬币质量均等，1表示有一个假币。因此， \(q_i=1\) 意味着我们把硬币 \(x_i\) 放在天平右侧， \(q_i=-1\) 则表示将x_i放在左侧盘里。这个时候我们必须保证，有相同数量的1和-1（天平里左右两侧放入相同数量的硬币），答案X正确的模拟了天平秤。如： \(X=0\) 则表示天平两边相等，反之 \(X=1\) 表示倾斜。
有效的构造转化W(这里的思想可以参考Gervor算法). 从上面我们也可看出，如果N个硬币里包含了k（k大于1）个假币，那么Find(k)的复杂度是多项式时间复杂，我们已经在Bernstein-Vazirani算法接触了k=2的情况（请参考我们算法库里的Bernstein-Vazirani Algorithm ）。本算法主要目的是展示量子算法的优越性，因此只考虑包含一个假币的情况（即k=1）。
查找所有 k 假硬币的量子查询复杂度是入下表, 给定输入如上描述。
| Results | k=1 | k=2 | k=3 | general |
| Quantum | 1 | 1 | 2<=k<=3 | O(k^(1/4)) |
| Classical | logN | >=2log(N/2) | >=3log(N/3) | Ω(k log(N/k)) |
通过上表，比较清晰的展示了量子策略的优越性，尤其在多假币的情况下，当然，我们一个假币的情况，但是在硬币为N的时候，量子测量一次就可以完成。 一个假币的情况，详情请看Counterfeit Coin Game的参考线路图：
参考线路图：¶
线路说明：紫色的if表示的是测量判断，根据输出的经典信息来判断是否需要执行下一步的操作。上面线路图里判定条件，如果输出为0的时候，则需要执行0 对应的操作，实际上就是从新执行一遍量子线路，反之，执行U_f操作，U_f指代了错误币所在位置的控制非门，目标位最后一位。
6.7.2 CoinFlip算法的实现¶
下面给出 QRunes 实现 CoinFlip 算法的代码示例：
6.7.3 CoinFlip算法小结¶
我们传统的电脑构建模块，只能存储两个状态中的其中一个，就如硬币，50个同时抛掷你只能记录一种正反面的状态，50个硬币同时记录的话，就需要量子计算机就数千兆字节的数据存储才能达到。量子计算机就是这样的，它们是基于量子位的，它可以同时处于两个状态。这可以使每个硬币的单个量子位一次存储所有配置的概率分布