想象你站在一座堆满十万本旧书的黑暗仓库里。管理员告诉你，只有一本记载着宝藏咒语的书藏在其中，但书架上没有任何编号或分类，你只能一本一本地翻开确认。运气好时一次命中，运气差时翻遍全库才找到。这就是计算机科学中最经典的“无序搜索”难题。 量子世界给出了一种近乎魔法的解法。Grover 算法就像在山谷里对着仓库大喊一声，目标书会发出微弱的回声——而你每喊一次，回声都会被神奇地放大。喊了大约 √N 次 后，回声大到让你能精准锁定目标。整个过程不需要“翻完所有书”，只需要“喊话”，也就是调用一个叫 Oracle（预言机）的“回声探测器”。 这个比喻背后，藏着量子叠加、相位翻转和振幅放大三大核心机制。Grover 算法于 1996 年由 Lov Grover 提出，是量子计算最具代表性的算法之一：它严格证明了量子计算机能在无序搜索问题上超越经典计算机，也为数据库检索、密码安全评估和组合优化带来了全新的可能性。

岗位关联

掌握 Grover 算法，你就读懂了“量子加速到底快在哪、快多少”——这是每一位 AI 从业者理解量子计算经济账的必修第一课。

目录
  1. 可视化演示
  2. 1. 无序搜索难题：经典为何只能线性找
  3. 2. Oracle设计：回声探测器
  4. 3. 振幅放大：回声越喊越响
  5. 4. 迭代次数：喊几次最合适
  6. 5. 复杂度对比：平方加速的账本
  7. 6. 电路实现：回声装置的电路图
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示量子搜索算法Grover的核心流程：均匀叠加态初始化、Oracle相位翻转、扩散变换振幅放大，实现O(√N)加速搜索。

本节配有交互动效（进入视口后自动加载，约 3KB）。

Grover搜索算法 叠加态初始化：N个量子态等概率叠加 Oracle标记：目标态相位翻转 扩散变换：振幅放大目标态概率 O(N) → O(√N) quadratic speedup Grover算法实现量子搜索二次加速

1. 无序搜索难题：经典为何只能线性找

你被关进一座堆满 N 本旧书的黑暗仓库，管理员在门外喊：“只有一本书记载着宝藏咒语，封面有银色月亮标记，自己去找吧！”你环顾四周，书架上没有分类编号、没有索引卡，只能一本一本地翻开书皮确认。运气不好时，翻到第五百本才找到目标。你不禁抱怨：为什么不能把所有书同时翻开？

计算机科学把这个困境称为“无序数据库搜索”：给定一个黑箱函数 f(x)，它只在唯一目标 x=w 时返回 1，要在 N 个可能输入中找到 w。经典世界没有“同时翻开”的能力，只能按顺序逐一检查。线性搜索的查询复杂度为 O(N)，而且理论早已证明：任何经典随机或确定算法，在无序搜索上的期望查询次数都不会低于 N/2。

1996 年，贝尔实验室的 Lov Grover 给出了量子回应：如果允许“同时翻开所有书”——让所有索引处于量子叠加态——再把“翻开动作”换成一次量子 Oracle 调用，搜索可以压缩到 O(√N) 次。量子叠加让“每本书都回答了一次”成为可能，这就是突破经典的起点。

所以 Grover 算法的出发点，就是把“一本一本翻书”的苦力活，变成“让所有书同时被问一遍”的量子魔法。不过魔法需要代价：一个 Oracle 回声探测器，和一套聪明的“回声放大”装置。

Tclassical=O(N),Tgrover=O(N)T_{\text{classical}} = O(N), \quad T_{\text{grover}} = O(\sqrt{N})
通俗理解：经典算法需要的查询次数随 N 成正比增长，Grover 只需要它的平方根那么多。
  1. 经典查询复杂度经典算法需要逐个检查输入，最坏情况要检查 N 次，平均也要 N/2 次，数量级为 O(N)
    Tclassical=O(N)T_{\text{classical}} = O(N)
  2. Grover 查询复杂度Grover 算法只需要约 π/4·√N 次 Oracle 查询即可高概率命中目标，数量级为 O(√N)
    Tgrover=O(N)T_{\text{grover}} = O(\sqrt{N})
  3. 平方加速比经典与量子的查询次数之比为 √N，这正是“平方加速”的数学来源
    TclassicalTgrover=NN=N\frac{T_{\text{classical}}}{T_{\text{grover}}} = \frac{N}{\sqrt{N}} = \sqrt{N}

2. Oracle设计：回声探测器

如何在黑暗中确认“这本是不是目标书”而不把它搬出来？你请管理员制作了一台“回声探测器”：把一本书的编号写在纸条上递进窗口，如果编号对应那本银色月亮封面的书，窗口亮一下绿灯——但不会告诉你书在哪个位置。这就是 Oracle：它只回答“是/否”，从不透露位置。

在量子电路中，Oracle 被实现为一个酉变换 O，它以索引态 |x⟩ 为输入，把“是否为目标”编码进相位里。这样设计很微妙：量子态在测量前不能直接读出 f(x) 的值，读出会破坏叠加态；但我们可以利用相位翻转来“标记”目标，而不影响其他成分。

经典的标记函数 f(x)∈{0,1} 被量子化为相位翻转算符：

Oracle 就像一位沉默的向导：它只在正确时“点头”——留下一个相位负号。而这轻轻一点头产生的相位差异，正是后续振幅放大得以“抓住”目标的唯一把柄。

O∣x⟩=(−1)f(x)∣x⟩O|x\rangle = (-1)^{f(x)} |x\rangle
通俗理解：Oracle 像一位“只会点头不会指路”的向导——它用一个看不见的负号标记目标，为后续放大留下线索。
  1. 经典标记函数f(x) 对目标返回 1，对其余输入返回 0，这是 Oracle 的判断逻辑
    f(x)={1x=w0x≠wf(x) = \begin{cases} 1 & x = w \\ 0 & x \neq w \end{cases}
  2. 相位翻转算符把 f(x) 放到指数上，当 x 是目标时振幅乘上 -1，否则保持不变
    O∣x⟩=(−1)f(x)∣x⟩O|x\rangle = (-1)^{f(x)} |x\rangle
  3. 叠加态下的局部反转把 Oracle 作用在均匀叠加态上，只有目标分量被翻转成负号，其余分量不受影响
    O∣s⟩=1N(−∣w⟩+∑x≠w∣x⟩)O|s\rangle = \frac{1}{\sqrt{N}} \left( -|w\rangle + \sum_{x \neq w} |x\rangle \right)

3. 振幅放大：回声越喊越响

现在你有了回声探测器，站在山谷中央大喊一声。所有书都会“反射”回声，但只有目标书的回声带着特殊的相位标记。山谷的形状会把这些回声重新汇聚、叠加——你每喊一次，目标的回声就增强一点，其他书的回声被平均“摊薄”。这就是振幅放大（Amplitude Amplification）。

一次 Grover 迭代由两步组成：先调用 Oracle 翻转目标相位，再施加扩散算子 D。扩散算子的作用是“关于均匀叠加态的反射”：它把当前的振幅分布做一次均值反射，从而让目标振幅的相对优势扩大。几何上看，这两步合在一起，就是在二维平面上把状态向量向目标方向旋转一个小角度。

为了看清几何本质，我们把状态向量分解为两个正交方向：目标方向 |w⟩ 与所有非目标方向的平均态 |s'⟩。初始均匀叠加态为：

定义角度 θ 满足 sinθ = 1/√N，则 |s⟩ 与 |s'⟩ 的夹角为 θ。每经过一次 Grover 迭代 G = D·O，向量就向 |w⟩ 方向旋转 2θ。经过 k 次迭代后，目标振幅变为：

就像山谷回声每喊一次就增强一点，振幅放大的秘密在于“旋转”而非直接放大——每一次 G 都让状态向量向目标方向转过一个小角度，而这个小角度的起点，正是 Oracle 标记留下的相位差。

∣s⟩=1N∣w⟩+N−1N∣s′⟩|s\rangle = \frac{1}{\sqrt{N}} |w\rangle + \sqrt{\frac{N-1}{N}} |s'\rangle
αk=sin⁡((2k+1)θ)\alpha_k = \sin((2k+1)\theta)
通俗理解：每一次迭代，都像在秋千上顺势推一把，让状态向量向“目标方向”转过一个小角度；角度虽小，积累起来却惊人。
  1. 态分解把叠加态拆成“目标分量 + 非目标分量”两个正交基，便于观察旋转
    ∣s⟩=1N∣w⟩+N−1N∣s′⟩|s\rangle = \frac{1}{\sqrt{N}} |w\rangle + \sqrt{\frac{N-1}{N}} |s'\rangle
  2. 小角度近似当 N 很大时 θ 很小，可以近似为
    θ≈sin⁡θ=1N\theta \approx \sin\theta = \frac{1}{\sqrt{N}}
  3. 累计旋转角每次 Grover 迭代把向量旋转 2θ，k 次后累计旋转 (2k+1)θ，目标振幅即正弦值
    αk=sin⁡((2k+1)θ)\alpha_k = \sin((2k+1)\theta)

4. 迭代次数：喊几次最合适

你可能会以为喊得越多越好。其实不是：山谷里的回声不断叠加，当目标方向的振幅越过峰值后，继续喊反而会让回声开始“过冲”衰减——就像荡秋千，每次推一把，推太多秋千会绕过最高点掉下来。所以“喊多少次”是一个需要精确计算的工程问题。

数学上，我们需要选择整数 k，使目标概率 P_k = sin²((2k+1)θ) 最大化。因为 P_k 最大为 1，理想条件是 (2k+1)θ = π/2。代入 θ ≈ 1/√N 求解，得到最优迭代次数：

以 N=100 为例，k_opt ≈ π/4 × 10 ≈ 7.85，取整 8 次。若继续迭代到 9、10 次，目标概率反而从 99% 回落。更进一步的理论结果表明：任何量子算法至少需要 Ω(√N) 次 Oracle 查询才能解决无序搜索——Grover 算法已经达到这个下界，是最优的。

“会喊话”比“喊得勤”更重要。Grover 算法像一位经验丰富的回声猎人，先心算好在第几个回响处侧耳倾听——多一声都不等。

kopt=⌊π4N⌋k_{\text{opt}} = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor
通俗理解：回声猎人会在第 8 个回响响起时侧耳倾听，因为第 9 个回响已经开始“拐弯”衰减了。
  1. 最大化条件要让目标概率的公式 sin² 达到最大值 1，角度必须等于 π/2
    (2k+1)θ=π2(2k+1)\theta = \frac{\pi}{2}
  2. 解出最优迭代次数代入 θ≈1/√N，得到 k 的表达式，再向下取整
    kopt=⌊π4N⌋k_{\text{opt}} = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor
  3. 过冲现象当 k 超过最优值后，(2k+1)θ 超过 π/2，sin² 开始下降，概率回落
    Pk=sin⁡2((2k+1)θ)随 k 先升后降P_k = \sin^2((2k+1)\theta) \quad \text{随 } k \text{ 先升后降}

5. 复杂度对比：平方加速的账本

我们回到仓库门口，给两种策略算一笔账。经典的方案是“人力翻书”：N 本书平均要翻 N/2 次，N 每扩大一倍，工作量也翻一倍。Grover 方案是“回声定位”：N 扩大到一千万本，喊话次数从约 1000 次涨到约 2500 次，增长平缓得多。

复杂度分析中，我们关心查询次数随 N 的增长规模（Big-O）。经典线性扫描是 O(N)，Grover 是 O(√N)。这被称为“平方加速”（quadratic speedup）。用加速比表示：

当 N=10⁶ 时，经典平均需要 5×10⁵ 次查询，而 Grover 只有约 785 次，快约 637 倍。当 N=10¹² 时，加速比达到 10⁶。不过要清醒地看到：Grover 每步迭代包含 Oracle 与扩散算子，若 Oracle 本身昂贵（例如需要对数据库做 QRAM 读取），总运行时间不完全等于查询次数——复杂度账本要算总账。

从“一趟翻书”到“一声回响”，加速的本质来自量子叠加的并行性。但这份加速是“平方式”而非“指数式”——它足够惊艳，却并非无所不能。

TCTG=NN=N\frac{T_C}{T_G} = \frac{N}{\sqrt{N}} = \sqrt{N}
通俗理解：经典是“线性阶梯”，N 涨多少、路就长多少；Grover 是“压缩弹簧”，N 涨一倍，路只长 41%。
  1. 经典查询量线性扫描平均 N/2 次、最坏 N 次，数量级 O(N)
    TC=O(N)T_C = O(N)
  2. 量子查询量Grover 需要约 π/4·√N 次 Oracle 查询，数量级 O(√N)
    TG=O(N)T_G = O(\sqrt{N})
  3. 加速比两者相除得到 √N，即加速幅度随问题规模增大而增大
    TCTG=NN=N\frac{T_C}{T_G} = \frac{N}{\sqrt{N}} = \sqrt{N}

6. 电路实现：回声装置的电路图

回声定位要真正落地，需要一套可执行的“喊话装置”。它的结构出奇简洁：先让所有候选编号进入“齐声合唱”的叠加状态，接着反复播放“回声探测器 + 山谷反射器”两个模块，最后用一只麦克风（测量）捕捉最大的回响。

在量子电路中，Grover 算法的结构由三部分组成：初始化、循环体、测量。初始化用 H⊗n 门把 n 个量子比特从 |0……0⟩ 制备成均匀叠加态 |s⟩；循环体交替执行 Oracle O 和扩散算子 D，重复 k 次；最后对 n 个量子比特做计算基测量。

扩散算子可以分解为两个 H 门变换夹着一个条件相位翻转——在计算基里实施“关于全零态的反射”，再变换回叠加基：

完整电路作用在寄存器上，相当于把 Grover 迭代 G 重复 k 次：

其中 N=2ⁿ。测量时，以约 1 - 2⁻ⁿ 的高概率坍缩到目标索引 |w⟩。

这条电路把“山谷回声”变成了可执行指令：H 门让所有书“齐声合唱”，Oracle 让目标书“独特回应”，扩散算子让回声“聚焦增强”，最后的测量则像竖起耳朵——几乎总能听到目标的方向。

---

D=H⊗n(2∣0⟩⟨0∣−I)H⊗nD = H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n}
Gk∣s⟩,k≈π42nG^k |s\rangle, \quad k \approx \frac{\pi}{4}\sqrt{2^n}
通俗理解：整条电路把“山谷回声”变成了硬件指令——H 门让所有书齐唱，Oracle 让目标书独唱，扩散算子让独唱越来越响，测量就是把麦克风对准最响的方向。
  1. 初始化叠加对 n 个量子比特施加 H 门，制备均匀叠加态，让所有候选索引同时存在
    ∣s⟩=H⊗n∣0⟩⊗n=1N∑x=0N−1∣x⟩|s\rangle = H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle
  2. 扩散算子分解D = H⊗n(2|0⟩⟨0| − I)H⊗n，先关于全零态做反射，再换回叠加基
    D=H⊗n(2∣0⟩⟨0∣−I)H⊗nD = H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n}
  3. 循环次数重复 Grover 迭代约 π/4·√N 次，其中 N=2ⁿ
    k≈π4N=π42n/2k \approx \frac{\pi}{4}\sqrt{N} = \frac{\pi}{4}2^{n/2}

AI 应用场景

量子数据库检索（数据搜索加速）

阶段：数据检索加速

解决的问题：传统数据库对无序数据的检索只能线性扫描，数据量达 PB 级时成本极高。Grover 算法可以在量子随机访问存储器（QRAM）之上，把“找一条记录”的查询次数从 O(N) 压缩到 O(√N)，对海量非结构化数据的命中检索有指数级性价比的提升。

具体案例：在量子数据库中，每条记录通过哈希生成索引，用户查询被编码为 Oracle（例如“查找用户 ID=13425”）。Grover 在 O(√N) 次 Oracle 调用内锁定记录位置，配合 AI 向量检索可用于量子版本的近似最近邻搜索，替代传统暴力扫描。

密码学安全评估（密钥空间扫描）

阶段：安全评估与参数设计

解决的问题：评估对称加密算法的量子安全性。经典暴力破解 AES-128 需要约 2¹²⁸ 次尝试，Grover 理论上可将搜索空间压缩到 2⁶⁴，这对“后量子时代”的安全参数设计是必须考虑的攻击模型。

具体案例：在后量子安全评估项目中，安全团队用 Grover 的复杂度公式重新测算企业加密体系：AES-128 被视为“量子可达”风险，因此升级到 AES-256（搜索空间 2²⁵⁶，Grover 后仍剩 2¹²⁸ 次，物理上不可行）。这一结论直接影响企业密码套件的选型。

组合优化与约束满足（求解器子程序）

阶段：求解器设计

解决的问题：SAT、图着色等组合优化问题在经典上缺乏多项式算法。Grover 可作为量子求解器的子程序，对候选赋值空间进行平方加速的暴力搜索，为经典启发式方法提供“量子增压”。

具体案例：在组合优化中，用 Grover 加速“在 2ⁿ 个赋值中找到满足约束的那一个”，配合量子计数（Quantum Counting）先估计可行解数量，再动态调整迭代次数；这为自动驾驶路径规划、芯片布线等 NP 困难问题的量子求解提供了新思路。

Python 演示

python35 行
import numpy as np  def grover_simulate(N, target, max_iter=None):    """用经典向量模拟 Grover 量子搜索过程"""    if max_iter is None:        max_iter = int(np.floor(np.pi / 4 * np.sqrt(N)))    psi = np.full(N, 1.0 / np.sqrt(N), dtype=complex)    history = []    for k in range(max_iter + 1):        prob = abs(psi[target]) ** 2        history.append((k, prob))        psi[target] = -psi[target]        avg = np.mean(psi)        psi = 2 * avg - psi    return history  def find_best_iteration(N, target):    hist = grover_simulate(N, target)    best_k, best_prob = max(hist, key=lambda item: item[1])    return best_k, best_prob, hist  if __name__ == "__main__":    N, target = 64, 42    best_k, best_prob, hist = find_best_iteration(N, target)    print(f"搜索空间 N = {N}, 目标索引 = {target}")    print("迭代次数  目标概率")    for k, p in hist:        print(f"{k:>6d}  {p * 100:6.2f}%")    print(f"\n最优迭代次数 = {best_k}")    print(f"最大目标概率 = {best_prob * 100:.2f}%")    theory = np.pi / 4 * np.sqrt(N)    print(f"理论值 pi/4*sqrt(N) ≈ {theory:.2f}")
目的：用经典向量模拟 Grover 算法的振幅放大过程，展示目标概率随迭代次数的变化，并验证最优迭代次数公式。
  1. psi = np.full(N, 1.0 / np.sqrt(N), dtype=complex)让所有候选态“齐声合唱”：把每个索引的振幅初始化为 1/√N，对应量子叠加态。
  2. prob = abs(psi[target]) ** 2提取目标振幅的模平方，即测量命中目标的概率。
  3. psi[target] = -psi[target]Oracle 的相位翻转：在目标状态上留下负号标记。
  4. avg = np.mean(psi)计算当前所有振幅的平均值，这是扩散变换的“山谷反射中心”。
  5. psi = 2 * avg - psi扩散算子：每个振幅关于均值做反射，让目标振幅相对增大。
  6. best_k, best_prob = max(hist, key=lambda item: item[1])从历史记录中找出概率最大的迭代次数。
  7. theory = np.pi / 4 * np.sqrt(N)与理论最优迭代次数公式对照，模拟结果应落在其附近。

常见误区

误区很多初学者认为“量子算法都是指数加速”，所以 Grover 把 N 次搜索变成 √N 次，应该也是指数级别的提升吧？

正解Grover 是平方加速（quadratic speedup），从 O(N) 降到 O(√N)，而不是从 O(N) 降到 O(log N)。以 N=10⁶ 为例，经典要 50 万次，Grover 约 785 次——快 637 倍，但随着 N 增长，加速比只是 √N。只有 Shor 算法那样的特殊问题才是指数加速。

为何常见：把量子算法的“神奇”一概而论，忽略了不同算法有不同加速类型；Shor 的指数加速名气太大，容易以偏概全。

误区“Oracle 能判断某本书是不是目标，那它肯定知道目标在哪。如果 Oracle 知道，经典算法找它帮忙不就行了？”

正解Oracle 只实现了判断函数 f(x)：“这个输入是不是目标？是/否”，它不知道目标在索引空间中的完整位置。经典世界中即使有 Oracle，也必须逐一询问每个索引，仍然是 O(N) 次。Grover 的突破在于用叠加态“同时询问”，而不是 Oracle 开小灶。

为何常见：把“能识别目标的能力”与“知道目标位置的信息”混为一谈；就像海关安检员能认出违禁品，但他并不会告诉你违禁品藏在哪个行李箱里。

误区“反正振幅放大是增强目标，那我一直迭代、迭代很多次，目标概率不就趋近 100% 了吗？”

正解目标概率 P_k = sin²((2k+1)θ) 不是单调递增的。超过最优迭代次数后，旋转角超过 π/2，正弦平方开始下降，出现“过冲”；继续迭代会呈周期性回升与回落。实用中必须用 k_opt ≈ π/4·√N 精确控制迭代次数。

为何常见：直觉上“增强”意味着单调上升，忽略了量子旋转的周期性——就像秋千推到最高点后，再推一把反而会减速。

误区“Grover 只要 O(√N) 次查询，速度飞快，任何搜索问题套上它都能秒杀经典。”

正解复杂度分析计入的是“查询次数”，而每次查询中 Oracle 本身的电路复杂度是额外成本。对于真实数据库，把数据编码进量子态、构建 QRAM 或实现 f(x) 电路可能非常昂贵。查询复杂度 O(√N) 不等于端到端运行时间 O(√N)。

为何常见：混淆“查询复杂度”与“总运行时间”，忽略数据载入和 Oracle 电路实现的工程开销。

误区“Grover 把密钥搜索加快到平方根，那 AES、RSA 这些加密算法立刻全部失效了？”

正解对对称加密（如 AES-128），Grover 把暴力搜索从 2¹²⁸ 降到 2⁶⁴，但 2⁶⁴ 次量子操作目前仍远超物理可实现范围；升级到 AES-256 即可抵御。而 RSA 的安全性建立在质因数分解上，主要威胁来自 Shor 算法而非 Grover。Grover 只影响“暴力搜索类”攻击。

为何常见：把所有密码威胁都归因于“搜索变快”，忽略了不同密码体制依赖不同的数学难题，也低估了绝对问题规模（2⁶⁴ 依然是天文数字）。

面试题

Q1. Grover算法主要解决什么问题？

单选题 · easy

  • A.无序数据库中的目标搜索← 正确答案
  • B.有序数组的快速二分查找
  • C.大规模数据的快速排序
  • D.大整数的高效质因数分解

答案：A。Grover 算法专门解决无序数据库中的唯一目标搜索问题，经典算法只能线性扫描。二分查找需要有序数据，排序是重排问题，质因数分解是 Shor 算法的领域，均与无序搜索无关。

Q2. Grover算法的查询复杂度是多少？

单选题 · easy

  • A.平方根量级的查询次数← 正确答案
  • B.线性量级的查询次数
  • C.对数量级的查询次数
  • D.平方量级的查询次数

答案：A。经典无序搜索平均需要 N/2 次查询（O(N)），Grover 只需约 π/4·√N 次（O(√N)），因此是平方根量级，对应平方加速而非对数或线性加速。

Q3. Grover算法的核心思想是什么？

单选题 · easy

  • A.振幅放大与相位翻转← 正确答案
  • B.比特串逐位取反替换
  • C.分治策略逐步缩小范围
  • D.并行遍历全部数据集合

答案：A。Grover 的核心是“Oracle 相位翻转标记目标 + 扩散算子振幅放大目标”，二者交替作用使目标概率迅速上升。比特取反、分治和并行遍历都是经典算法思路，与量子振幅放大无关。

Q4. Grover迭代中Oracle的作用是？

单选题 · mid

  • A.对目标态施加相位翻转← 正确答案
  • B.直接输出目标的索引号
  • C.将所有非目标振幅清零
  • D.完成最终状态的测量动作

答案：A。Oracle 是一个酉变换 O|x⟩=(-1)^f(x)|x⟩，只对目标态翻转相位（乘上负号），并不输出索引、不清零非目标振幅。测量由最后的计算基测量完成。

Q5. N=100时Grover最优迭代次数约为？

单选题 · mid

  • A.大约8次← 正确答案
  • B.大约9次
  • C.大约16次
  • D.大约32次

答案：A。最优迭代次数 k_opt = ⌊π/4·√N⌋，代入 N=100 得 π/4×10≈7.85，向下取整为 8 次。9 次已开始过冲，16 次、32 次偏差更大。

Q6. Grover扩散算子D的数学形式是？

单选题 · mid

  • A.关于均匀叠加态的反射运算← 正确答案
  • B.关于目标态自身的反射运算
  • C.关于全零态的直接振幅减法
  • D.对量子比特做张量积组合运算

答案：A。扩散算子 D=2|s⟩⟨s|−I，是围绕均匀叠加态 |s⟩ 的反射（均值反射），它放大目标相对非目标的振幅差。B 描述的是 Oracle（绕目标态的反射），C、D 均为干扰项。

Q7. Grover算法的电路组成包括哪些模块？

多选题 · mid

  • A.H门制备均匀叠加态← 正确答案
  • B.Oracle相位翻转模块← 正确答案
  • C.扩散算子振幅放大环节← 正确答案
  • D.经典快速排序核心模块

答案：ABC。Grover 电路 = 初始化（H⊗n 制备均匀叠加）+ 循环体（Oracle 与扩散算子交替）+ 测量三部分。快速排序是经典算法，不属于量子电路模块。

Q8. 超过最优迭代次数后目标概率会？

单选题 · hard

  • A.先下降后呈周期回升← 正确答案
  • B.单调继续向上攀升
  • C.缓慢逼近百分之百
  • D.随机在零与一之间跳

答案：A。目标概率 P_k=sin²((2k+1)θ) 是周期函数。超过 k_opt 后旋转角超过 π/2，概率回落；继续迭代又从低点回升，呈现周期性。因此“过冲”后并非单调上升，也非随机跳变。

Q9. 以下关于Grover加速特征正确的是？

多选题 · hard

  • A.相对经典是平方级加速← 正确答案
  • B.查询次数为根号N量级← 正确答案
  • C.属于指数级量子加速
  • D.可用于暴力破解密钥搜索← 正确答案

答案：ABD。Grover 从 O(N) 到 O(√N) 是平方加速，查询次数为根号 N 量级，可加快对称密钥暴力搜索（如 AES 密钥空间）。它并非指数加速，指数加速的典型是 Shor 算法。

Q10. 以下关于搜索问题查询复杂度的说法正确的是？

多选题 · extreme

  • A.平方根量级的量子查询下界← 正确答案
  • B.平方超线性的经典查询上界
  • C.线性量级的经典查询下界← 正确答案
  • D.对数量级的量子查询下界

答案：AC。Bennett 等人证明无序搜索的量子查询下界为 Ω(√N)，Grover 达到该下界因而最优；经典无序搜索的下界为 Ω(N)。B 中“平方超线性”混淆了上界与下界，D 的“对数下界”与已知结论矛盾。