量易简

西蒙算法

背景介绍

由上一节可知，在判定一个黑盒计算的是常数函数还是平衡函数时，经典确定性算法需要调用 $O (2^{n})$ 次（ $n$ 是函数输入比特串长度）黑盒，而多伊奇-约萨算法只需要调用 $1$ 次相应的量子黑盒，因此该量子算法相对于最好的经典确定性算法有着指数级加速。但是，存在经典概率算法只需要调用 $2$ 次黑盒就能以不小于 $2 / 3$ 的概率成功判定该黑盒计算的是常数函数还是平衡函数。因此从概率算法的角度来看，多伊奇-约萨算法相对于最好的经典概率算法并没有指数级加速。

本节将要介绍的西蒙算法是由西蒙（Daniel Simon）在1994年提出的量子算法 $^{[1]}$ 。西蒙算法是一个量子概率算法，它相对于最好的经典概率算法有指数级加速。更重要的是，西蒙算法直接启发了著名的秀尔算法（详见第四章）。

问题描述

以下我们形式化描述西蒙算法解决的问题。

给定一个黑盒（Oracle） $O$ ，它计算函数 $f : {0, 1}^{n} \to {0, 1}^{n}$ 。 $f$ 满足以下性质：存在长度为 $n$ 的非零比特串 $s \in {0, 1}^{n}$ （我们称 $s$ 为函数 $f$ 的隐藏比特串）使得
$\begin{matrix} \forall x, y \in {0, 1}^{n}, f (x) = f (y) 当且仅当 x \oplus y = s, \\ (1) \end{matrix}$
其中 $\oplus$ 是按位异或运算。用 $x \in {0, 1}^{n}$ 作为输入调用 $O$ ，黑盒的输出为 $f (x)$ 。算法的任务是通过调用 $O$ 来计算比特串 $s$ 。算法的复杂度定义为调用 $O$ 的次数。

深入分析 $f$ 的性质，我们发现给定 $x \in {0, 1}^{n}$ ，有且仅有一个 $y \in {0, 1}^{n}$ 满足 $x \oplus y = s$ ，因此 $f$ 的作用是恰好将两个不同的输入映射为同一个输出，属于二对一函数。 $f$ 输入比特串的总数为 $2^{n}$ ，输出比特串的总数为 $2^{n - 1}$ 。

注：令 $0^{n}$ 表示长度为 $n$ 的全 $0$ 比特串。在上面的问题描述中，我们假设隐藏比特串 $s \neq 0^{n}$ ，此时 $f$ 是二对一函数。如果 $s = 0^{n}$ ，对应的 $f$ 是一对一函数，即 $f (x) = f (y)$ 当且仅当 $x = y$ 。不过接下来介绍的西蒙算法也可以用来解决 $s = 0^{n}$ 的情况。

例 1. 考虑如下表 1 定义的函数 $g : {0, 1}^{3} \to {0, 1}^{3}$ ：

$x$	$g (x)$
$000$	$000$
$001$	$001$
$010$	$010$
$011$	$011$
$100$	$000$
$101$	$001$
$110$	$010$
$111$	$011$

表 1 : 函 数 g 的 真 值 表 。

易见 $g (000) = g (100), g (001) = g (101), g (010) = g (110), g (011) = g (111)$ ，即 $g$ 是一个二对一函数。通过分析可知函数 $g$ 对应的隐藏比特串为 $s = 100$ 。

经典算法

在这一节，我们分析使用经典计算机完成该判定任务需要调用 $O$ 的次数 $^{[2]}$ 。

假设经典概率算法 $A$ 用于计算隐藏比特串 $s$ 。 $A$ 已经使用 $k$ 个输入 $x^{(1)}, \dots, x^{(k)}$ 对黑盒 $O$ 共进行 $k$ 次调用，并得到 $k$ 个输入输出对 $(x^{(1)}, f (x^{(1)})), \dots, (x^{(k)}, f (x^{(k)}))$ 。我们分析利用这些数据能够获得多少关于隐藏比特串 $s$ 信息。注意， $s$ 取值空间的大小为 $2^{n} - 1$ （即 $s$ 所有取值的集合的大小，我们这里不考虑 $s = 0^{n}$ 的情况）。

最好情况下，存在两个输入 $x^{(i)}$ 和 $x^{(j)}$ ， $1 \leq i \neq j \leq k$ ，使得 $f (x^{(i)}) = f (x^{(j)})$ 。此时，我们可以直接计算 $s$ 的值： $s = x^{(i)} \oplus x^{(j)}$ 。

最坏情况下，所有 $k$ 个输出值都不相同，我们可以断言对任意的 $1 \leq i \neq j \leq k$ ， $s \neq x^{(i)} \oplus x^{(j)}$ 。此时，我们最多可以排除 $(\frac{k}{2})$ 个 $s$ 可能的取值，这里 $(\frac{k}{2})$ 是组合数记号，常用记号还有 $C_{k}^{2}$ 。即 $k$ 个都不相同的输出最多能将 $s$ 取值空间的大小减小为

\begin{matrix} 2^{n} - 1 - (\frac{k}{2}) . \\ (2) \end{matrix}

算法 $A$ 用新输入 $x^{(k + 1)}$ 再次调用黑盒 $O$ 并得到输出 $f (x^{(k + 1)})$ 。该调用结果可以用来计算 $s$ 当且仅当 $f (x^{(k + 1)})$ 和前 $k$ 个输出结果中的某一个相同（根据假设，其最多只能和其中一个相同），即存在 $1 \leq i \leq k$ 使得 $f (x^{(i)}) = f (x^{(k + 1)})$ 。该事件等价于从 $s$ 的取值空间随机选取 $k$ 个值，因而其成功概率不大于

\begin{matrix} \frac{k}{2^{n} - 1 - (\frac{k}{2})} . \\ (3) \end{matrix}

这里需要强调的是，也有可能 $f (x^{(k + 1)})$ 和前 $k$ 个输出结果均不相同，此时我们仍然无法计算 $s$ 。所以第 $k + 1$ 轮结束后能够成功计算出 $s$ 的概率肯定不超过公式 $(3)$ 。以此类推，在最坏情况下 $K$ 个输出结果可以计算 $s$ 的概率满足

\begin{matrix} p (K 个输出结果可以计算 s 的概率) \leq K \sum k = 2 \frac{k}{2^{n} - 1 - (\frac{k}{2})} \leq K \sum k = 2 \frac{k}{2^{n} - k^{2}} \leq \frac{K^{2}}{2^{n} - K^{2}} . \\ (4) \end{matrix}

从上面的表达式可以看出，如果 $K$ 是 $n$ 的多项式函数，则能够计算 $s$ 的概率是指数小的，即 $p = O (1 / 2^{n})$ 。换言之，只有当 $K$ 满足 $Ω (2^{n / 2})$ 时，能够计算 $s$ 的概率才可能是个常数，即 $p = O (1)$ 。因此，任意经典概率算法都至少需要 $n$ 的指数次调用才能以常数概率获得正确结果。

西蒙算法

在这一节，我们介绍西蒙算法。该算法只需要调用黑盒 $O (n)$ 次就能以和经典算法相同的概率判断出 $O$ 所计算的函数的性质，因此相对经典算法有指数级加速。

这里我们首先回顾一下量子黑盒的形式，然后利用该量子门给出西蒙算法的量子电路，最后逐步分析该量子电路的演化和经典数据后处理过程，证明算法的正确性。

量子黑盒

在西蒙算法中，用到的量子黑盒如下图所示：

数学上，量子门 $U_{f}$ 的定义为：

\begin{matrix} \forall x, y \in {0, 1}^{n}, U_{f} (| x ⟩ \otimes | y ⟩) = | x ⟩ \otimes | y \oplus f (x) ⟩, \\ (5) \end{matrix}

由于此量子黑盒与本章第二节 Bernstein-Vazirani 算法中介绍的一致，此处我们不再过多赘述。

算法流程与算法分析

基于量子门 $U_{f}$ ，西蒙算法的量子电路可以表示为：

以下我们按照量子电路从左至右逐步分析系统状态的演化过程。

步骤1：初始化系统量子态。 将主寄存器和辅助寄存器都初始化为 $| 0 ⟩^{\otimes n}$ 。此时整个系统（主寄存器和辅助寄存器所构成的复合系统）所处的状态为

\begin{matrix} | ψ_{0} ⟩ = | 0 ⟩^{\otimes n} \otimes | 0 ⟩^{\otimes n} . \\ (6) \end{matrix}

步骤2：均匀叠加。 对主寄存器的所有量子比特分别作用 $H$ 门，作用后的系统状态为：

\begin{matrix} | ψ_{1} ⟩ = (H^{\otimes n} \otimes I_{n}) | ψ_{0} ⟩ = H^{\otimes n} | 0 ⟩^{\otimes n} \otimes | 0 ⟩^{\otimes n} = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 | x ⟩ \otimes | 0 ⟩^{\otimes n} . \\ (7) \end{matrix}

步骤3：作用量子黑盒。 将 $U_{f}$ 作用到 $| ψ_{1} ⟩$ ，作用后的系统状态为：

\begin{matrix} | ψ_{2} ⟩ = U_{f} | ψ_{1} ⟩ = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 U_{f} (| x ⟩ \otimes | 0 ⟩^{\otimes n}) = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 | x ⟩ \otimes | f (x) ⟩ . \\ (8) \end{matrix}

步骤4：对主寄存器的所有量子比特分别作用 $H$ 门。 作用后的系统状态为：

\begin{matrix} | ψ_{3} ⟩ & = (H^{\otimes n} \otimes I_{n}) | ψ_{2} ⟩ = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 H^{\otimes n} | x ⟩ \otimes | f (x) ⟩ = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 (\frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum y = 0 (- 1)^{x \cdot y} | y ⟩) \otimes | f (x) ⟩, \\ (9) \end{matrix}

其中 $x \cdot y$ 是点积运算，定义为 $x \cdot y = \oplus_{k = 0}^{n - 1} x_{k} y_{k}$ ， $x_{k}$ 表示比特串 $x$ 第 $k$ 个比特。在最后一步使用了量子计算中一个常用的技巧：

\begin{matrix} H^{\otimes n} | x ⟩ = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum y = 0 (- 1)^{x \cdot y} | y ⟩ . \\ (10) \end{matrix}

步骤5：主寄存器的所有量子比特分别执行计算基测量。 注意到

\begin{matrix} | ψ_{3} ⟩ & = \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 (\frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum y = 0 (- 1)^{x \cdot y} | y ⟩) \otimes | f (x) ⟩ = 2^{n} - 1 \sum y = 0 | y ⟩ \otimes (\frac{1}{2^{n}} 2^{n} - 1 \sum x = 0 (- 1)^{x \cdot y} | f (x) ⟩), \\ (11) \end{matrix}

所以测量之后主寄存器的测量结果是比特串 $y$ 的概率为

\begin{matrix} p (y) = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} 2^{n} - 1 \sum x = 0 (- 1)^{x \cdot y} | f (x) ⟩ ∣ ∣ ∣ ∣}^{2}, \\ (12) \end{matrix}

其中 $| c |$ 表示复数 $c$ 的模。令 $R$ 表示函数 $f$ 的值域，即 $f$ 输出比特串的集合。由函数 $f$ 定义可知 $| R | = 2^{n - 1}$ ，对任意的 $z \in R$ ，有且仅有两个不同的 $x_{z} \neq x_{z}^{'} \in {0, 1}^{n}$ 使得

\begin{matrix} f (x_{z}) = f (x_{z}^{'}) = z, \\ (13) \end{matrix}

并且它们满足关系式 $x_{z} \oplus x_{z}^{'} = s$ 。将关系 (13) 代入到等式 (12)，我们可得

\begin{matrix} p (y) & = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} 2^{n} - 1 \sum x = 0 (- 1)^{x \cdot y} | f (x) ⟩ ∣ ∣ ∣ ∣}^{2} = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} \sum z \in R ((- 1)^{x_{z} \cdot y} \oplus (- 1)^{x_{z}^{'} \cdot y}) | z ⟩ ∣ ∣ ∣ ∣}^{2} = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} \sum z \in R ((- 1)^{x_{z} \cdot y} \oplus (- 1)^{(x_{z} \oplus s) \cdot y}) | z ⟩ ∣ ∣ ∣ ∣}^{2} = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} \sum z \in R (- 1)^{x_{z} \cdot y} (1 \oplus (- 1)^{s \cdot y}) | z ⟩ ∣ ∣ ∣ ∣}^{2} = {\begin{matrix} \frac{1}{2^{n - 1}}, & 如果 s \cdot y = 0 0, & 如果 s \cdot y = 1 \end{matrix} \\ (14) \end{matrix}

其中推导的第四步利用了分配律 $(x_{z} \oplus s) \cdot y = (x_{z} \cdot y) \oplus (s \cdot y)$ 。以下给出当 $s \cdot y = 0$ 时， $p (y) = 1 / 2^{n - 1}$ 的详细推导过程：

\begin{matrix} p (y) & = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} \sum z \in R (- 1)^{x_{z} \cdot y} (1 \oplus (- 1)^{s \cdot y}) | z ⟩ ∣ ∣ ∣ ∣}^{2} = {∣ ∣ ∣ ∣ \frac{1}{2^{n - 1}} \sum z \in R (- 1)^{x_{z} \cdot y} | z ⟩ ∣ ∣ ∣ ∣}^{2} = \frac{1}{2^{2 (n - 1)}} \sum z, z^{'} \in R (- 1)^{x_{z} \cdot y \oplus x_{z^{'}} \cdot y} ⟨ z^{'} | z ⟩ = \frac{1}{2^{2 (n - 1)}} \sum z \in R ⟨ z | z ⟩ = \frac{1}{2^{n - 1}}, \\ (15) \end{matrix}

其中第二步利用 $s \cdot y = 0$ ，第四步利用 ${| z ⟩}_{z \in R}$ 是一组标准正交基，最后一步利用 $| R | = 2^{n - 1}$ 。记集合

\begin{matrix} B = {y | y \in {0, 1}^{n}, s \cdot y = 0}, \\ (16) \end{matrix}

即 $B$ 是所有满足 $s \cdot y = 0$ 的 $n$ 比特串的集合。易见 $| B | = 2^{n - 1}$ 。公式 $(15)$ 表明，量子电路测量结果比特串 $y$ 等价于从集合 $B$ 中均匀随机采样得到。

经典数据后处理与复杂度分析

运行西蒙算法的量子电路一次得到一个比特串输出 $y$ ，其满足 $s \cdot y = 0$ 。但是这个信息不足以让我们直接计算隐藏比特串 $s$ 。我们需要更多满足 $s \cdot y = 0$ 的不同比特串来计算 $s$ 。那么运行量子电路多少次才能计算 $s$ 呢？假设我们运行量子电路 $n - 1$ 次，得到 $n - 1$ 个比特串输出 $y^{(1)}, \dots, y^{(n - 1)}$ ，它们可以等价理解为从集合 $B$ 独立随机采样得到，且满足条件

\begin{matrix} y^{(1)} \cdot s & = 0, y^{(2)} \cdot s & = 0, ⋮ y^{(n - 1)} \cdot s & = 0. \\ (17) \end{matrix}

我们可以使用高斯消元法求解这个方程组从而得到 $s$ 。由线性代数的知识可知，如果这 $n - 1$ 个比特串 $y^{(1)}, \dots, y^{(n - 1)}$ 线性无关（Linearly Independent），那么 $s$ 的解唯一。从而问题变成随机得到的 $n - 1$ 个比特串 $y^{(1)}, \dots, y^{(n - 1)}$ 满足线性无关的概率是多少？

假设我们已经运行量子电路 $k$ 次并且得到 $k$ 个线性无关比特串 $y^{(1)}, \dots, y^{(k)}$ 。我们再运行量子电路得到第 $k + 1$ 个比特串 $y^{(k + 1)}$ ，这个比特串和之前 $k$ 比特串线性无关的概率为 $(2^{n} - 2^{k}) / 2^{n} = 1 - 1 / 2^{n - k}$ 。因此运行量子电路 $n - 1$ 次并且得到 $n - 1$ 个线性无关比特串的概率满足

\begin{matrix} p (y^{(1)}, \dots, y^{(k)} 线性无关) & = (1 - \frac{1}{2^{n - 1}}) (1 - \frac{1}{2^{n - 2}}) \dots (1 - \frac{1}{2}) = n - 1 \prod k = 1 (1 - \frac{1}{2^{k}}) \geq \infty \prod k = 1 (1 - \frac{1}{2^{k}}) \approx 0.28879 \geq \frac{1}{4} . \\ (18) \end{matrix}

在附录中的习题 1里，我们使用一种更简单的方法证明 $1 / 4$ 是概率下界。这意味着，如果我们运行西蒙算法的量子电路 $n$ 次，得到的比特串输出是线性无关的概率大于等于 $1 / 4$ 。一旦我们得到了一组线性无关比特串集合，我们求解方程组 (17) 即可得到隐藏比特串 $s$ 。

我们重复上面的量子电路和数据后处理过程 $4 m$ 次。因为 $(3 / 4)^{4} \leq 1 / e$ ，其中 $e$ 是自然常数，则至少有一次过程输出结果是一组线性无关比特串集合的概率不小于

\begin{matrix} 1 - {(1 - \frac{1}{4})}^{4 m} \geq 1 - e^{- m} . \\ (19) \end{matrix}

我们可以发现成功概率随着 $m$ 的值增大快速收敛到极限值 $1$ 。比如说当 $m = 10$ 的时候，成功概率大于 $0.9999$ 。

算法总结

需要的硬件设备：
- $2 n$ 个量子比特。
- Hadamard 门。
- 量子黑盒 $U_{f}$ 。
- 计算基测量。
- 经典计算机。
输入： 量子黑盒 $U_{f}$ ，功能是 $U_{f} | x ⟩ | y ⟩ = | x ⟩ | y \oplus f (x) ⟩$ ，其中函数 $f$ 如公式 $(1)$ 定义。
输出： $f$ 的隐藏比特串 $s$ 。
运行代价： 复杂度 $O (n)$ ，成功概率 $O (1)$ 。
运行过程：
1. 重复以下运行过程 $O (n)$ 次：
  
  1.1. 所有量子比特均初始化为 $| 0 ⟩$ 。
  
  1.2. 均匀叠加，对主寄存器的每个量子比特作用 $H$ 门得到
  $\begin{matrix} \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 | x ⟩ \otimes | 0 ⟩^{\otimes n} . \\ (20) \end{matrix}$
  1.3. 作用量子黑盒 $U_{f}$ 得到
  $\begin{matrix} \frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 | x ⟩ \otimes | f (x) ⟩ . \\ (21) \end{matrix}$
  1.4. 主寄存器的每个量子比特作用 $H$ 门得到
  $\begin{matrix} 2^{n} - 1 \sum y = 0 | y ⟩ \otimes (\frac{1}{2^{n}} 2^{n} - 1 \sum x = 0 (- 1)^{x \cdot y} | f (x) ⟩) . \\ (22) \end{matrix}$
  1.5. 测量主寄存器得到测量结果比特串 $y$ 。
2. 从第一步得到的 $O (n)$ 个比特串构造方程组，使用高斯消元法求解该方程组得到 $s$ 。

简例与量易伏平台演示

在这一节，我们在量易伏平台上实现西蒙算法。作为例子，我们先构造在问题描述部分表 1 中给出的函数 $g$ 对应的量子黑盒 $U_{g}$ ，然后使用西蒙算法来计算这个黑盒对应的函数的隐藏比特串。

QComposer 电路

约定 $x = x_{0} x_{1} x_{2}$ ， $x_{k}$ 表示 $x$ 的第 $k$ 个比特。分析函数 $g$ 的性质可知（此时隐藏比特串为 $s = 100$ ），

\begin{matrix} y \oplus g (x) = (y_{0} \oplus 1) (y_{1} \oplus x_{1}) (y_{2} \oplus x_{2}), \\ (23) \end{matrix}

因此 $g$ 对应的量子黑盒 $U_{g}$ 可如下构造：

此时西蒙算法对应在 QComposer 上的电路如下图 4：

量易伏 QComposer 西蒙算法电路 — 图 4：量易伏上 QComposer 对西蒙算法的电路

对应 OPENQASM 代码如下：

OPENQASM 2.0;
include "qelib1.inc";
// 初始化系统量子态
qreg q[6];
creg c[6];
// 主寄存器的所有量子比特分别作用 H 门
//
h q[0];
h q[1];
h q[2];
// 作用量子黑盒 U_f
// 
cx q[1], q[4];
cx q[2], q[5];
// 主寄存器的所有量子比特分别作用 H 门
// 
h q[0];
h q[1];
h q[2];
// 主寄存器的所有量子比特分别执行计算基测量
//
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];

复制

理想模拟器输出结果为：

{
    "100": 245,
    "110": 255,
    "000": 255,
    "010": 269
}

复制

可解得只有 100 与上述结果（翻转后的）内积均为 0，故得到 100 即为隐藏比特串（注意，量易伏默认从最后一位开始测量，因此输出需要反向）。

QCompute 程序

下面是用来实现西蒙算法的代码，此处我们检验每一次测量结果与隐藏比特串 100 的内积，如果算法成立则每一次测量结果与 100 内积都应为 0。

"""
本脚本用于演示西蒙算法，目标函数 g 的真值表为
        |  x  |  g(x) |
        ---------------
        | 000 |  000  |
        | 001 |  001  |
        | 010 |  010  |
        | 011 |  011  |
        | 100 |  000  |
        | 101 |  001  |
        | 110 |  010  |
        | 111 |  011  |
对应的隐藏比特串 s = 100

我们主要是验证西蒙量子电路的测量结果，即测量结果比特串与 s 的点积为 0
参考资料：https://qlearn.baidu.com/chapter3/simon.html
"""
from QCompute import *
import numpy as np

# 不直接给出输出，后续通过print给出需要信息
from QCompute import Define
Define.Settings.drawCircuitControl = []
Define.Settings.outputInfo = False

# 隐藏比特串
s = '100'


def oracle_g(master, ancilla):
    """
    构造函数 g 对应的量子黑盒。

    :param master: n 量子比特主寄存器
    :param ancilla: n 量子比特辅助寄存器
    """
    CX(master[1], ancilla[1])
    CX(master[2], ancilla[2])


def simon_circuit(oracle, n):
    """
    西蒙算法主程序，按照“图 2”的电路图实现。

    :param oracle: 用于实现函数 g 的量子黑盒
    :param n: 函数 f 输入长度
    :return output_seq: 西蒙量子电路的输出比特串
    """
    # 初始化量子环境，选择使用本地自研模拟器
    # 注：量易伏也支持云端模拟器和真机后端，访问 https://quantum-hub.baidu.com/ 获取更多信息。
    env = QEnv()
    env.backend(BackendName.LocalBaiduSim2)

    # 步骤 1：初始化系统量子态
    # master 是一个 n 量子比特的主寄存器，ancilla 是一个 n 量子比特的辅助寄存器
    master = []
    ancilla = []
    for i in range(n):
        master.append(env.Q[i])
        ancilla.append(env.Q[i + n])

    # 步骤 2：主寄存器作用 H 门
    for i in range(n):
        H(master[i])

    # 步骤 3：将量子黑盒作用到系统
    oracle(master, ancilla)

    # 步骤 4：主寄存器的所有量子比特分别作用 H 门
    for i in range(n):
        H(master[i])

    # 步骤 5：主寄存器量子比特分别执行 Z 测量
    MeasureZ(master, range(n))

    # 运行本地模拟器并去读结果
    result = env.commit(shots=1, fetchMeasure=True)

    output_seq = list(result['counts'].items())[0][0]

    return output_seq


def xdoty(x, y):
    """
    计算两个等长比特串 x 和 y 的点积 x cdot y

    :param x: 一个比特串
    :param y: 一个与 y 等长的比特串
    :return value: x 与 y 的点积，定义为 x dot y = (\sum_k x_ky_k) mod 2
    """
    n = len(x)
    value = 0
    for i in range(n):
        value += int(x[i]) * int(y[i])
    return value % 2


def simon(oracle, n):
    """
    西蒙算法主程序

    :param oracle: 用于实现函数 f 的量子黑盒
    :param n: 函数 f 输入比特串长度
    """
    # 运行西蒙量子电路 4n 次，检测量子电路测量结果是否满足与隐藏比特串 s 的点积为 0
    for i in range(4 * n):
        output_seq = simon_circuit(oracle, n)
        # QCompute 默认从最后一位开始测量，因此输出需要反向
        output_seq = output_seq[::-1]

        value = xdoty(output_seq, s)
        print("第", i + 1, "轮测试：西蒙算法量子电路测量结果比特串为", output_seq,
              "，与隐藏比特串", s, "的点积为", value)


def main():
    """
    调用西蒙算法
    """
    n = 3
    print("使用西蒙算法计算量子黑盒对应的函数的隐藏比特串 ...")
    simon(oracle_g, n)


if __name__ == '__main__':
    main()

复制

上述程序的输出结果如下：

使用西蒙算法计算量子黑盒对应的函数的隐藏比特串 ...
第 1 轮测试：西蒙算法量子电路测量结果比特串为 011 ，与隐藏比特串 100 的点积为 0
第 2 轮测试：西蒙算法量子电路测量结果比特串为 001 ，与隐藏比特串 100 的点积为 0
第 3 轮测试：西蒙算法量子电路测量结果比特串为 000 ，与隐藏比特串 100 的点积为 0
第 4 轮测试：西蒙算法量子电路测量结果比特串为 000 ，与隐藏比特串 100 的点积为 0
第 5 轮测试：西蒙算法量子电路测量结果比特串为 011 ，与隐藏比特串 100 的点积为 0
第 6 轮测试：西蒙算法量子电路测量结果比特串为 011 ，与隐藏比特串 100 的点积为 0
第 7 轮测试：西蒙算法量子电路测量结果比特串为 001 ，与隐藏比特串 100 的点积为 0
第 8 轮测试：西蒙算法量子电路测量结果比特串为 010 ，与隐藏比特串 100 的点积为 0
第 9 轮测试：西蒙算法量子电路测量结果比特串为 000 ，与隐藏比特串 100 的点积为 0
第 10 轮测试：西蒙算法量子电路测量结果比特串为 011 ，与隐藏比特串 100 的点积为 0
第 11 轮测试：西蒙算法量子电路测量结果比特串为 010 ，与隐藏比特串 100 的点积为 0
第 12 轮测试：西蒙算法量子电路测量结果比特串为 000 ，与隐藏比特串 100 的点积为 0

复制

参考资料

[1] Simon, Daniel R. "On the power of quantum computation." SIAM Journal on Computing 26.5 (1997): 1474-1483.

[2] Vazirani, Umesh V. Lecture 7: Simon's Algorithm, Course CS294-2, Quantum Computation, Fall 2004.

附录：习题

习题 1. 证明公式 $(18)$ ： $p (y^{(1)}, \dots, y^{(k)} 线性无关) \geq \frac{1}{4}$ 。

证明. 对任意 $a, b \in [0, 1]$ 有 $(1 - a) (1 - b) = 1 - a - b + a b \geq 1 - (a + b)$ 。利用这个不等式，我们有

\begin{matrix} p (y^{(1)}, \dots, y^{(k)} 线性无关) & = (1 - \frac{1}{2^{n - 1}}) (1 - \frac{1}{2^{n - 2}}) \dots (1 - \frac{1}{2}) \geq \frac{1}{2} [1 - (\frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n - 1}})] \geq \frac{1}{4} . \\ (24) \end{matrix}

证明完毕。 $□$

最后更新时间：2021年12月20日

背景介绍
经典算法
西蒙算法
简例与量易伏平台演示
参考资料
附录：习题