在上一篇文章中，Bernstein-Vazirani算法向我们展示了查询模型中查找秘密字符串的线性加速。

在本文中，我们将讨论Simon算法，该算法为我们提供了查询模型中的指数级加速，以查找函数中的模式。

设置：

在 Simon 的问题中，我们得到了一个从 n 位字符串到 n 位字符串的函数，并且还给出了如下图 1 所示的承诺。

图1：Simon的条件

这里$a$ 是一个秘密字符串，$\oplus$ 表示模 2 的按位加法。换句话说，$f$ 的值以某种模式重复，并且模式由$a$ 确定。 我们称$a$ 的周期为$f$ 。Simon算法的目标是确定$a$ ，如果$f$ 是二比一。我们通过下面的示例对此进行讨论。

示例：让我们考虑$n=3$ ，$a=101$ 。那么我们对$f$ 的要求如下图2所示：

图2：示例

从上面的示例中，请注意，如果$a=\left(n\cdot 0\right)$ ，如下图 3 所示，则该函数是一对一的。否则，该函数是二对一的(这意味着两个输入产生相同的输出)。

图3：位字符串n乘以0

经典解决方案：

考虑如下图 4 所示的函数，秘密字符串$a=110$ 由值表定义，如下图 5 所示。

图 4：$n=3$ 的函数

图 5：值表

上面提到的表格如图5所示，遵循了上述图1中提到的 Simon 属性。

假设我们首先发送输入$x1=010$ ，然后发送输入$x2=100$ 。从表中可以看出，两个输入产生相同的输出。

我们可以从图1和图5验证秘密字符串$a$ 满足$a=x1\oplus x2$ ($x1,x2$ 是匹配的输入)。我们可以把$x1=x2\oplus a$ 写成$x1\oplus x2=x2\oplus a\oplus$ ，这就得到了一个秘密字符串$a\left(x2\oplus x2=0,a\oplus 0=a\right)$ 。

不难看出，这种情况总是成立的，即；如果输入$x$ 和$y$  ，我们总是可以通过找到“碰撞对”或“匹配对”来找到$a$ 。

我们现在知道，我们可以通过解决Simon的问题，通过找到碰撞对来计算。现在的问题是需要多少次查询才能找到碰撞对？

图6：Simon的经典解决方案

我们可以做的一件事就是查询函数$f$ 的每个值。然后我们可以查看并确定找到匹配的对。

这需要多少次查询?

$f$ 是长度为$n$ 的位字符串上的函数，这样的位串总共有2个幂$n（2^n）$ 这样的位字符串。因此，我们可以经典地以最多2次幂$n（2^n）$ 次查询求解Simon问题，如图6所示。

我们能做得比这更好吗？

是的，有一个量子算法可以解决$O（n）$ 查询，这是一个指数级的改进！

证明就是Simon算法。我们将核实此声明。

Simon算法：

从图1开始，我们有两个输入$x和y$ ，它们的整数为$0,1$ ，重复$n$ 次，如下图7所示

图7:函数$f$ 的幺正运算

当$|x,y⟩$ 变为$|x,y\oplus f(x)⟩$ 时，$Uf$ 再次是其自身的逆。

在这里，如果我们设置$|y⟩=|0⟩$ ，那么$|y\oplus f(x)⟩$ 将变成$|f(x)⟩$ ，这为我们提供了评估$f(x)$ 的简单方法。因此，第二个寄存器的输入应该是$|0⟩$ ，连续$n$ 次，不应用叠加。

注意：这里我们没有根据 Simon 算法考虑相位回扣，我们使用的是 Born 规则。

综合以上考虑，电路如下图 8 所示

图8：Simon的电路

从上图8中，我们看到了一个熟悉的模式。有两个多维寄存器，上面的(我们认为是A寄存器或数据寄存器)和下面的(我们认为是B寄存器或目标寄存器)。

这与我们最近的算法电路几乎相同，但有以下变化：

• 目标通道是“阴影线”，反映它有$n$ 条分量线而不是一条。
• 我们将如图8所示，将“$n$ 个量子位$|0⟩$ ”发送到目标寄存器，而不是$|1⟩$ 。
• 我们似乎在测量两个输出寄存器，而不是忽略目标。

电路中的数据寄存器在逻辑和意图上都与 Deutsch-Jozsa 和 Bernstein-Vazirani 电路相同。它通过产生完美混合的纠缠态来建立量子并行性，使预言机能够同时对所有可能的$x$ 作用于$f(x)$ 。

分析：

图 9：Simon 的分析电路

我们讨论波形在特定区间的行为，如上图 9 所示。

将$n$ 个量子位$|0⟩$ 发送到两个寄存器，即图9所示的数据寄存器和目标寄存器，以及$|\psi 0⟩$ 表示如下图10所示。

图10：两个寄存器的输入

我们可以看到这个 Hadamard 算子的输出状态是$n$ 阶$x$ 基。它提醒我们，Hadamard 门不仅提供量子并行性，而且还兼作 $Z\leftrightarrow X$ 基转换算子。

图 11：应用$n$ 个量子位的Hadamard。

在设置$|y⟩=|0⟩$ 并通过Oracle，$Uf$ 将输入变为$|y\oplus f(x)⟩$ 到$|f(x)⟩$ 后，如下图12所示。

图 12：应用 Oracle 函数$f$ 之后

在状态$|\psi 3⟩$ 上，测量第二个寄存器。可以观察到$f(x)$ 的某个值。由于问题的设置如图1所示，观察值$f(x)$ 可能对应两种可能的输入:$x和y=x\oplus a$ 。因此，第一个寄存器变为如下图13所示。

注：Register A和 Register B通勤测量。因此，测量顺序无关紧要。

我们省略了第二个寄存器，因为它已经被测量过了。

继续假设我们在$B$ 寄存器输出测量$f(x)$ 的一个值，从而折叠两个寄存器，在A寄存器中，我们继续处理得到的叠加$|\psi 3⟩$ 。当我们将 Hadamard 门应用到它时，让我们跟踪它的进度，如下图 14 所示。

图 14：应用n量子比特Hadamard

Hadamard 对个别项和简化表达式如下图 15 所示。

图 15：个别条款的 Hadamard

将这些简化的表达式保留到$|\psi 4⟩$ ，如下图 16 所示。

图 16：更新$|\psi 4⟩$ 表达式

括号中的表达式如下图 17 所示。

图17:求表达式的值

所以我们可以省略所有对应于$z\cdot a=1\left(\mathrm{mod}2\right)$ 的 0 项，留下$|\psi 4⟩$ ，如下图 18 所示。

图18:省略 0 个项

请注意，在省略零项后，总和现在仅超过原始$2^n$ 的$2^{n-1}$ 或恰好一半。

首次运行分析：

有了得到的条件$z\cdot a=0\left(\mathrm{mod}2\right)$ ，我们可以说最终$A$ 寄存器叠加中的所有向量都与$a$ 正交（因为点积为零）。所以我们现在可以测量混合状态并获得一些信息。

我们不知道我们将测量$2^{n-1}$ 个z 中的哪个$z$,这取决于坍缩，而且它们的可能性都相同。但是，我们只是表明它们都与$a$ 正交。

在电路“ $O\left(1\right)$ ”的单个应用中，我们找到了第一个$z$ ，其中$z\perp a$ 。我们希望找到$n-1$ 个这样的向量，它们作为一个集合都是线性独立的，因此我们预计对电路进行多次采样。

生成“$n-1$ ”线性独立向量：

我们展示的是，我们可以在电路的单个应用中找到与$a$ 正交的向量。然而，我们需要找到的不是一个，而是$n-1$ 个与$a$ 正交的线性无关向量$z$ 。

重复这个过程$n-1$ 次以解决问题吗？

这样做肯定会制造如下图19所示。

图 19：$n-1$ 项

但是，这还不够好。其中一些$Zk$ 可能是其他的线性组合，甚至是重复的。为此，我们需要每个人不仅与$a$ 正交，而且线性地独立于所有其他。这可以通过高斯消除来实现。

高斯消除和反向替换：

方便的是，剩下的两个经典任务都通过线性代数中一种古老且有据可查的技术来解决，该技术用于求解线性方程组，称为“具有反向替换的高斯消除”。考虑一个线性方程组，如下面的示例1所示。

示例 1：方程组

上述线性方程组用其常系数矩阵表示，如下例 1.1 所示。

例 1.1：上述线性方程的矩阵表示

没有要求系统应具有与未知数相同数量的方程;方程越少，你对解的了解就越少。

高斯消元法，它在左下三角形中产生一个 0 的矩阵，

在增强形式中，示例 1.1 变为如下示例 1.2 所示

示例 1.2：增强形式

行梯形，其中“对角线”以下的所有内容均为 0，如下例 1.3 所示。

示例 1.3：行梯形

简化的行梯形形式，即梯形形式，附加要求每行中的第一个非零元素为 1，如下例 1.4 所示。

示例 1.4：简化的行梯形

恢复变换后的矩阵方程，如下例 1.5 所示。

示例 1.5：恢复变换后的矩阵方程

可以立即求解，得到$z=-4/5$

反向替换，它使用该矩阵尽可能地求解方程组，这意味着如果没有足够的方程，我们可能只会得到未知数之间的关系，而不是唯一数。

反向代入得到$y=4$ （在本例中实际上很简单），然后再次反向代入$x+y+z=3$ 以找到$x=-1/5$

经典部分：

将集合$W$ 初始化为空集合。$W$ 最终将包含一个不断增长的向量。使用经典算法（高斯消除和反向替换）来确定$z$ 是否线性依赖于$W$ 中的向量。如果它是独立的，则将特定的$z$ 添加到$W$ 。这会求解$a$ 的$n$ 个方程组。

经典$O\left(n^2\right)+$ 量子$O\left(n\right)=O\left(n^3\right)$

实现Simon算法：

我们将使用 cirq 和 qiskit为函数$f(x)$ 生成一个 Oracle( Uf ) ，它的周期是$a$ 。使用 cirq 将定义高斯消除和反向替换，其中使用 qiskit 计算方程组。

使用 Cirq 实现 Simon 算法：

导入所需的模块，如下 cirq1 所示。

cirq1：导入模块

如下面的 cirq2 所示，为 Simon 算法生成初始条件和测量条件。

cirq2：生成初始条件和测量条件

如下面的 cirq 3 所示，为给定函数生成 Oracle。

cirq3：为给定函数生成oracle

如下面的cirq4所示，为给定函数生成Simon电路。

cirq4：为给定函数生成Simon电路

如下 cirq5 所示，该函数执行上述理论部分中讨论的后处理。

cirq5：后处理

如下图cirq6所示，初始化电路，量子比特数，生成Simon电路。

cirq6：生成西蒙电路

可视化为给定函数生成的电路，如下 cirq7 所示。

cirq7：为给定函数生成的电路

结论：随机生成的秘密位字符串  101 与模拟器值 101 匹配的概率为 100%，如上所示。

使用 qiskit 实现Simon算法：

如下 qiskit1 所示，为 Simon 算法生成初始条件和测量条件。

qiskit1：生成初始条件和测量条件

如下 qiskit2 所示，为给定函数生成 Oracle。

qiskit2：为给定函数生成预言机

如下 qiskit3 所示，为给定函数生成Simon 电路。

qiskit3：生成Simon电路

如下 qiskit4 所示，初始化电路，量子比特数，生成 Simon 电路并可视化生成的电路。

qiskit4：没有量子位、寄存器和可视化电路

为给定函数生成的电路，如下图 qiskit5 所示

qiskit5：生成的电路

如下图 qiskit6 所示，使用模拟器进行测量。

qiskit6：使用模拟器进行测量

电路在模拟器上运行后，下面是获得结果的直方图

qiskit7：a = 110 的上述问题的结果

由于我们已经知道$a$ ，我们可以验证这些结果确实满足$a\cdot z=0\left(\mathrm{mod}2\right)$ ，如下 qiskit8 所示。

qiskit8: $a\cdot z=0\left(\mathrm{mod}2\right)$

使用这些结果，我们可以通过求解这组联立方程来恢复$a=110$ 的值。

例如，假设我们首先测量 001，这告诉我们：

如果我们接下来测量 111，我们有

这告诉我们

其中$a=110$ 是我们联立方程的非平凡解。

原文链接：https://anonymousket.medium.com/quantum-algo-simon-algorithm-82b9c8964673

---煤油灯科技victorlamp.com翻译整理---