Grover搜索算法(Grover's Search Algorithm)

使用 Grover 的振幅放大算法(Amplitude Amplification)实现具有二次加速的非结构化搜索。

---

问题

非结构化搜索问题(Unstructured Search Problem)

给定一个包含 $N$ 个项目的非结构化数据库和一个函数 $f:\{0,1,\dots ,N-1\}\to \{0,1\}$，其中恰好有一个未知目标 $w$ 使得 $f(w)=1$，对所有 $x\ne w$ 有 $f(x)=0$，任务是找到 $w$。

这是计算机科学中最基本的问题之一。数据库是非结构化的——没有排序、索引或哈希结构可供利用。每次查询只能询问"项目 $x$ 是目标吗？"并接收是/否答案。在没有关于数据的额外信息的情况下，唯一的策略是逐个测试项目。

在量子计算机上，函数 $f$ 作为黑盒 Oracle(Black-Box Oracle)提供——一个可以在叠加态中被查询的酉算子 $U_f$：

$$U_f|x⟩|q⟩=|x⟩|q\oplus f(x)⟩$$

其中 $q$ 是一个 Oracle 量子比特。设置 $q=|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ 将其转换为相位 Oracle(Phase Oracle)，用 $-1$ 相位标记目标：

$$U_w|x⟩=(-1{)}^{f(x)}|x⟩$$

经典与量子复杂度

在经典计算机上，没有结构可供利用，必须逐个检查项目。最坏情况下需要检查所有 $N$ 个项目。平均而言，在检查一半数据库后找到目标：

$$T_{\text{classical}}=\frac{N}{2}=O(N)$$

Grover 算法在量子计算机上仅需：

$$T_{\text{quantum}}=O\left(\sqrt{N}\right)$$

这是可证明最优的——Bennett、Bernstein、Brassard 和 Vazirani（1997）证明了没有任何量子算法能以优于 $O(\sqrt{N})$ 的渐近速度解决非结构化搜索。因此 Grover 算法实现了该问题可能的最优量子加速。

量子优势随数据库规模增长：

$N$（项目数）	经典查询次数	量子查询次数（$\approx \frac{\pi }{4}\sqrt{N}$）	加速比
4（$n=2$）	2	1	2x
8（$n=3$）	4	2	2x
256（$n=8$）	128	13	10x
$2^{20}$	524,288	804	652x
$2^{40}$	$\approx 5.5\times {10}^{11}$	$\approx 8.2\times {10}^5$	$\approx \mathrm{670,000}$x

将 $N=2^n$ 个项目编码在 $n$ 个量子比特中，复杂度比较变为：

$$T_{\text{classical}}=O(2^n),T_{\text{quantum}}=O\left(2^{n/2}\right)$$

这种加速是二次的(Quadratic)，在节省的查询次数上是指数级的。虽然这不如 Shor 算法的指数加速那样显著，但 Grover 加速适用于极其广泛的问题类别。

为什么 Grover 算法很重要

Grover 算法不仅仅是一个搜索工具。它是一个通用的振幅放大(Amplitude Amplification)子程序，可以与其他量子算法组合使用：

• 数据库搜索。 经典应用：在无序列表中查找标记记录。
• SAT 和约束满足问题。 Grover 搜索所有 $2^n$ 个变量赋值为 3-SAT、图着色和 N 皇后等 NP 完全问题提供二次加速。
• 优化。 使用量子指数搜索（Durr-Hoyer 算法）寻找非结构化函数的最小值（或最大值）。
• 碰撞查找。 以比经典方法更少的查询次数检测哈希函数中的碰撞。
• 量子计数。 通过将 Grover 迭代与量子相位估计结合来估计标记项目数 $M$。

振幅放大的直观理解(Amplitude Amplification Intuition)

Grover 算法通过振幅放大(Amplitude Amplification)工作。从所有 $N$ 个基态的均匀叠加开始，然后迭代地放大目标态的振幅，同时抑制所有其他态。每次 Grover 迭代(Grover Iteration) 在由 $|w⟩$ 和非目标态均匀叠加所张成的二维子空间中旋转态矢量。

关键洞察是两个反射的组合构成一个旋转：

1. Oracle 将态关于非目标叠加 $|r⟩$ 反射。
2. 扩散算子(Diffusion Operator) 将态关于均匀叠加 $|s⟩$ 反射。
3. 两个反射的组合是一个角度为 $2\theta$ 的旋转，其中 $\sin \theta =1/\sqrt{N}$。

经过 $R$ 次迭代后，态已向 $|w⟩$ 方向旋转了 $2R\theta$。最优迭代次数使态矢量几乎与 $|w⟩$ 完全对齐。

---

方案

算法概述

Grover 算法分四个阶段进行：

步骤 1 -- 初始化

从 $n$ 个全零量子比特开始：$|{\psi }_0⟩=|0{⟩}^{\otimes n}$。

步骤 2 -- 创建均匀叠加

对每个量子比特施加 Hadamard 门：

$$|{\psi }_1⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩=|s⟩$$

该态在每个基态上有相等的振幅 $\frac{1}{\sqrt{N}}$，包括目标 $|w⟩$。

步骤 3 -- Grover 迭代

每次 Grover 迭代由两个酉操作组成：

3a. 施加 Oracle $U_w$。 Oracle 通过翻转目标态的相位来标记它：

$$U_w|x⟩=\{\begin{array}{ll}-|x⟩& \text{如果 }x=w\\ \phantom{-}|x⟩& \text{如果 }x\ne w\end{array}$$

这可以写成 $U_w=I-2|w⟩⟨w|$。Oracle 将态关于垂直于 $|w⟩$ 的超平面反射。

3b. 施加扩散算子 $D$。 扩散算子将态关于平均振幅反射：

$$D=2|s⟩⟨s|-I,|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

在实践中，$D$ 实现为 $H^{\otimes n}\cdot U_0\cdot H^{\otimes n}$，其中 $U_0=2|0⟩⟨0|-I$ 仅翻转 $|0{⟩}^{\otimes n}$ 的符号。$U_0$ 的电路为：对每个量子比特施加 X，在 $|1{⟩}^{\otimes n}$ 上施加多控 Z 门，然后再次对每个量子比特施加 X。

一次迭代的组合效果是在 $\{|w⟩,|w^{\perp }⟩\}$ 子空间中旋转角度 $2\theta$，其中 $\sin \theta =1/\sqrt{N}$。

步骤 4 -- 最优迭代次数与测量

经过 $R$ 次迭代后，$|w⟩$ 的振幅为 $\sin ((2R+1)\theta )$，在以下条件下最大化：

$$R\approx \frac{\pi }{4\theta }=\frac{\pi }{4\arcsin (1/\sqrt{N})}\approx \frac{\pi }{4}\sqrt{N}$$

成功概率为 $P_{\text{success}}={\sin }^2((2R+1)\theta )$。测量所有量子比特以概率接近 1 获得 $w$。

电路结构

$n$ 个量子比特、$R$ 次迭代的完整 Grover 电路结构如下：

扩散算子 $D$ 分解为：

---

代码

2 量子比特 Grover 算法（4 个项目，1 个目标）

最简单的非平凡情况：$n=2$，$N=4$，目标 $|11⟩$。一次 Grover 迭代即可，因为 $\theta =\arcsin (1/2)=\pi /6$，所以一次旋转 $2\theta =\pi /3$ 将态精确对齐到 $|11⟩$。$|11⟩$ 的 Oracle 就是简单的 CZ 门，它翻转 $|11⟩$ 基态的相位。

from pyqpanda3 import core

# Build the 2-qubit Grover search circuit.
# QProg is the top-level container for quantum operations.
prog = core.QProg()

# Step 1: Create uniform superposition over 4 states (|00>, |01>, |10>, |11>).
# Each state has amplitude 1/sqrt(4) = 0.5.
prog << core.H(0) << core.H(1)

# Step 2: Oracle -- mark |11> with a -1 phase.
# CZ applies a Z gate on qubit 1 conditioned on qubit 0.
# This flips the sign of |11> while leaving all other states unchanged.
prog << core.CZ(0, 1)

# Step 3: Diffusion operator (inversion about the mean).
# Decomposed as: H on all, X on all, CZ (phase flip |00>), X on all, H on all
# Before the X gates, CZ flips |00>. After X gates, this is equivalent
# to flipping |11> in the Hadamard basis, which is the diffusion operator.
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Step 4: Measure both qubits.
prog << core.measure([0, 1], [0, 1])

# Run the circuit.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
print("2-qubit Grover (target |11>):", counts)
# Expected: {'11': ~10000}

预期输出：

2-qubit Grover (target |11>): {'11': 10000}

当 $N=4$ 时，一次迭代将振幅精确旋转至与 $|11⟩$ 完全对齐，成功概率为 100%。这是 Grover 算法唯一实现精确 1.0 成功概率的情况。

搜索不同的 2 量子比特目标

要搜索 $|11⟩$ 以外的目标，在目标比特为 0 的量子比特上用 X 门包裹 CZ Oracle。例如，搜索 $|10⟩$：

from pyqpanda3 import core

prog = core.QProg()

# Uniform superposition
prog << core.H(0) << core.H(1)

# Oracle for |10>: X on qubit 1 maps |10> -> |11>, CZ flips |11>, X restores.
prog << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(1)

# Diffusion operator
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Measure
prog << core.measure([0, 1], [0, 1])

machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
print("2-qubit Grover (target |10>):", counts)
# Expected: {'10': ~10000}

预期输出：

2-qubit Grover (target |10>): {'10': 10000}

3 量子比特 Grover 算法（8 个项目，1 个目标）

对于 $n=3$ 和 $N=8$，最优迭代次数为：

$$R=\lfloor \frac{\pi }{4\arcsin (1/\sqrt{8})}\rfloor =2$$

我们搜索 $|101⟩$。Oracle 用 X 翻转量子比特 1（将 $|101⟩\to |111⟩$），通过 Hadamard 共轭的 Toffoli 门施加受控-受控-Z（CCZ），然后撤销 X。扩散算子使用相同的 CCZ 模式。

from pyqpanda3 import core

def oracle_3qubit_target_101(prog):
    """Mark |101> with a phase flip.

    Strategy: X on qubit 1 maps |101> -> |111>, then CCZ on |111>,
    then X on qubit 1 restores the original basis. The CCZ is
    implemented as H(2) + TOFFOLI(0,1,2) + H(2), which converts
    the Toffoli's bit-flip into a phase-flip on the target qubit.
    """
    # X on qubit 1: |101> becomes |111>
    prog << core.X(1)
    # CCZ via H + Toffoli + H on qubit 2
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    # Undo X on qubit 1
    prog << core.X(1)


def diffusion_3qubit(prog):
    """Apply the 3-qubit diffusion operator.

    D = H^3 * X^3 * CCZ * X^3 * H^3
    The CCZ flips the phase of |111>, which corresponds to
    flipping |000> in the Hadamard basis (i.e., D = 2|s><s| - I).
    """
    prog << core.H(0) << core.H(1) << core.H(2)
    prog << core.X(0) << core.X(1) << core.X(2)
    # CCZ via H + Toffoli + H
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    prog << core.X(0) << core.X(1) << core.X(2)
    prog << core.H(0) << core.H(1) << core.H(2)


# Build the full Grover circuit.
prog = core.QProg()

# Uniform superposition over 8 states
prog << core.H(0) << core.H(1) << core.H(2)

# Two Grover iterations
for _ in range(2):
    oracle_3qubit_target_101(prog)
    diffusion_3qubit(prog)

# Measure all qubits
prog << core.measure([0, 1, 2], [0, 1, 2])

# Run the circuit.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
success = counts.get("101", 0) / sum(counts.values())
print(f"3-qubit Grover (target |101>): {counts}")
print(f"Success rate: {success:.4f}")
# Expected: success rate ~0.945

预期输出：

3-qubit Grover (target |101>): {'101': 9445, '001': 73, '110': 72, ...}
Success rate: 0.9445

成功率为 ${\sin }^2(5\theta )\approx 0.945$，其中 $\theta =\arcsin (1/\sqrt{8})\approx 0.3614$ rad，不精确等于 1.0，因为 $R=2$ 略低于连续最优值 $R_{\text{opt}}\approx 2.27$。

为任意标记态构建 Oracle 电路

目标为 $|w⟩=|w_0{w}_1\dots w_{n-1}⟩$ 的 Grover Oracle 施加 $U_w=I-2|w⟩⟨w|$：

1. 对每个 $w_i=0$ 的量子比特 $i$ 施加 X（将 $|w⟩$ 映射到 $|1{⟩}^{\otimes n}$）。
2. 施加多控 Z 门（在 $|1{⟩}^{\otimes n}$ 上翻转相位）。
3. 撤销步骤 1 中的 X 门。

此模式适用于任何目标态：

from pyqpanda3 import core

def build_oracle(n, target_bits):
    """Construct a Grover oracle that marks a specific target state.

    Args:
        n: Number of qubits.
        target_bits: Bitstring of length n, e.g. '101'.

    Returns:
        A QCircuit applying a phase flip on the target state.

    The oracle works by:
    1. Applying X gates to flip 0-bits to 1, mapping |target> -> |11...1>
    2. Applying a multi-controlled Z on |11...1>
    3. Undoing the X gates
    """
    circ = core.QCircuit()

    # Step 1: X on qubits where target bit is '0'
    for i in range(n):
        if target_bits[i] == '0':
            circ << core.X(i)

    # Step 2: Multi-controlled Z on |1...1>
    # For n=1: just Z. For n=2: CZ. For n>=3: H + Toffoli + H.
    if n == 1:
        circ << core.Z(0)
    elif n == 2:
        circ << core.CZ(0, 1)
    else:
        # CCZ via H + Toffoli + H on last qubit
        circ << core.H(n - 1)
        circ << core.TOFFOLI(0, 1, n - 1)
        circ << core.H(n - 1)

    # Step 3: Undo X gates
    for i in range(n):
        if target_bits[i] == '0':
            circ << core.X(i)

    return circ

构建扩散算子（H-X-MCZ-X-H）

扩散算子 $D=2|s⟩⟨s|-I$ 关于均匀叠加反射。它分解为 $H^{\otimes n}\cdot (2|0⟩⟨0|-I)\cdot H^{\otimes n}$，其中 $2|0⟩⟨0|-I$ 与 $|0{⟩}^{\otimes n}$ 的 Oracle 结构相同：

def build_diffusion(n):
    """Construct the n-qubit diffusion (inversion-about-mean) operator.

    D = H^n * (2|0><0| - I) * H^n
    where (2|0><0| - I) = X^n * (2|1><1| - I) * X^n

    The multi-controlled Z in the middle flips the phase of |11...1>,
    which after the X gates corresponds to |00...0>.
    """
    circ = core.QCircuit()

    # Apply H to all qubits
    for i in range(n):
        circ << core.H(i)

    # Apply X to all qubits (so |00...0> becomes |11...1>)
    for i in range(n):
        circ << core.X(i)

    # Phase flip on |11...1> (was |00...0> before X gates)
    if n == 1:
        circ << core.Z(0)
    elif n == 2:
        circ << core.CZ(0, 1)
    else:
        # Multi-controlled Z via H + Toffoli + H
        circ << core.H(n - 1)
        circ << core.TOFFOLI(0, 1, n - 1)
        circ << core.H(n - 1)

    # Undo X gates
    for i in range(n):
        circ << core.X(i)

    # Undo H gates
    for i in range(n):
        circ << core.H(i)

    return circ

计算最优迭代次数

经过 $R$ 次迭代后的成功概率为 $P(R)={\sin }^2((2R+1)\theta )$，其中 $\theta =\arcsin (1/\sqrt{N})$。当 $(2R+1)\theta =\pi /2$ 时达到最优：

import math

def optimal_grover_iterations(n_qubits, n_targets=1):
    """Compute the optimal number of Grover iterations.

    Args:
        n_qubits: Number of qubits (database size N = 2^n).
        n_targets: Number of marked items (default 1).

    Returns:
        Optimal integer iteration count R.
    """
    N = 2 ** n_qubits
    M = n_targets
    sin_theta = math.sqrt(M / N)

    if sin_theta >= 1.0:
        return 0  # All items marked, no search needed

    theta = math.asin(sin_theta)
    # (2R + 1) * theta ~ pi/2  =>  R ~ pi/(4*theta) - 1/2
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))
    return R

# Show optimal iterations for different database sizes.
print(f"{'n':>3s}  {'N':>8s}  {'theta':>10s}  {'R_opt':>6s}  {'P_success':>10s}")
print("-" * 45)
for n in range(2, 11):
    N = 2 ** n
    theta = math.asin(1.0 / math.sqrt(N))
    R = optimal_grover_iterations(n)
    p_success = math.sin((2 * R + 1) * theta) ** 2
    print(f"{n:3d}  {N:8d}  {theta:10.6f}  {R:6d}  {p_success:10.6f}")

预期输出：

  n         N      theta   R_opt  P_success
---------------------------------------------
  2         4    0.523599       1    1.000000
  3         8    0.361368       2    0.945312
  4        16    0.252680       3    0.961314
  5        32    0.177664       4    0.999024
  6        64    0.125327       6    0.998469
  7       128    0.088659       8    0.999756
  8       256    0.062705      12    0.999407
  9       512    0.044368      17    0.999869
 10      1024    0.031334      25    0.999835

通用 n 量子比特 Grover 搜索函数

将 Oracle、扩散算子和迭代次数组合为单一可复用函数：

from pyqpanda3 import core
import math


def grover_search(n, target_bits, shots=10000):
    """Run Grover's algorithm for a given number of qubits and target.

    Args:
        n: Number of qubits.
        target_bits: Target bitstring, e.g. '101'.
        shots: Number of measurement shots.

    Returns:
        Dictionary of measurement counts.
    """
    if len(target_bits) != n:
        raise ValueError(
            f"Target length ({len(target_bits)}) must equal n ({n})"
        )

    N = 2 ** n
    theta = math.asin(1.0 / math.sqrt(N))
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

    print(f"  n={n}, N={N}, theta={theta:.4f} rad, R={R} iterations")

    prog = core.QProg()

    # Step 1: Uniform superposition
    for i in range(n):
        prog << core.H(i)

    # Step 2: Grover iterations
    for _ in range(R):
        prog << build_oracle(n, target_bits)
        prog << build_diffusion(n)

    # Step 3: Measure
    prog << core.measure(list(range(n)), list(range(n)))

    # Step 4: Execute
    machine = core.CPUQVM()
    machine.run(prog, shots=shots)

    counts = machine.result().get_counts()
    success = counts.get(target_bits, 0) / shots
    print(f"  Target |{target_bits}> probability: {success:.4f}")
    return counts


# Run examples for different database sizes.
print("=== 2-qubit Grover (target |11>) ===")
grover_search(2, "11")

print("\n=== 3-qubit Grover (target |101>) ===")
grover_search(3, "101")

预期输出：

=== 2-qubit Grover (target |11>) ===
  n=2, N=4, theta=0.5236 rad, R=1 iterations
  Target |11> probability: 1.0000

=== 3-qubit Grover (target |101>) ===
  n=3, N=8, theta=0.3614 rad, R=2 iterations
  Target |101> probability: 0.9453

多个标记项

当 $M$ 个项目被标记时，旋转角度变为 $\sin \theta =\sqrt{M/N}$，最优迭代次数变为 $R\approx \frac{\pi }{4}\sqrt{N/M}$。Oracle 通过链接相位翻转独立标记每个目标：

from pyqpanda3 import core
import math


def grover_multi_target(n, targets, shots=10000):
    """Grover search with multiple marked targets.

    Args:
        n: Number of qubits.
        targets: List of target bitstrings, e.g. ['010', '110'].
        shots: Number of measurement shots.

    Returns:
        Dictionary of measurement counts.
    """
    N = 2 ** n
    M = len(targets)
    theta = math.asin(math.sqrt(M / N))
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

    print(f"  N={N}, M={M} targets, R={R} iterations")

    prog = core.QProg()

    # Uniform superposition
    for i in range(n):
        prog << core.H(i)

    for _ in range(R):
        # Oracle: phase flip each target independently
        for target in targets:
            prog << build_oracle(n, target)
        # Diffusion
        prog << build_diffusion(n)

    prog << core.measure(list(range(n)), list(range(n)))

    machine = core.CPUQVM()
    machine.run(prog, shots=shots)

    counts = machine.result().get_counts()
    success = sum(counts.get(t, 0) for t in targets) / shots
    print(f"  Combined success rate: {success:.4f}")
    print(f"  Individual counts: {dict(sorted(counts.items()))}")
    return counts


print("=== 3-qubit Grover, 2 targets (|010>, |110>) ===")
grover_multi_target(3, ["010", "110"])
# Expected: combined success rate ~1.0, each target ~50%

预期输出：

=== 3-qubit Grover, 2 targets (|010>, |110>) ===
  N=8, M=2 targets, R=1 iterations
  Combined success rate: 1.0000
  Individual counts: {'010': 4985, '110': 5015}

当 $N=8$ 中有 $M=2$ 个目标时，$\theta =\pi /4$，一次迭代即为最优，给出 100% 的成功率和每个目标的等概率分布。

使用状态向量验证振幅放大

检查完整的状态向量以直接观察振幅放大：

from pyqpanda3 import core

# 2-qubit Grover without measurement.
prog = core.QProg()

# Uniform superposition
prog << core.H(0) << core.H(1)

# Oracle: CZ marks |11>
prog << core.CZ(0, 1)

# Diffusion
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Run without measurement to get the state vector.
machine = core.CPUQVM()
machine.run(prog, shots=1)
sv = machine.result().get_state_vector()

print("State vector after 1 Grover iteration (2 qubits):")
for i, amp in enumerate(sv):
    bits = format(i, '02b')
    print(f"  |{bits}>: {amp:+.6f}  (prob={abs(amp)**2:.6f})")

# Verify that |11> has near-unit amplitude.
assert abs(sv[3]) > 0.99, "Amplification failed"
print("PASS: |11> has near-unit amplitude.")

预期输出：

State vector after 1 Grover iteration (2 qubits):
  |00>: -0.000000+0.j  (prob=0.000000)
  |01>: -0.000000+0.j  (prob=0.000000)
  |10>: -0.000000+0.j  (prob=0.000000)
  |11>: -1.000000+0.j  (prob=1.000000)
PASS: |11> has near-unit amplitude.

成功概率与迭代次数的关系

成功概率 $P(R)={\sin }^2((2R+1)\theta )$ 呈振荡变化。此示例通过扫描 3 量子比特搜索的迭代次数，展示过度迭代会降低性能：

from pyqpanda3 import core
import math

n = 3
N = 2 ** n
theta = math.asin(1.0 / math.sqrt(N))
target = "111"

print(f"3-qubit Grover (target |{target}>), theta={theta:.4f} rad")
print(f"{'R':>3s}  {'Theory':>10s}  {'Empirical':>10s}")
print("-" * 30)

for R in range(7):
    p_theory = math.sin((2 * R + 1) * theta) ** 2

    prog = core.QProg()
    for i in range(n):
        prog << core.H(i)
    for _ in range(R):
        # Oracle for |111>: no X gates needed since target is all 1s
        prog << core.H(2)
        prog << core.TOFFOLI(0, 1, 2)
        prog << core.H(2)
        # Diffusion
        prog << build_diffusion(n)
    prog << core.measure(list(range(n)), list(range(n)))

    machine = core.CPUQVM()
    machine.run(prog, shots=5000)
    p_emp = machine.result().get_counts().get(target, 0) / 5000

    print(f"{R:3d}  {p_theory:10.6f}  {p_emp:10.4f}")

预期输出：

3-qubit Grover (target |111>), theta=0.3614 rad
  R     Theory   Empirical
------------------------------
  0   0.125000     0.1238
  1   0.781250     0.7827
  2   0.945312     0.9449
  3   0.330078     0.3318
  4   0.330078     0.3291
  5   0.945312     0.9462
  6   0.781250     0.7803

注意 $R=2$ 处的峰值、$R=3$ 处的下降（过度旋转）以及周期性恢复。这展示了选择正确迭代次数的重要性。

带噪声模拟运行

真实量子硬件会引入误差。此示例模拟具有去极化噪声的 Grover 搜索并量化保真度退化：

from pyqpanda3 import core
import math

n = 3
target = "111"
N = 2 ** n
theta = math.asin(1.0 / math.sqrt(N))
R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

# Build the Grover circuit.
prog = core.QProg()
for i in range(n):
    prog << core.H(i)
for _ in range(R):
    # Oracle for |111>
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    # Diffusion
    prog << build_diffusion(n)
prog << core.measure(list(range(n)), list(range(n)))

# Ideal simulation.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
ideal = machine.result().get_counts()

# Noisy simulation with realistic error rates:
# 1% depolarizing on single-qubit gates (H, X)
# 2% depolarizing on two-qubit gates (CNOT, CZ)
noise = core.NoiseModel()
for q in range(n):
    noise.add_quantum_error(core.depolarizing_error(0.01), core.GateType.H, [q])
    noise.add_quantum_error(core.depolarizing_error(0.01), core.GateType.X, [q])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CNOT, [0, 1])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CZ, [0, 1])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CNOT, [0, 2])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CZ, [0, 2])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CNOT, [1, 2])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CZ, [1, 2])
noise.add_quantum_error(core.depolarizing_error(0.03), core.GateType.TOFFOLI, [0, 1, 2])

machine2 = core.CPUQVM()
machine2.run(prog, shots=10000, model=noise)
noisy = machine2.result().get_counts()

print(f"Ideal success:  {ideal.get(target, 0) / 10000:.4f}")
print(f"Noisy success:  {noisy.get(target, 0) / 10000:.4f}")
print(f"Fidelity loss:  {(ideal.get(target, 0) - noisy.get(target, 0)) / 10000:.4f}")
# Expected: ideal ~0.945, noisy ~0.82

预期输出：

Ideal success:  0.9453
Noisy success:  0.8214
Fidelity loss:  0.1239

---

解析

几何解释：二维平面中的旋转

每次 Grover 迭代在二维子空间中执行旋转。定义两个正交矢量：

• $|w⟩$：目标态（我们要搜索的）
• $|r⟩=\frac{1}{\sqrt{N-1}}\sum _{x\ne w}|x⟩$：所有非目标态的均匀叠加

这两个矢量张成完整 $N$ 维希尔伯特空间的一个二维子空间。初始均匀叠加可分解为：

$$|s⟩=\frac{1}{\sqrt{N}}\sum _x|x⟩=\sin \theta |w⟩+\cos \theta |r⟩,\theta =\arcsin \left(\frac{1}{\sqrt{N}}\right)$$

从 $|r⟩$ 向 $|w⟩$ 方向的初始角度 $\theta$ 很小：对于 $N=1024$，$\theta \approx 0.031$ rad。

Oracle $U_w=I-2|w⟩⟨w|$ 关于 $|r⟩$ 反射。它翻转 $|w⟩$ 分量的符号，同时保持 $|r⟩$ 不变。

扩散算子 $D=2|s⟩⟨s|-I$ 关于 $|s⟩$ 反射。它将所有振幅关于其均值取反。

两个反射组合成角度为 $2\theta$ 的旋转：

$$G=D\cdot U_w=\text{角度为 }2\theta \text{ 的旋转，在 }\{|w⟩,|r⟩\}\text{ 平面中}$$

经过 $R$ 次迭代后：

$$G^R|s⟩=\sin ((2R+1)\theta )|w⟩+\cos ((2R+1)\theta )|r⟩$$

旋转角度的数学推导

让我们从基本原理推导旋转。初始均匀叠加为：

$$|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

$|s⟩$ 在 $|w⟩$ 上的投影为：

$$⟨w|s⟩=\frac{1}{\sqrt{N}}$$

定义 $\theta$ 使得：

$$\sin \theta =\frac{1}{\sqrt{N}},\cos \theta =\sqrt{\frac{N-1}{N}}$$

步骤 1：Oracle。 Oracle 关于垂直于 $|w⟩$ 的超平面反射：

$$U_w|s⟩=|s⟩-2⟨w|s⟩|w⟩=|s⟩-\frac{2}{\sqrt{N}}|w⟩$$

在 $\{|w⟩,|r⟩\}$ 基中分解：

$$U_w|s⟩=-\sin \theta |w⟩+\cos \theta |r⟩$$

这是关于 $|r⟩$ 的反射：$|w⟩$ 分量被取反。

步骤 2：扩散。 扩散算子关于 $|s⟩$ 反射：

$$D\cdot U_w|s⟩=2⟨s|U_w|s⟩\cdot |s⟩-U_w|s⟩$$

计算内积：

$$⟨s|U_w|s⟩=1-\frac{2}{N}=\frac{N-2}{N}$$

在二维基中进行代数运算，一次完整迭代后的结果为：

$$G|s⟩=\sin (3\theta )|w⟩+\cos (3\theta )|r⟩$$

这确认了一次迭代旋转 $2\theta$（从角度 $\theta$ 到 $3\theta$）。由数学归纳法，经过 $R$ 次迭代后：

$$G^R|s⟩=\sin ((2R+1)\theta )|w⟩+\cos ((2R+1)\theta )|r⟩$$

最优迭代次数分析

当态与 $|w⟩$ 对齐时成功概率最大化：

$$P(R)={\sin }^2((2R+1)\theta )\le 1$$

当 $(2R+1)\theta =\pi /2$ 时达到最大值：

$$R_{\text{opt}}=\frac{\pi }{4\theta }-\frac{1}{2}\approx \frac{\pi }{4}\sqrt{N}-\frac{1}{2}$$

由于 $R$ 必须是整数，我们四舍五入到最接近的整数并取 $max(1,\cdot )$。

$n$	$N$	$\theta$（rad）	$R_{\text{opt}}$	$P_{\text{success}}$
2	4	0.5236	1	1.0000
3	8	0.3614	2	0.9453
4	16	0.2527	3	0.9613
5	32	0.1777	4	0.9990
8	256	0.0626	12	0.9994
10	1024	0.0313	25	0.9998

对于大 $N$，$\theta \approx 1/\sqrt{N}$ 很小，离散化误差变得可忽略。成功概率随 $N$ 增长指数级趋近于 1。

过度旋转：为什么太多迭代有害

每次迭代旋转固定的 $2\theta$，因此成功概率呈正弦振荡。超过 $R_{\text{opt}}$ 后，态旋转越过目标，降低概率。

这有几个实际影响：

1. 了解 $N$（或 $M$）以选择 $R$。 没有数据库规模信息，你有过度或不足迭代的风险。量子计数可以估计标记项目数。

2. 大 $N$ 更宽容。 概率曲线在峰值附近较宽，因此当 $N$ 很大时，差 $\pm 1$ 次迭代几乎没有影响。

3. 可变迭代策略。 如果 $R$ 未知，尝试 $R=1,2,4,8,\dots$ 并在每次尝试后经典地验证结果。这在处理未知 $M$ 的同时保持 $O(\sqrt{N})$ 的平均复杂度。

标度分析

一次 Grover 运行的总门复杂度为 $O(n\sqrt{N})$，其中 $n={\log }_{2}N$：

• 每次迭代： $O(n)$ 个门用于 Oracle（X 门 + 多控 Z）+ $O(n)$ 个门用于扩散算子 = 每次迭代 $O(n)$ 个门。
• 迭代次数： $O(\sqrt{N})$。
• 总计： $O(n\sqrt{N})=O(\sqrt{N}\log N)$。

多控 Z 门本身可以使用 $n-2$ 个辅助量子比特分解为 $O(n)$ 个 Toffoli 门，因此整个电路使用 $O(n\sqrt{N})$ 个 Toffoli 门。

对于当前量子硬件，实际限制由电路深度和相干时间决定：

量子比特（$n$）	Grover 迭代	近似 Toffoli 数	可行性
2-3	1-2	~10	当前硬件
4-5	3-5	~100	近期
8-10	12-25	~1000	容错时代
20+	800+	~100,000	远未来

多标记项情况

$N$ 个总项目中有 $M$ 个目标时，分析如下变化。定义 $|W⟩=\frac{1}{\sqrt{M}}\sum _{w\text{ marked}}|w⟩$。则：

$$|s⟩=\sqrt{\frac{M}{N}}|W⟩+\sqrt{\frac{N-M}{N}}|r⟩=\sin \theta |W⟩+\cos \theta |r⟩$$

其中 $\sin \theta =\sqrt{M/N}$。最优迭代次数为：

$$R_{\text{opt}}\approx \frac{\pi }{4}\sqrt{\frac{N}{M}}$$

经过 $R$ 次迭代后，测量到 $M$ 个目标态中任意一个的概率为：

$$P_{\text{success}}={\sin }^2((2R+1)\theta )$$

边界情况：

• $M=N/2$：$\theta =\pi /4$，最多 1 次迭代即可。
• $M>N/2$：改为搜索 $N-M$ 个非目标项并取反。
• $M$ 未知：使用量子计数在运行 Grover 之前估计 $M$。

振幅放大推广

Grover 算法是振幅放大(Amplitude Amplification)（Brassard, Hoyer, Mosca, Tapp, 2000）的特例。给定：

• 一个制备态 $|\psi ⟩=\mathcal{A}|0⟩$ 的量子算法 $\mathcal{A}$。
• 一个具有投影算子 $P_{\text{good}}$ 的"好"子空间。

设 $a=⟨\psi |P_{\text{good}}|\psi ⟩$ 为一次应用 $\mathcal{A}$ 后测量到"好"结果的概率。经典重复需要 $O(1/a)$ 次期望试验。振幅放大仅需 $O(1/\sqrt{a})$ 次迭代。

这将 Grover 算法（其中 $\mathcal{A}=H^{\otimes n}$，$a=M/N$）推广到任意量子子程序。应用包括：

• 蒙特卡洛估计。 放大从期望区域采样的概率。
• 量子行走搜索。 加速图上的空间搜索。
• 优化。 在变分算法中提升找到近优解的概率。

振幅放大的迭代次数为：

$$R_{\text{opt}}=\frac{\pi }{4\arcsin (\sqrt{a})}\approx \frac{\pi }{4\sqrt{a}}$$

常见陷阱与调试

陷阱 1：Oracle 方向错误。 Oracle 必须翻转目标态的相位，而非所有非目标态的。验证 $U_w|w⟩=-|w⟩$ 且对 $x\ne w$ 有 $U_w|x⟩=|x⟩$。

陷阱 2：忘记撤销 X 门。 Oracle 模式是 X - MCZ - X。如果忘记第二组 X 门，Oracle 标记了错误的状态，算法失败。

陷阱 3：错误迭代次数。 太少迭代 = 低成功概率。太多 = 过度旋转。始终从 $\theta =\arcsin (\sqrt{M/N})$ 计算 $R$。

陷阱 4：多控 Z 分解不正确。 对于 $n\ge 3$，MCZ 实现为 $H_{\text{last}}\cdot \text{Toffoli}\cdot H_{\text{last}}$。Hadamard 门将 Toffoli 的比特翻转转换为相位翻转。在错误的量子比特上使用 Hadamard 会得到不正确的结果。

陷阱 5：忽略全局相位。 Grover 后的状态矢量可能在目标态上显示全局相位 $-1$（例如 $-|w⟩$ 而非 $|w⟩$）。这在物理上无意义，不影响测量概率。

调试策略： 从 2 量子比特情况开始（数学是精确的），验证获得 100% 成功。然后扩展到 3 量子比特并与理论值 ${\sin }^2((2R+1)\theta )$ 比较。使用状态向量检查（machine.result().get_state_vector()）检查中间点的振幅。

---

总结

方面	详情
问题	在包含 $N=2^n$ 个项目的非结构化数据库中查找标记项 $w$
量子加速	$O(\sqrt{N})$ 次查询 vs. 经典 $O(N)$
算法	均匀叠加 + 重复（Oracle + 扩散）+ 测量
最优迭代次数	单目标时 $R\approx \frac{\pi }{4}\sqrt{N}$
Oracle	目标上的相位翻转：$U_w=I-2|w⟩⟨w|$
扩散	$D=H^{\otimes n}{X}^{\otimes n}\text{MCZ}{X}^{\otimes n}{H}^{\otimes n}$
旋转角度	$\theta =\arcsin (1/\sqrt{N})$，每次迭代旋转 $2\theta$
多目标	$M$ 个目标时 $R\approx \frac{\pi }{4}\sqrt{N/M}$
过度迭代	成功概率振荡；过量迭代降低性能
门复杂度	每次运行 $O(n\sqrt{N})$ 个门

另见

• Deutsch-Jozsa算法 -- 另一个基础量子算法
• 自定义量子门 -- 构建 Oracle 和多控操作
• Bell态制备 -- 基本纠缠操作
• GHZ态制备 -- 多量子比特纠缠
• VQE教程 -- 使用参数化电路的变分算法
• 噪声表征 -- 建模和分析硬件噪声