量易简

伯恩斯坦-瓦兹拉尼算法

背景介绍

伯恩斯坦-瓦兹拉尼算法是由伯恩斯坦（Ethan Bernstein）和瓦兹拉尼（Umesh Vazirani）于 1992 年提出 $^{[1, 2]}$ ，用来展示量子算法在理论上有胜过经典计算机的潜力。

在这一节中我们将具体介绍量子黑盒的概念及其电路形式，并介绍设计量子算法中非常重要的步骤——均匀叠加，是实现量子并行计算的关键。量子黑盒与均匀叠加的概念对这一章后续的算法都非常重要。

问题描述

以下我们形式化描述伯恩斯坦-瓦兹拉尼算法解决的问题。

给定一个黑盒（Oracle） $O$ ，计算布尔函数 $f : {0, 1}^{n} \to {0, 1}$ 。 $f$ 满足以下性质：存在长度为 $n$ 的比特串 $s \in {0, 1}^{n}$ （我们称 $s$ 为函数 $f$ 的隐藏比特串。）使得
$\begin{matrix} f (x) = s \cdot x \\ (1) \end{matrix}$
其中 $s \cdot x$ 是点积运算，定义为 $s \cdot x = \oplus_{k = 0}^{n - 1} s_{k} x_{k}$ ， $s_{k}$ 表示比特串 $s$ 第 $k$ 个比特， $\oplus$ 表示模 $2$ 加法运算。用 $x \in {0, 1}^{n}$ 作为输入调用 $O$ ，黑盒的输出为 $f (x)$ 。算法的任务是通过调用 $O$ 来计算比特串 $s$ 。算法的复杂度定义为调用 $O$ 的次数。

经典算法

在这一节我们分析使用经典计算机完成该任务需要调用 $O$ 的次数。任何经典算法调用一次 $O$ 最多只能获取一比特信息，因此要计算长度为 $n$ 的比特串 $s$ 至少需要对 $O$ 进行 $n$ 次调用。另一方面，因为

\begin{matrix} f (1000 \dots 00) & = s_{1} f (0100 \dots 00) & = s_{2} f (0010 \dots 00) & = s_{3} f (0001 \dots 00) & = s_{4} ⋮ f (0000 \dots 10) & = s_{n - 1} f (0000 \dots 01) & = s_{n} \end{matrix}

即每次调用能够确定 $s$ 的一位比特，所以对 $O$ 调用 $n$ 次可以计算 $s$ 。经典计算机完成该任务需要调用 $O$ 的次数为 $n$ 。

伯恩斯坦-瓦兹拉尼算法

在这一节我们介绍伯恩斯坦-瓦兹拉尼量子算法，该算法只需调用 $1$ 次 $O$ 即可计算 $s$ ，因此相对经典算法有多项式级加速。我们首先讨论如何构造一个量子门实现 “调用 $O$ ” 操作，然后利用该量子门给出伯恩斯坦-瓦兹拉尼算法的量子电路，最后逐步分析该量子电路的演化过程，证明算法的正确性。

量子黑盒

我们首先要将“调用 $O$ ”翻译成量子计算机能识别的操作。为此，我们假设有如下形式的量子门：

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

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

其中 $| x ⟩$ 是 $n$ 量子比特串，我们称之为主寄存器； $| y ⟩$ 是单量子比特，我们称之为辅助量子比特。可以证明如上构造的 $U_{f}$ 是一个酉矩阵，它的作用是将输出 $f (x)$ 编码到辅助量子比特 $y$ 上。从这个意义来讲， $U_{f}$ 实现了“调用 $O$ ”操作。当 $x$ 满足 $f (x) = 0$ 时，辅助量子比特不变；当输入 $x$ 满足 $f (x) = 1$ 时，辅助量子比特会被翻转。

习题 1. 证明满足公式 $(2)$ 的 $n + 1$ 比特量子门 $U_{f}$ 是一个酉矩阵。

算法流程与算法分析

伯恩斯坦-瓦兹拉尼算法的量子电路表示如下：

伯恩斯坦-瓦兹拉尼算法的量子电路.png — 图 2：伯恩斯坦-瓦兹拉尼算法的量子电路。

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

步骤1：初始化系统量子态。 将主寄存器初始化为 $| 0 ⟩^{\otimes n}$ ，即前 $n$ 个量子比特初始化为 $| 0 ⟩$ 状态，并将辅助量子比特初始化为 $| 1 ⟩$ 状态。此时整个系统（主寄存器加辅助量子比特所构成的系统）所处的状态为

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

步骤2：均匀叠加。 即对所有 $n + 1$ 个量子比特分别作用 $H$ 门，作用后的系统状态为：

\begin{matrix} | ψ_{1} ⟩ & = H^{\otimes (n + 1)} | ψ_{0} ⟩ = H^{\otimes n} | 0 ⟩^{\otimes n} \otimes H | 1 ⟩ = (\frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 | x ⟩) (\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}), \\ (4) \end{matrix}

最后一步利用了量子计算中的一个常用技巧：

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

注：在这里我们解释并强调一下均匀叠加的重要性，这一步也是大多数基于黑盒的量子算法可以相对于经典算法实现加速的关键。注意到在经过均匀叠加后，主寄存器的量子态变成了 $(\frac{1}{\sqrt{2^{n}}} \sum_{x = 0}^{2^{n} - 1} | x ⟩)$ ，也就是所有可能输入的均匀叠加态，因此在后续作用量子黑盒后将实现对所有输入的并行计算，而这是经典计算所无法实现的。

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

\begin{matrix} | ψ_{2} ⟩ & = U_{f} | ψ_{1} ⟩ = \frac{1}{\sqrt{2^{n + 1}}} 2^{n} - 1 \sum x = 0 U_{f} (| x ⟩ | 0 ⟩ - | x ⟩ | 1 ⟩) = \frac{1}{\sqrt{2^{n + 1}}} 2^{n} - 1 \sum x = 0 (| x ⟩ | f (x) ⟩ - | x ⟩ | 1 \oplus f (x) ⟩) = \frac{1}{\sqrt{2^{n + 1}}} 2^{n} - 1 \sum x = 0 (- 1)^{f (x)} | x ⟩ (| 0 ⟩ - | 1 ⟩) = (\frac{1}{\sqrt{2^{n}}} 2^{n} - 1 \sum x = 0 (- 1)^{s \cdot x} | x ⟩) (\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}) = (H^{\otimes n} | s ⟩) (\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}), \\ (6) \end{matrix}

推导的第四步利用了量子计算中常用的等式： $| f (x) ⟩ - | 1 \oplus f (x) ⟩ = (- 1)^{f (x)} (| 0 ⟩ - | 1 ⟩)$ 。可以通过穷举 $f (x)$ 的值来证明该等式。最后一步利用到公式 $(5)$ 。

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

\begin{matrix} | ψ_{3} ⟩ & = (H^{\otimes n} \otimes I) | ψ_{2} ⟩ = (H^{\otimes n} H^{\otimes n} | s ⟩) (\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}) = | s ⟩ (\frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}}), \\ (7) \end{matrix}

最后一步利用了 $H$ 门的基本性质： $H$ 门的逆变换仍为 $H$ ，即 $H^{2} = I$ 。

步骤5：主寄存器的所有量子比特分别执行计算基测量。 由 $| ψ_{3} ⟩$ 的表达式可知，测量结果比特串就是 $s$ 。

习题 2. 证明公式 $(5)$ 。

算法总结

需要的硬件设备：
- $n + 1$ 个量子比特。
- Hadamard 门。
- 量子黑盒 $U_{f}$ 。
- 计算基测量。
输入： 量子黑盒 $U_{f}$ ，功能是 $U_{f} | x ⟩ | y ⟩ = | x ⟩ | y \oplus f (x) ⟩$ ，其中函数 $f$ 如公式 $(1)$ 定义。
输出： 隐藏比特串 $s$ 。
运行代价： 调用一次量子黑盒 $U_{f}$ 。
运行过程：
1. 主寄存器量子比特初始化为 $| 0 ⟩$ ，辅助量子比特初始化为 $| 1 ⟩$ 。
2. 均匀叠加，对每个量子比特上作用 $H$ 门得到
$\begin{matrix} H^{\otimes n} | 0 ⟩^{\otimes n} \otimes H | 1 ⟩ . \\ (8) \end{matrix}$
1. 作用量子黑盒 $U_{f}$ 得到
$\begin{matrix} H^{\otimes n} | s ⟩ \otimes H | 1 ⟩ . \\ (9) \end{matrix}$
1. 主寄存器的每个量子比特上作用 $H$ 门得到
$\begin{matrix} | s ⟩ \otimes H | 1 ⟩ . \\ (10) \end{matrix}$
1. 测量主寄存器，测量结果即为比特串 $s$ 。

简例与量易伏平台演示

为了加深对此算法的理解，在这一小节，我们介绍如何在量易伏平台上进行模拟实验。我们将首先考虑一个三比特的简单例子，给出对应的量子黑盒，以及 QComposer 中的量子电路。有兴趣的读者可以登录量易伏平台搭建并体验使用量子真机运行，也可以考虑其他的隐藏比特串，设计对应的量子黑盒并搭建自己的电路。然后我们将基于混合语言编程给出此例子的代码，推荐读者在本地使用 QCompute SDK 进行模拟实验。

QComposer 电路

考虑隐藏比特串为 $s = 101$ ，此时黑盒 $O$ 计算的函数 $f : {0, 1}^{3} \to {0, 1}$ 可表示为

\begin{matrix} f (x) = (x_{0} \cdot 1) \oplus (x_{1} \cdot 0) \oplus (x_{2} \cdot 1), \\ (11) \end{matrix}

其中 $x_{i}$ 表示 $x$ 的第 $i$ 比特。在 QComposer 中的电路如下图 3 所示（读者可自行验证此处量子黑盒部分实现了上述函数）：

量易伏 QComposer 伯恩斯坦-瓦兹拉尼算法量子黑盒 — 图 3：量易伏 QComposer 上对 $U_{f}$ 的电路

其对应的 OPENQASM 代码如下：

OPENQASM 2.0;
include "qelib1.inc";
qreg q[4];
creg c[4];
// 将辅助量子比特初始化为|1>
//
x q[3];
// 所有 n+1 个量子比特分别作用 H 门
//
h q[0];
h q[1];
h q[2];
h q[3];
//
// 作用量子黑盒
cx q[0], q[3];
cx q[2], q[3];
// 主寄存器的所有量子比特分别作用 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];

复制

理想模拟器输出结果为：

{
    "101":1024
}

复制

注：量易伏平台上模拟返回的字符串从左往右第一位表示的是最高位的量子比特，和传入的信息顺序相反，故此处理想模拟器输出结果 101 在翻转后得到 101 即为隐藏比特串（如果读者考虑其他例子需要注意这一点）。

QCompute 程序

基于量易伏平台的具体代码如下：

from QCompute import *
import numpy as np

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

# 量子电路比特数
qubit_num = 4
# 测量次数
shots = 1024
# 创建环境
env = QEnv()
# 选择随机数
seed = int(2147483647*np.random.random())
# 选择后端
# 注：量易伏也支持云端模拟器和真机后端，访问 https://quantum-hub.baidu.com/ 获取更多信息。
env.backend(BackendName.LocalBaiduSim2, '-s ' + str(seed))

# 量子黑盒，其中比特串 s 为 101
def Oracle(q):
    CX(q[0], q[3])
    CX(q[2], q[3])

# 步骤 1：初始化 4 量子比特电路
q = [env.Q[i] for i in range(qubit_num)]

# 最后一个量子比特初始化为1
X(q[3])

# 步骤 2：加一层 H 门
for i in range(qubit_num):
    H(q[i])

# 步骤 3：加入量子黑盒
Oracle(q)

# 步骤 4：加一层 H 门
for i in range(qubit_num):
    H(q[i])

# 步骤 5：测量 0, 1, 2 号量子比特结果
MeasureZ([q[0], q[1], q[2]], range(3))
taskResult = env.commit(shots, fetchMeasure=True)
print("Shots", taskResult['shots'])
print("Counts", taskResult['counts'])
print("Seed", seed)

# QCompute 默认从最后一位开始测量，因此输出需要反向
bit = max(taskResult['counts'], key=taskResult['counts'].get)
bit[::-1]
print("解码得到隐藏比特串：", bit[::-1])

复制

运行结束后我们会得到

Shots 1024
Counts {'101': 1024}
Seed 948332576
解码得到隐藏比特串： 101

复制

这就是 $f$ 对应的隐藏比特串 $s = 101$ 。

参考资料

[1] Bernstein, Ethan, and Umesh Vazirani. "Quantum complexity theory." Proceedings of the 25th Annual ACM Symposium on Theory of Computing. 1993.

[2] Bernstein, Ethan, and Umesh Vazirani. "Quantum complexity theory." SIAM Journal on Computing 26.5 (1997): 1411-1473.

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

背景介绍
经典算法
伯恩斯坦-瓦兹拉尼算法
简例与量易伏平台演示
参考资料