20、量子计算高级算法：从搜索到因式分解

量子计算高级算法：从搜索到因式分解

1. Simon 算法相关

1.1 Simon 预言机构建规则

构建 Simon 预言机时，需遵循以下两条关键规则：
1. 将第一个寄存器的状态复制到第二个寄存器，即对第一个寄存器的所有量子比特应用 CX 门到第二个寄存器的对应量子比特。
2. 找到字符串s中第一个 1 的索引i，然后从i到第二个寄存器中每个 1 出现的索引应用 n - CX 门，其中 n 是字符串中 1 的数量。这等价于当 qubit(i) == 1 时，|x⟩ → |s.x⟩。

从这些规则可知，CX 门的总数等于字符串中的量子比特数加上 1 的数量。

1.2 Simon 预言机示例

以下是一个 3 比特字符串的 Simon 预言机示例：
| 输入比特串 | 预言机操作 |
| ---- | ---- |
| 000 | 无 |
| 001 | CX(0,0) |
| 111 | CX(1,1)CX(1,2)CX(1,3) |

1.3 代码实现 Simon 预言机

# n - qubit 版本的 Simon 预言机 def oracle (s): # 为了适应 Qiskit 的量子比特排序，反转字符串 s = s[::-1] n = len(s) qc = QuantumCircuit(n * 2) # 如果字符串全