Physic Labs

前沿物理学

量子算法（Shor、Grover）

演示 Grover 算法：在 NN 个元素中放大目标态的振幅。观察态矢量在二维平面内旋转，并检验最优迭代次数 ≈π4N\approx \frac{\pi}{4}\sqrt{N}。

研究

器材

  • 二维平面中旋转的态矢量模型
  • 规模 N 与迭代次数 k 滑块
  • 逐次迭代的目标振幅/概率显示

实验步骤

  1. 设定问题规模

    拖动"规模 N"滑块选择模拟数据库的元素个数（如 N = 25）。观察初始状态轴：目标振幅从 1/N1/\sqrt{N} 开始，N 越大越小。与平均需要 N/2N/2 次尝试的经典搜索对比。

  2. 增加迭代次数

    逐档增大"迭代次数"滑块，观察态矢量向目标轴旋转：每次 Grover 迭代转过角度 2θ2\theta，其中 sin⁡θ=1/N\sin\theta = 1/\sqrt{N}。读取 k 次迭代后测到目标的概率 P(k)=sin⁡2((2k+1)θ)P(k) = \sin^2((2k+1)\theta)。

  3. 寻找最优迭代次数

    对每个 N，扫描使概率最大的 k，并与 k∗≈π4Nk^* \approx \frac{\pi}{4}\sqrt{N} 比较。超过最优值继续迭代，会看到概率反而下降——矢量转过了目标。把 N 调大（如 100）重复实验：k∗k^* 按 N\sqrt{N} 增长，而非 NN。

模拟

实验历史

1982年，理查德·费曼提出用量子系统模拟其他量子系统——量子计算的思想由此发端。大卫·多伊奇（1985年）定义了通用量子图灵机。1994年彼得·秀尔发表多项式时间分解算法，1996年洛夫·格罗弗提出只需 O(N)O(\sqrt{N}) 次查询的搜索算法——相对任何经典方法的二次加速。 与秀尔的数论机制不同，格罗弗算法只用两个几何变换：关于目标态的反射（oracle）和关于均值的反射（扩散算符）。本内特、伯恩斯坦、布拉萨尔和瓦齐拉尼证明 Ω(N)\Omega(\sqrt{N}) 也是量子搜索的下界，因此格罗弗算法渐近最优。小规模演示已在离子阱和超导量子比特上实现。

相关物理学家

理查德·费曼尼尔斯·玻尔

相关知识库主题

量子算法（Shor、Grover）