Grover 搜索
假设有大量候选,其中只有一个是目标。 你能够判断某个候选是否正确,却不知道目标究竟在哪里。 怎样找到这个目标?
设置你的问题
q 个量子比特可以表示 N = 2^q 个候选状态。
|0111⟩
最终量子态将被重复测量,用实际采样形成结果分布。
QPRIMORA 如何把现实问题转成量子问题
真正关键的并不是简单地告诉量子计算机“帮我找到答案”, 而是首先把现实中的候选集合表示成量子状态, 再把“什么才是目标”转换成量子算法可以调用的 Oracle。
逐步查看 QPRIMORA 如何完成转换
点击下面各层,可以看到一个“从大量候选中找到目标”的现实需求, 如何逐步变成量子状态、Oracle 和 Grover 振幅放大过程。
A
REAL PROBLEM
现实中到底要寻找什么?
+
现实问题中有 16 个编号候选,其中只有一个是目标。
B
SEARCH PREDICATE
怎样判断一个候选是不是目标?
+
首先定义判定函数 f(x)。只有当 x 是目标时返回 1, 其他候选全部返回 0。
Grover 的查询复杂度优势建立在可以调用这一 Oracle 进行目标判定的模型之上。
C
ENCODING
候选编号怎样变成量子状态?
+
q 个量子比特可以提供 2^q 个计算基态, 因此可以用这些基态对应现实中的候选编号。
D
SUPERPOSITION
怎样同时表示全部候选?
+
量子寄存器首先从 |00...0⟩ 开始。 对全部量子比特施加 Hadamard 门后, 得到包含所有 N 个候选状态的均匀叠加。
E
ORACLE + DIFFUSION
Grover 怎样逐步放大目标状态?
+
Oracle 首先对目标状态进行相位标记, 随后 Diffusion 操作提高目标状态相对于其他状态的振幅。 重复这一过程后,测量概率逐渐集中到目标状态。
F
RETURN TO REALITY
量子测量怎样重新变成现实答案?
+
Virtual QPU 对最终状态进行重复测量。 出现频率最高的 bitstring 再被解码回现实中的候选编号。
同一个问题,两条计算路径
两条路径接收完全相同的问题: 在 16 个候选中寻找目标 7。
路径 B · 量子计算
为什么问题规模很重要
对于无结构搜索,经典查询次数随候选数量 N 近似线性增长; 在 Oracle 模型下,Grover 所需查询次数的理论量级约为 √N。
上面的比较指的是 Oracle 查询复杂度。 它并不意味着现实中的十亿个普通对象, 可以简单地用 31,623 次普通物理操作完成搜索。 真实系统还必须考虑 Oracle 构造、状态制备、线路深度、 量子门误差、纠错、数据加载以及量子硬件成本。 本网站的 Virtual QPU 运行在经典服务器上, 因此网页运行时间不能作为真实量子硬件加速的证据。
从现实需求到量子计算
这个实例的目的,是让用户清楚看到: 一个简单的现实搜索需求, 怎样被表示成量子问题、怎样经过量子计算处理, 最后又怎样重新变成可以理解的现实答案。