QPRIMORA · QUANTUM COMPUTING DEMO

Grover 搜索

Grover Search · Amplitude Amplification

假设有大量候选,其中只有一个是目标。 你能够判断某个候选是否正确,却不知道目标究竟在哪里。 怎样找到这个目标?

Grover 搜索是一种用于无结构搜索的量子算法。 在 Oracle 查询模型下,经典搜索最坏需要 O(N) 次查询, 而 Grover 算法的查询复杂度可以降低到 O(√N)。 这个实例使用同一个搜索问题,同时展示 经典计算路径和量子计算路径, 让你看到现实问题如何一步一步进入量子计算。
01 · YOUR PROBLEM

设置你的问题

4

q 个量子比特可以表示 N = 2^q 个候选状态。

7

|0111⟩

1000

最终量子态将被重复测量,用实际采样形成结果分布。

当前搜索空间
N 16 个候选
TARGET 7 0111
QUBITS 4 N = 2^q
在 16 个候选中寻找目标 7。
02 · QPRIMORA TRANSFORMATION

QPRIMORA 如何把现实问题转成量子问题

真正关键的并不是简单地告诉量子计算机“帮我找到答案”, 而是首先把现实中的候选集合表示成量子状态, 再把“什么才是目标”转换成量子算法可以调用的 Oracle。

REAL-WORLD PROBLEM 16 个候选中寻找唯一目标
↓
SEARCH FUNCTION f(x)=1 only for target 定义如何判断某个候选是否为目标
↓
QUANTUM REPRESENTATION 4 Qubits → 16 States
↓
TARGET STATE 7 → |0111⟩
↓
QUANTUM ALGORITHM Oracle + Diffusion Grover Amplitude Amplification
↓
VIRTUAL QPU Measurement → Answer
QPRIMORA · INSIDE THE TRANSFORMATION

逐步查看 QPRIMORA 如何完成转换

点击下面各层,可以看到一个“从大量候选中找到目标”的现实需求, 如何逐步变成量子状态、Oracle 和 Grover 振幅放大过程。

A
REAL PROBLEM 现实中到底要寻找什么?
+

现实问题中有 16 个编号候选,其中只有一个是目标。

N 16
→
TARGET 7
B
SEARCH PREDICATE 怎样判断一个候选是不是目标?
+

首先定义判定函数 f(x)。只有当 x 是目标时返回 1, 其他候选全部返回 0。

f(7)=1 · f(x≠7)=0

Grover 的查询复杂度优势建立在可以调用这一 Oracle 进行目标判定的模型之上。

C
ENCODING 候选编号怎样变成量子状态?
+

q 个量子比特可以提供 2^q 个计算基态, 因此可以用这些基态对应现实中的候选编号。

4 Qubits → 2⁴ = 16 states
7
→
0111
→
|0111⟩
D
SUPERPOSITION 怎样同时表示全部候选?
+

量子寄存器首先从 |00...0⟩ 开始。 对全部量子比特施加 Hadamard 门后, 得到包含所有 N 个候选状态的均匀叠加。

H⊗4 |0000⟩ → 1/√16 Σ|x⟩
E
ORACLE + DIFFUSION Grover 怎样逐步放大目标状态?
+

Oracle 首先对目标状态进行相位标记, 随后 Diffusion 操作提高目标状态相对于其他状态的振幅。 重复这一过程后,测量概率逐渐集中到目标状态。

Superposition → Oracle → Diffusion → Repeat → Measurement
F
RETURN TO REALITY 量子测量怎样重新变成现实答案?
+

Virtual QPU 对最终状态进行重复测量。 出现频率最高的 bitstring 再被解码回现实中的候选编号。

BITSTRING 0111
→
ANSWER 7
03 · SAME PROBLEM · TWO COMPUTATIONAL PATHS

同一个问题,两条计算路径

两条路径接收完全相同的问题: 在 16 个候选中寻找目标 7。

CLASSICAL

路径 A · 经典计算

检查候选 0 ↓ 1 ↓ 2 ↓ … ↓ 找到目标 7
QUANTUM PATH

路径 B · 量子计算

16 Candidate States ↓ 4 Qubits ↓ Superposition ↓ Oracle ↓ Diffusion ↓ Virtual QPU ↓ Measurement
WHY SCALE MATTERS

为什么问题规模很重要

对于无结构搜索,经典查询次数随候选数量 N 近似线性增长; 在 Oracle 模型下,Grover 所需查询次数的理论量级约为 √N。

N CLASSICAL GROVER
16 16 ≈ 4
256 256 ≈ 16
10,000 10,000 ≈ 100
1,000,000 1,000,000 ≈ 1,000
1,000,000,000 1,000,000,000 ≈ 31,623
科学说明

上面的比较指的是 Oracle 查询复杂度。 它并不意味着现实中的十亿个普通对象, 可以简单地用 31,623 次普通物理操作完成搜索。 真实系统还必须考虑 Oracle 构造、状态制备、线路深度、 量子门误差、纠错、数据加载以及量子硬件成本。 本网站的 Virtual QPU 运行在经典服务器上, 因此网页运行时间不能作为真实量子硬件加速的证据。

QPRIMORA ARCHITECTURE

从现实需求到量子计算

现实问题 → Representation → Oracle → Grover → Virtual QPU → Measurement → 现实答案

这个实例的目的,是让用户清楚看到: 一个简单的现实搜索需求, 怎样被表示成量子问题、怎样经过量子计算处理, 最后又怎样重新变成可以理解的现实答案。