19、量子计算在经典谜题与算法中的优势展现
量子计算在经典谜题与算法中的优势展现
1. 多假币问题的推广
在假币谜题中，数学家Terhal和Smolin在1998年将其推广到任意数量（k>1）的假币情况。他们采用了平衡预言机模型（B - Oracle），具体操作如下：
1. 给定一个N位的输入x = x₁x₂…xₙ ∈ {0, 1}ⁿ。
2. 构建一个N位三值位的查询字符串q = q₁q₂…qₙ ∈ {0, 1, - 1}ⁿ，其中1和 - 1的数量相同。
3. 答案为1位，规则如下：
- 如果x₁q₁ + x₂q₂+… + xₙqₙ = 0，则为平衡（结果为0）。
- 否则为倾斜（结果为1）。
这里的预言机可看作算法中的黑盒部分，它用于简化电路，并能对量子算法和经典算法的复杂度进行比较。一个好的预言机应具备速度快、通用性强和可行性高的特点。以6个硬币中有2个假币（k = 2，N = 6）为例，图展示了B - Oracle的实际应用。
2. 梅明 - 佩雷斯魔术方块游戏
2.1 游戏规则
这是由物理学家David Mermin和A. Peres提出的经典谜题，体现了量子伪心灵感应，即两名玩家在外部观察者看来似乎能进行超自然的交流，这得益于量子纠缠的神奇特性。游戏如下进行：
- 两个玩家Alice和Bob与一名裁判对抗。魔术方块是一个3x3的矩阵，所有元素为0或1，每行元素之和为偶数，每列元素之和为奇数。但实际上，由于矩阵元素数量为奇数，不存在这样有效的组合（可自行用纸笔验证）。
- 裁判向Alice发送一个整数a ∈ {1, 2, 3}，向Bob发送另一个整数b ∈ {1, 2, 3}。Alice需回复