Grover 搜索算法完整教程¶

本教程详细介绍如何使用 Qibo 实现 Grover 量子搜索算法。

目录¶

1. Grover 算法原理
2. 示例 1：查找全 1 态
3. 示例 2：查找特定数量的 1
4. 示例 3：自定义叠加态
5. 实际应用场景
6. 练习题

---

Grover 算法原理¶

什么是 Grover 算法？¶

Grover 算法是一种量子搜索算法，可以在无结构数据库中以 O(√N) 的复杂度找到目标元素，相比经典算法的 O(N) 有显著的加速。

核心步骤¶

1. 初始化：创建均匀叠加态
2. Oracle（预言机）：标记目标状态（翻转符号）
3. 扩散算子：放大目标状态的振幅
4. 重复：重复步骤 2-3 约 π√(N/M)/4 次
5. 测量：获得目标状态

数学公式¶

最优迭代次数： $$ R = \left\lfloor \frac{\pi}{4} \sqrt{\frac{N}{M}} \right\rfloor $$

其中：

• $N = 2^n$ 是搜索空间大小
• $M$ 是解的数量

---

In [ ]:

# 导入必要的库
import numpy as np
from qibo import Circuit, gates
from qibo.models import Grover
import matplotlib.pyplot as plt

print("Qibo Grover 算法教程")
print(f"当前后端已准备就绪")

# 导入必要的库 import numpy as np from qibo import Circuit, gates from qibo.models import Grover import matplotlib.pyplot as plt print("Qibo Grover 算法教程") print(f"当前后端已准备就绪")

示例 1：查找全 1 态¶

问题描述¶

在 $n$ 个量子比特的系统中，查找所有量子比特都为 1 的状态 $|111...1\rangle$。

实现步骤¶

In [ ]:

# 设置参数
nqubits = 4  # 4个量子比特，搜索空间大小为 2^4 = 16

# 步骤 1：创建叠加态（均匀叠加）
superposition = Circuit(nqubits)
superposition.add([gates.H(i) for i in range(nqubits)])

print("叠加态电路：")
print(superposition())
print(f"\n叠加态创建完成，搜索空间大小：{2**nqubits}")

# 设置参数 nqubits = 4 # 4个量子比特，搜索空间大小为 2^4 = 16 # 步骤 1：创建叠加态（均匀叠加） superposition = Circuit(nqubits) superposition.add([gates.H(i) for i in range(nqubits)]) print("叠加态电路：") print(superposition()) print(f"\n叠加态创建完成，搜索空间大小：{2**nqubits}")

In [ ]:

# 步骤 2：创建 Oracle（预言机）
# Oracle 的作用是标记目标状态 |1111⟩

oracle = Circuit(nqubits + 1)  # +1 是用于 Grover 辅助量子比特
# 使用多控 X 门标记全 1 态
oracle.add(gates.X(nqubits).controlled_by(*range(nqubits)))

print("Oracle 电路：")
print(oracle())

# 步骤 2：创建 Oracle（预言机） # Oracle 的作用是标记目标状态 |1111⟩ oracle = Circuit(nqubits + 1) # +1 是用于 Grover 辅助量子比特 # 使用多控 X 门标记全 1 态 oracle.add(gates.X(nqubits).controlled_by(*range(nqubits))) print("Oracle 电路：") print(oracle())

In [ ]:

# 步骤 3：创建并执行 Grover 算法

grover = Grover(
    oracle=oracle,
    superposition_circuit=superposition,
    number_solutions=1  # 只有一个解（全 1 态）
)

# 执行搜索
solution, iterations = grover()

print(f"找到的解：{solution}")
print(f"需要的迭代次数：{iterations}")
print(f"\n理论最优迭代次数：{int(np.pi/4 * np.sqrt(2**nqubits))}")

# 步骤 3：创建并执行 Grover 算法 grover = Grover( oracle=oracle, superposition_circuit=superposition, number_solutions=1 # 只有一个解（全 1 态） ) # 执行搜索 solution, iterations = grover() print(f"找到的解：{solution}") print(f"需要的迭代次数：{iterations}") print(f"\n理论最优迭代次数：{int(np.pi/4 * np.sqrt(2**nqubits))}")

结果分析¶

• 找到的解：1111 - 所有量子比特都是 1
• 迭代次数：理论值为 $\frac{\pi}{4}\sqrt{16} = 3.14 \approx 3$ 次
• 成功概率：接近 100%

---

示例 2：查找特定数量的 1¶

问题描述¶

查找所有具有恰好 k 个 1 的状态。例如，在 4 个量子比特中查找恰好有 2 个 1 的所有状态：

• 1100, 1010, 1001, 0110, 0101, 0011

这个问题的解的数量是 $\binom{n}{k}$。

In [ ]:

from scipy.special import comb

# 设置参数
nqubits = 4
num_ones = 2  # 查找恰好有 2 个 1 的状态

# 计算解的数量
n_solutions = int(comb(nqubits, num_ones))
print(f"搜索空间大小：{2**nqubits}")
print(f"解的数量：{n_solutions}")
print(f"\n所有解：")
print(f"1100, 1010, 1001, 0110, 0101, 0011")

from scipy.special import comb # 设置参数 nqubits = 4 num_ones = 2 # 查找恰好有 2 个 1 的状态 # 计算解的数量 n_solutions = int(comb(nqubits, num_ones)) print(f"搜索空间大小：{2**nqubits}") print(f"解的数量：{n_solutions}") print(f"\n所有解：") print(f"1100, 1010, 1001, 0110, 0101, 0011")

In [ ]:

# 创建 Oracle
# 注意：这里简化了 Oracle 的实际实现
# 实际应用中需要使用量子加法器来计算 1 的个数

oracle = Circuit(nqubits + 1)
# 简化示例：查找特定状态 1100
oracle.add(gates.X(2))
oracle.add(gates.X(3))
oracle.add(gates.X(4).controlled_by(0, 1, 2, 3))
oracle.add(gates.X(2))
oracle.add(gates.X(3))

# 创建叠加态（使用默认的 Hadamard 叠加）
# 由于使用了 ancilla，需要指定 superposition_qubits

grover = Grover(
    oracle=oracle,
    superposition_qubits=nqubits,  # 指定叠加态使用的量子比特数
    number_solutions=1  # 简化示例：只找一个解
)

# 执行搜索
solution, iterations = grover()

print(f"找到的解：{solution}")
print(f"迭代次数：{iterations}")

# 创建 Oracle # 注意：这里简化了 Oracle 的实际实现 # 实际应用中需要使用量子加法器来计算 1 的个数 oracle = Circuit(nqubits + 1) # 简化示例：查找特定状态 1100 oracle.add(gates.X(2)) oracle.add(gates.X(3)) oracle.add(gates.X(4).controlled_by(0, 1, 2, 3)) oracle.add(gates.X(2)) oracle.add(gates.X(3)) # 创建叠加态（使用默认的 Hadamard 叠加） # 由于使用了 ancilla，需要指定 superposition_qubits grover = Grover( oracle=oracle, superposition_qubits=nqubits, # 指定叠加态使用的量子比特数 number_solutions=1 # 简化示例：只找一个解 ) # 执行搜索 solution, iterations = grover() print(f"找到的解：{solution}") print(f"迭代次数：{iterations}")

迭代 Grover（未知解数量）¶

当不知道解的数量时，可以使用迭代 Grover 算法。

In [ ]:

# 定义检查函数
def check_solution(bitstring, target_count):
    """检查比特串中是否有 target_count 个 1"""
    return bitstring.count('1') == target_count

# 使用迭代模式
grover_iterative = Grover(
    oracle=oracle,  # 使用相同的 oracle
    superposition_qubits=nqubits,
    check=check_solution,  # 提供检查函数
    check_args=(num_ones,),  # 检查函数的参数
    iterative=True  # 使用迭代模式
)

# 执行搜索
# solution, iterations = grover_iterative()
print("迭代 Grover 算法（实际运行已注释）")
print("特点：不需要预先知道解的数量")

# 定义检查函数 def check_solution(bitstring, target_count): """检查比特串中是否有 target_count 个 1""" return bitstring.count('1') == target_count # 使用迭代模式 grover_iterative = Grover( oracle=oracle, # 使用相同的 oracle superposition_qubits=nqubits, check=check_solution, # 提供检查函数 check_args=(num_ones,), # 检查函数的参数 iterative=True # 使用迭代模式 ) # 执行搜索 # solution, iterations = grover_iterative() print("迭代 Grover 算法（实际运行已注释）") print("特点：不需要预先知道解的数量")

示例 3：自定义叠加态¶

高级应用¶

在某些应用中，我们可能需要在非均匀叠加态中搜索。

In [ ]:

# 创建自定义叠加态
def create_custom_superposition(nqubits, target_ones):
    """
    创建包含恰好有 target_ones 个 1 的所有状态的叠加态
    """
    n_anc = int(np.ceil(np.log2(target_ones + 1)))
    c = Circuit(nqubits + n_anc)
    
    # 这里简化实现
    # 实际应用中需要更复杂的电路
    for i in range(nqubits):
        c.add(gates.H(i))
    
    return c

# 创建自定义叠加态
superposition_custom = create_custom_superposition(4, 2)

print("自定义叠加态电路创建完成")
print(superposition_custom())

# 创建自定义叠加态 def create_custom_superposition(nqubits, target_ones): """ 创建包含恰好有 target_ones 个 1 的所有状态的叠加态 """ n_anc = int(np.ceil(np.log2(target_ones + 1))) c = Circuit(nqubits + n_anc) # 这里简化实现 # 实际应用中需要更复杂的电路 for i in range(nqubits): c.add(gates.H(i)) return c # 创建自定义叠加态 superposition_custom = create_custom_superposition(4, 2) print("自定义叠加态电路创建完成") print(superposition_custom())

In [ ]:

# 创建对应的 Oracle
oracle_custom = Circuit(5)
oracle_custom.add(gates.X(4).controlled_by(0, 1, 2, 3))

# 使用自定义叠加态
grover_custom = Grover(
    oracle=oracle_custom,
    superposition_circuit=superposition_custom,
    superposition_qubits=4,
    superposition_size=6,  # 叠加态中实际包含的状态数
    number_solutions=1
)

print("自定义 Grover 模型创建完成")
print("\n关键参数：")
print("- superposition_qubits: 叠加态使用的量子比特数")
print("- superposition_size: 叠加态中实际包含的状态数")
print("- number_solutions: 目标解的数量")

# 创建对应的 Oracle oracle_custom = Circuit(5) oracle_custom.add(gates.X(4).controlled_by(0, 1, 2, 3)) # 使用自定义叠加态 grover_custom = Grover( oracle=oracle_custom, superposition_circuit=superposition_custom, superposition_qubits=4, superposition_size=6, # 叠加态中实际包含的状态数 number_solutions=1 ) print("自定义 Grover 模型创建完成") print("\n关键参数：") print("- superposition_qubits: 叠加态使用的量子比特数") print("- superposition_size: 叠加态中实际包含的状态数") print("- number_solutions: 目标解的数量")

实际应用场景¶

1. 数据库搜索¶

# 在未排序的数据库中查找特定记录
# 数据库大小：N = 2^n
# 经典算法：O(N)
# Grover 算法：O(√N)

In [ ]:

# 示例：在 8 个记录中查找
nqubits = 3  # 2^3 = 8 个记录
target_record = 5  # 查找记录 5 (二进制：101)

# 创建叠加态
superposition = Circuit(nqubits)
superposition.add([gates.H(i) for i in range(nqubits)])

# 创建 Oracle - 标记记录 5
binary = format(target_record, f'0{nqubits}b')
oracle = Circuit(nqubits + 1)
for i, bit in enumerate(binary):
    if bit == '0':
        oracle.add(gates.X(i))
oracle.add(gates.X(nqubits).controlled_by(*range(nqubits)))
for i, bit in enumerate(binary):
    if bit == '0':
        oracle.add(gates.X(i))

# 执行 Grover 搜索
grover_db = Grover(oracle, superposition_circuit=superposition, number_solutions=1)
solution, iterations = grover_db()

print(f"数据库大小：{2**nqubits} 个记录")
print(f"目标记录：{target_record} (二进制：{binary})")
print(f"找到的解：{solution}")
print(f"迭代次数：{iterations}")
print(f"\n加速比：{(2**nqubits) / np.sqrt(2**nqubits):.2f}x")

# 示例：在 8 个记录中查找 nqubits = 3 # 2^3 = 8 个记录 target_record = 5 # 查找记录 5 (二进制：101) # 创建叠加态 superposition = Circuit(nqubits) superposition.add([gates.H(i) for i in range(nqubits)]) # 创建 Oracle - 标记记录 5 binary = format(target_record, f'0{nqubits}b') oracle = Circuit(nqubits + 1) for i, bit in enumerate(binary): if bit == '0': oracle.add(gates.X(i)) oracle.add(gates.X(nqubits).controlled_by(*range(nqubits))) for i, bit in enumerate(binary): if bit == '0': oracle.add(gates.X(i)) # 执行 Grover 搜索 grover_db = Grover(oracle, superposition_circuit=superposition, number_solutions=1) solution, iterations = grover_db() print(f"数据库大小：{2**nqubits} 个记录") print(f"目标记录：{target_record} (二进制：{binary})") print(f"找到的解：{solution}") print(f"迭代次数：{iterations}") print(f"\n加速比：{(2**nqubits) / np.sqrt(2**nqubits):.2f}x")

2. 3-SAT 问题求解¶

Grover 算法可以用于解决 NP 完全问题，如 3-SAT。

In [ ]:

# 简化的 3-SAT 示例
# 子句：(x1 OR x2 OR x3) AND (¬x1 OR x2 OR ¬x3)

def create_3sat_oracle(nqubits, clauses):
    """
    为 3-SAT 问题创建 Oracle
    
    参数:
        nqubits: 变量数量
        clauses: 子句列表，每个子句是 3 个文字的元组
    """
    oracle = Circuit(nqubits + 1)
    
    # 实际实现需要多控门和辅助量子比特
    # 这里简化演示
    
    return oracle

# 定义 3-SAT 问题
clauses = [
    [(1, 0), (1, 0), (1, 0)],  # (x1 OR x2 OR x3)
    [(0, 0), (1, 0), (0, 0)]   # (¬x1 OR x2 OR ¬x3)
]
# 其中 (is_positive, var_index)

# 创建 Oracle
oracle_3sat = create_3sat_oracle(3, clauses)

print("3-SAT 问题 Oracle 创建完成")
print("\n注意：完整的 3-SAT 求解请参考 examples/grover3sat/")

# 简化的 3-SAT 示例 # 子句：(x1 OR x2 OR x3) AND (¬x1 OR x2 OR ¬x3) def create_3sat_oracle(nqubits, clauses): """ 为 3-SAT 问题创建 Oracle 参数: nqubits: 变量数量 clauses: 子句列表，每个子句是 3 个文字的元组 """ oracle = Circuit(nqubits + 1) # 实际实现需要多控门和辅助量子比特 # 这里简化演示 return oracle # 定义 3-SAT 问题 clauses = [ [(1, 0), (1, 0), (1, 0)], # (x1 OR x2 OR x3) [(0, 0), (1, 0), (0, 0)] # (¬x1 OR x2 OR ¬x3) ] # 其中 (is_positive, var_index) # 创建 Oracle oracle_3sat = create_3sat_oracle(3, clauses) print("3-SAT 问题 Oracle 创建完成") print("\n注意：完整的 3-SAT 求解请参考 examples/grover3sat/")

Grover 算法性能分析¶

In [ ]:

# 比较不同问题规模下的性能
def analyze_grover_performance(max_qubits=12):
    """
    分析 Grover 算法在不同问题规模下的性能
    """
    qubits_range = range(2, max_qubits + 1)
    
    classic_ops = []
    quantum_ops = []
    speedup = []
    
    for n in qubits_range:
        N = 2**n
        # 经典算法平均操作数
        classic = N / 2
        
        # Grover 算法操作数
        quantum = (np.pi / 4) * np.sqrt(N)
        
        classic_ops.append(classic)
        quantum_ops.append(quantum)
        speedup.append(classic / quantum)
    
    # 绘图
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))
    
    # 操作数对比
    axes[0].plot(qubits_range, classic_ops, 'o-', label='经典算法', linewidth=2)
    axes[0].plot(qubits_range, quantum_ops, 's-', label='Grover 算法', linewidth=2)
    axes[0].set_xlabel('量子比特数', fontsize=12)
    axes[0].set_ylabel('操作数（对数尺度）', fontsize=12)
    axes[0].set_yscale('log')
    axes[0].set_title('算法复杂度对比', fontsize=14)
    axes[0].legend(fontsize=11)
    axes[0].grid(alpha=0.3)
    
    # 加速比
    axes[1].plot(qubits_range, speedup, '^-', color='green', linewidth=2)
    axes[1].set_xlabel('量子比特数', fontsize=12)
    axes[1].set_ylabel('加速比', fontsize=12)
    axes[1].set_title('Grover 算法加速比', fontsize=14)
    axes[1].grid(alpha=0.3)
    
    plt.tight_layout()
    plt.show()
    
    # 打印关键数据
    print("\n性能对比表：")
    print("量子比特数 | 搜索空间 | 经典操作数 | Grover操作数 | 加速比")
    print("-" * 75)
    for n in range(2, max_qubits + 1, 2):
        N = 2**n
        idx = n - 2
        print(f"{n:4d} | {2**n:8d} | {classic_ops[idx]:10.0f} | {quantum_ops[idx]:12.2f} | {speedup[idx]:7.2f}x")

# 执行分析
analyze_grover_performance(12)

# 比较不同问题规模下的性能 def analyze_grover_performance(max_qubits=12): """ 分析 Grover 算法在不同问题规模下的性能 """ qubits_range = range(2, max_qubits + 1) classic_ops = [] quantum_ops = [] speedup = [] for n in qubits_range: N = 2**n # 经典算法平均操作数 classic = N / 2 # Grover 算法操作数 quantum = (np.pi / 4) * np.sqrt(N) classic_ops.append(classic) quantum_ops.append(quantum) speedup.append(classic / quantum) # 绘图 fig, axes = plt.subplots(1, 2, figsize=(14, 5)) # 操作数对比 axes[0].plot(qubits_range, classic_ops, 'o-', label='经典算法', linewidth=2) axes[0].plot(qubits_range, quantum_ops, 's-', label='Grover 算法', linewidth=2) axes[0].set_xlabel('量子比特数', fontsize=12) axes[0].set_ylabel('操作数（对数尺度）', fontsize=12) axes[0].set_yscale('log') axes[0].set_title('算法复杂度对比', fontsize=14) axes[0].legend(fontsize=11) axes[0].grid(alpha=0.3) # 加速比 axes[1].plot(qubits_range, speedup, '^-', color='green', linewidth=2) axes[1].set_xlabel('量子比特数', fontsize=12) axes[1].set_ylabel('加速比', fontsize=12) axes[1].set_title('Grover 算法加速比', fontsize=14) axes[1].grid(alpha=0.3) plt.tight_layout() plt.show() # 打印关键数据 print("\n性能对比表：") print("量子比特数 | 搜索空间 | 经典操作数 | Grover操作数 | 加速比") print("-" * 75) for n in range(2, max_qubits + 1, 2): N = 2**n idx = n - 2 print(f"{n:4d} | {2**n:8d} | {classic_ops[idx]:10.0f} | {quantum_ops[idx]:12.2f} | {speedup[idx]:7.2f}x") # 执行分析 analyze_grover_performance(12)

练习题¶

练习 1：基本应用¶

在 5 个量子比特的系统中，查找状态 10101。

练习 2：多解问题¶

在 4 个量子比特的系统中，查找所有偶数校验的状态（即 1 的个数为偶数）。

In [ ]:

# 练习 1 的解答框架
def exercise_1_solution():
    """
    查找状态 10101
    """
    nqubits = 5
    target_state = '10101'
    
    # 创建叠加态
    superposition = Circuit(nqubits)
    superposition.add([gates.H(i) for i in range(nqubits)])
    
    # 创建 Oracle
    oracle = Circuit(nqubits + 1)
    # TODO: 完成 Oracle 的创建
    
    # 执行 Grover
    # grover = Grover(...)
    # solution, iterations = grover()
    
    print(f"目标状态：{target_state}")
    # print(f"找到的解：{solution}")

# 运行练习
exercise_1_solution()

# 练习 1 的解答框架 def exercise_1_solution(): """ 查找状态 10101 """ nqubits = 5 target_state = '10101' # 创建叠加态 superposition = Circuit(nqubits) superposition.add([gates.H(i) for i in range(nqubits)]) # 创建 Oracle oracle = Circuit(nqubits + 1) # TODO: 完成 Oracle 的创建 # 执行 Grover # grover = Grover(...) # solution, iterations = grover() print(f"目标状态：{target_state}") # print(f"找到的解：{solution}") # 运行练习 exercise_1_solution()

In [ ]:

# 练习 2 的解答框架
def exercise_2_solution():
    """
    查找偶数校验的状态
    """
    nqubits = 4
    
    # 偶数校验的状态：
    # 0000 (0个1), 0011 (2个1), 0101 (2个1), 0110 (2个1),
    # 1001 (2个1), 1010 (2个1), 1100 (2个1), 1111 (4个1)
    
    n_solutions = 8
    
    # 创建 Oracle
    # TODO: 完成 Oracle 的创建
    
    print(f"搜索空间：{2**nqubits}")
    print(f"解的数量：{n_solutions}")
    print(f"理论迭代次数：{int(np.pi/4 * np.sqrt(2**nqubits / n_solutions))}")

# 运行练习
exercise_2_solution()

# 练习 2 的解答框架 def exercise_2_solution(): """ 查找偶数校验的状态 """ nqubits = 4 # 偶数校验的状态： # 0000 (0个1), 0011 (2个1), 0101 (2个1), 0110 (2个1), # 1001 (2个1), 1010 (2个1), 1100 (2个1), 1111 (4个1) n_solutions = 8 # 创建 Oracle # TODO: 完成 Oracle 的创建 print(f"搜索空间：{2**nqubits}") print(f"解的数量：{n_solutions}") print(f"理论迭代次数：{int(np.pi/4 * np.sqrt(2**nqubits / n_solutions))}") # 运行练习 exercise_2_solution()

总结¶

关键要点¶

1. Grover 算法核心：

   • Oracle 标记目标状态
   • 扩散算子放大目标状态振幅
   • 迭代次数：$O(\sqrt{N/M})$

2. 三种模式：

   • 标准模式：已知解的数量
   • 迭代模式：未知解的数量
   • 自定义叠加态：非均匀搜索空间

3. 应用场景：

   • 数据库搜索
   • NP 完全问题（如 3-SAT）
   • 组合优化问题

4. 性能：

   • 二次加速：$O(\sqrt{N})$ vs $O(N)$
   • 对大问题更显著

下一步学习¶

• 变分量子算法：VQE、QAOA（教程 02-03）
• 量子机器学习：量子分类器（教程 04）
• 绝热演化：绝热量子计算（教程 05）

参考资源¶

• Qibo 官方示例：examples/grover/
• 原论文：arXiv:quant-ph/9605043
• Qibo 文档：https://qibo.readthedocs.io/

---

恭喜！ 你已经掌握了 Grover 搜索算法的基本用法。

继续探索其他量子算法吧！🚀