西蒙算法

西蒙算法是一种量子计算算法，发明的目的是解决一种被称为西蒙问题的人为问题。与其他量子计算算法之一Deutsch-Jozsa算法相比，它只需要运行一次，而Simon的算法需要运行多次，但它仍然能够以指数级的速度解决在量子电路上运行的Simon问题，而不是在经典电路上运行的最好的传统概率算法。

在这篇博客中，我想详细讨论西蒙的问题和西蒙的算法。

其中$\Oplus$是$\text{XOR}$(模2的二进制加法)。这一点很容易用真值表进行验证。

在上一篇博客文章中，我们定义了复向量空间的内积和内积空间。类似地，我们也可以定义二元向量空间的内积和内积空间。

给定两个二元向量$\mathbf{x}，\mathbf{y}\in\{0，1\}^n$，$\mathbf{x}=\{x_0，x_1，\cdots，x_{n-1}\}$和$\mathbf{y}=\{y_0，y_1，\cdots，y_{n-1}$，即$\mathbf{x}的内积。

还为相同长度的二进制向量$\mathbf{x}$和$\mathbf{y}$定义了按位异或操作$\Oplus$。给定两个二元向量$\mathbf{x}，\mathbf{y}\in\{0，1\}^n$，$\mathbf{x}=\{x_0，x_1，\cdots，x_{n-1}\}$和$\mathbf{y}=\{y_0，y_1，\cdots，y_{n-1}\}$，

给定$\mathbf{x}，\mathbf{x}^{\Prime}，\mathbf{y}，\mathbf{y}^{\Prime}\in\{0，1\}^n$，使用我们上面导出的$\text{XOR}$分配性属性，

Hadamard算子的大多数重要性质已经在我上一篇关于Deutsch-Jozsa算法的博客文章的前提条件部分得到了推导。与Deutsch-Jozsa算法不同，Simon的算法只使用Deutsch-Jozsa算法使用的Hadamard算子性质的一小部分。我只会复制对西蒙算法有用的属性。有关Hadamard运算符的推导、证明和其他性质，读者应该参考我上一篇博客文章。

为了从$H^{{n}}$中提取任意列$j$，我们准备了一个单热点量子系统基本态矢量$|\mathbf{y}\rangle=[y_0，y_1，\cdots，y_{2^n-1}]^{\top}$，其中$y_j=1$，$y_k=0$，其中$k\neq j$。

其中$|\mathbf{x}_i\range$是量子系统的一热基本态矢量，$|\mathbf{x}_i\range=[x_0，x_1，\cdots，x_{2^{n}-1}]^{\top}$，其中$x_i=1$，$x_k=0$(对于$k\neq i$)。

具体地说，如果$j=0$，$|\mathbf{y}\Rangle=[\下括号{1，0，0，\cdots，0}_{2^n}]^{\top}=|\mathbf{0}\Rangle$，

西蒙的问题定义如下。给出一个黑盒函数$f：\{0，1\}^n\right tarrow\{0，1\}^n$，我们进一步确信在\{0，1\}^n$中存在一个隐藏的二进制字符串$\mathbf{c}\，使得对于所有$\mathbf{x}，\mathbf{y}\在\{0，1\}^n$中，

映射$f$有一些属性。$f$是一对一或二对一映射。

因为$f$是$\right tarrow$$\mathbf{c}=\mathbf{0}$的一对一映射，证明它太简单了。

对于$\mathbf{c}=\mathbf{0}$$\right tarrow$$f$是一对一映射，我们想用矛盾的方法证明。

如果$\mathbf{c}=\mathbf{0}$和$f$不是一对一映射，则必须存在$\mathbf{x}$和$\mathbf{y}$、$\mathbf{x}\neq\mathbf{y}$和$f(\mathbf{x})=f(\mathbf{y})$。根据保证，$\mathbf{y}=\mathbf{x}\oplus\mathbf{c}=\mathbf{x}\oplus\mathbf{0}=\mathbf{x}$。这增加了矛盾，因此当$\mathbf{c}=\mathbf{0}$时，$f$必须是一对一映射。

因为$f$是二对一映射$\right tarrow$$\mathbf{c}\neq\mathbf{0}$，证明它太简单了。

对于$\mathbf{c}\neq\mathbf{0}$$\right tarrow$$f$是二对一映射，我们想用矛盾的方法来证明。

如果$\mathbf{c}\neq\mathbf{0}$，对于任何$\mathbf{x}$，我们必须有$\mathbf{y}$，其中$\mathbf{y}=\mathbf{x}\oplus\mathbf{c}$和$\mathbf{x}\neq\mathbf{y}$，$f(\mathbf{x})=f(\。所以$f$至少是二对一映射。假设存在$\mathbf{x}$、$\mathbf{y}$和$\mathbf{z}$的元组，其中$\mathbf{y}=\mathbf{x}\oplus\mathbf{c}$、$\mathbf{z}\neq\mathbf{x}$和$\mathbf{z}\neq\mathbf{y}$。根据保证，$\mathbf{z}=\mathbf{x}\oplus\mathbf{c}$。但是$\mathbf{x}\oplus\mathbf{c}=\mathbf{y}$，所以我们有$\mathbf{z}=\mathbf{y}$。这增加了矛盾，因此当$\mathbf{c}\neq\mathbf{0}$时，$f$必须是二对一映射。

如果我们碰巧知道任何$\mathbf{x}$和$\mathbf{y}$，其中$\mathbf{x}\neq\mathbf{y}$和$f(\mathbf{x})=f(\mathbf{y})$，我们立即知道$\mathbf{c}\neq\mathbf{0}$和$\mathbf{c}=\mathbf{x}。这是因为，

如果我们检查了0，1^n$中的所有$\mathbf{x}，\mathbf{y}，发现没有$\mathbf{x}$和$\mathbf{y}$，其中$\mathbf{x}\neq\mathbf{y}$和$f(\mathbf{x})=f(\mathbf{y})$，我们立即知道$\mathbf。

因此，解决Simon问题的普通解决方案是使用$0，1^n$中的值逐个评估$f$，并检查新评估的值是否显示在以前的评估中。

使用散列，我们应该能够检查新评估的值是否已经在前面的评估中显示在$O(1)$中。但是，大部分计算成本来自使用$0，1^n$中的值逐个计算$f$。

如果$\mathbf{c}\neq\mathbf{0}$，如果我们非常幸运，并且前两个评估值$f(\mathbf{x}_0)=f(\mathbf{x}_1)$，那么我们就完成了，$\mathbf{c}=\mathbf{x}_0\oplus\mathbf{x}_1$。但是，在最坏的情况下，我们必须计算$0，1^n$中的$2^{n-1}+1$的值。

如果$\mathbf{c}=\mathbf{0}$，我们将在评估$0，1^n$中的$2^{n-1}+1$值后知道，因为没有两个评估值是相同的。

因此，使用平凡的解决方案，在最坏的情况下，我们必须运行评估$2^{n-1}+1$次来确定$\mathbf{c}$的值。

与我们用于Deutsch算法和Deutsch-Jozsa算法的量子门类似，黑盒$f(\mathbf{x})$使用量子门$U_f$表示。

量子门$U_f$是一个酉矩阵，它从$|\mathbf{x}\Rangle\oTimes|\mathbf{y}\Rangle$映射到$|\mathbf{x}\Rangle\oTimes|f(\mathbf{x})\Oplus\mathbf{y}\rangle$，即$U_f(|\mathbf{x}\Rangle\oTimes|\mathbf{y}。对于$\mathbf{x}\in\{0，1\}^n$和$\mathbf{y}\in\{0，1\}^n$。当$\mathbf{y}=\mathbf{0}$，$|f(\mathbf{x})\oplus\mathbf{y}\rangle=|f(\mathbf{x})\oplus\mathbf{0}\rangle=|f(\mathbf{x})\rangle$，$|\mathbf{y}\oplus f(\mathbf{x})\rangle。

请注意，当$|\mathbf{x}\Rangle$和$|\mathbf{y}\Rangle$重叠时，上述映射不一定有效。

让我们进一步检查一下，是否可以通过叠加和$U_f$来实现更少的运行。

我们有下面的量子马戏团。让我们计算一下马戏团里的每个量子态。与Deutsch-Jozsa算法相比，数学实际上要容易得多。

假设$\mathbf{x}_2=\mathbf{x}_1\oplus\mathbf{c}$，我们还有$\mathbf{x}_1=\mathbf{x}_2\oplus\mathbf{c}$。因为

请注意，$\langle\mathbf{z}，\mathbf{c}\rangle$是一个二进制值。当$\langle\mathbf{z}，\mathbf{c}\rangle=1$，$\sum_{\mathbf{x}\in\{0，1\}^n}\frac{(-1)^{\langle\mathbf{z}，\mathbf{x}\rangle}\Big(1+(-1)^{\langle\mathbf{z}，\mathbf{c}\。我们完全没有观察到$\mathbf{z}$的概率。对于顶部的输出量子比特，我们只能观察到$\mathbf{z}$其$\langle\mathbf{z}，\mathbf{c}\rangle=0$。

统计地，当$\mathbf{c}=0$，$\langle\mathbf{z}，\mathbf{c}\rangle=0$时，对于0，1^2$中的所有$\mathbf{z}\。这意味着所有的$\mathbf{z}$都可以从顶部的输出量子比特中观察到。那么观察到$\mathbf{z}$，$p(\mathbf{z})$的概率是多少？是均匀分布的吗？

现在，假设我们运行马戏团并观察顶部输出的量子比特$k$次，我们观察到$\mathbf{z}_0$，$\mathbf{z}_1$，$\cdots$，$\mathbf{z}_{k-1}$。我们现在知道$\langle\mathbf{z}_i，\mathbf{c}\rangle=0$，对于[0，k-1]$中的$i\。

计算$\mathbf{c}$就像解线性方程一样。让我们看看怎么做。

在传统的线性代数中，要求解具有$n$变量的线性方程，需要有$n$线性无关的线性方程。这也适用于求解二元向量空间中的线性方程。

在我们的特定问题中，$\mathbf{c}$是包含$n$变量的二进制向量，$\{\mathbf{c}_0，\mathbf{c}_1，\cdots，\mathbf{c}_{n-1}\}$，结果是我们需要$n-1$线性无关的$\mathbf{z}_i$使得$\langle\mathbf{z}_i，\mathbf{z}_i。(实际上，当$\mathbf{c}\neq 0$时，至多只能找到$n-1$线性独立的$\mathbf{z}_i$)。

在二元向量空间中线性依赖的上下文中，如果至少一个二元向量可以定义为其他向量的线性组合，则我们说二元向量集是线性相关的。无二进制向量可以这样写，这样二进制向量是线性无关的。

给定二进制向量$\mathbf{z}_0$、$\mathbf{z}_1$、$\cdots$和$\mathbf{z}_{n-1}$，以及布尔值$b_0$、$b_1$、$\cdots$、$b_{n-1}$，我们称$\mathbf{z}_0$、$\mathbf{z}_1$、$\cdots

只有平凡解$b_0=b_1=\cdots=b_{n-1}=0$。否则，$\mathbf{z}_0$、$\mathbf{z}_1$、$\cdots$和$\mathbf{z}_{n-1}$线性相关。

这也表明，要成为线性独立的，$\mathbf{z}_i\neq\mathbf{0}$，对于[1，n-1]$中的$i\。

假设$\mathbf{z}_0$，$\mathbf{z}_1$，$\cdots$和$\mathbf{z}_{n-1}$线性相关，$\langle\mathbf{z}_0，\mathbf{c}\range=0$，$\langle\mathbf{z}_1，\mathbf{c}\。

由于$\mathbf{z}_0$、$\mathbf{z}_1$、$\cdots$和$\mathbf{z}_{n-1}$是线性相关的，所以假设$bi\neq 0$($bi=1$)。

给定$n-1$线性无关的二元向量，让我们进一步了解如何在二元向量空间中解线性方程。该过程类似于求解传统线性方程的高斯消去法。

让我们从一个例子开始，其中$n=3$。$\mathbf{z}_0=\{1，0，1\}$，$\mathbf{z}_1=\{1，1，1\}$。很容易证明$\mathbf{z}_0$，$\mathbf{z}_1$线性无关。因为，$\langle\mathbf{z}_0，\mathbf{c}\rangle=0$，$\langle\mathbf{z}_1，\mathbf{c}\rangle=0$，

我们可以通过$\langle\mathbf{z}_0，\mathbf{c}\rangle\oplus\langle\mathbf{z}_1，\mathbf{c}\rangle$消除$(1\wedge\mathbf{c}_0)$，然后我们有。

我们还可以看到，求解$n-1$线性方程总是导致$\mathbf{c}^{\Prime}=\mathbf{0}$和另一个非零的$\mathbf{c}^{\Prime\Prime}$。

我们如何确定$\mathbf{c}^{\Prime}=\mathbf{0}$或$\mathbf{c}^{\Prime\Prime}$是正确的解决方案？我们运行一次电路以获得$f(\mathbf{0})$和$f(\mathbf{c}^{\Prime\Prime})$的值。如果$f(\mathbf{c}^{\Prime\Prime})=f(\mathbf{0})$，则$\mathbf{c}=\mathbf{c}^{\Prime\Prime}$。如果$f(\mathbf{c}^{\Prime\Prime})\neq f(\mathbf{0})$，则$\mathbf{c}=\mathbf{0}$。

最后一个问题是，在几次运行中观察到$n-1$线性独立的$\mathbf{z}$的概率是多少。

让我们计算在$n-1$运行中观察到$n-1$线性独立的$\mathbf{z}$的概率。

假设$\mathbf{c}\neq 0$。对于第一次$t=0$我们“抽出”$\mathbf{z}$，我们必须避免$\mathbf{z}_{t=0}\neq\mathbf{0}$，这样的概率是$1-\frac{1}{2^{n-1}}$。一旦画出$\mathbf{z}_{t=0}$，在$t=1$处，我们可以画出$\mathbf{z}_{t=1}$，而不是$\mathbf{z}_{t=0}$和$\mathbf{0}$，这样的概率是$1-\frac{1}{2^{n-2}}$；$\mathbf{z}_{t=0}$和$\mathbf{z}_{t=1}$构成一个由$2^2=4$向量组成的子空间，如果我们从这个子空间中画出$\mathbf{z}_{t=2}$，我们就会有线性依赖关系。所以在$t=2$时，我们必须避免这些$2^2=4$矢量，这样的概率是$1-\frac{1}{2^{n-3}}$。我们反复进行，直到我们绘制了$n-1$$\mathbf{z}$。在$n-1$运行中观察到$n-1$线性独立$\mathbf{z}$的概率为。

我们注意到$(1-a)(1-b)\geq1-(a+b)$对应于[0，1]$中的$a，b\。

因此，Simon的算法成功的概率至少为$\frac{1}{4}$。我们可以通过多次重复这个过程来提高成功的概率。

西蒙的问题和算法是量子力学和统计学的结合。从这里，我们开始看看量子计算是如何开始解决遵循一些统计规则的问题的。