量易简

多伊奇-约萨算法

背景介绍

多伊奇-约萨算法是由多伊奇（David Deutsch）和约萨（Richard Jozsa）在 1992 年设计的一个确定性的量子算法 $^{[1]}$ 。上一节介绍的伯恩斯坦-瓦兹拉尼算法可看作是条件限制版的多伊奇-约萨算法。该量子算法相对于最好的经典确定性算法有着指数级加速，是第一个体现量子计算的有指数级优势的量子算法。需要指出的是，多伊奇-约萨算法是为展示量子计算优势而人为构造的数学问题并为之“量身打造”的量子算法，这些数学问题本身可能没有实用价值。

问题描述

以下我们形式化描述多伊奇-约萨算法解决的问题。

给定一个黑盒（Oracle） $O$ ，它计算布尔函数 $f : {0, 1}^{n} \to {0, 1}$ 。 $f$ 满足以下性质之一：

它是常数函数，即对任意输入 $x, y \in {0, 1}^{n}$ ， $f (x) = f (y)$ 。

它是平衡函数，即满足 $f (x) = 0$ 的 $x$ 的个数为 $2^{n - 1}$ ，满足 $f (y) = 1$ 的 $y$ 的个数为 $2^{n - 1}$ 。

用 $x \in {0, 1}^{n}$ 作为输入调用 $O$ ，黑盒的输出为 $f (x)$ 。算法的任务是通过调用 $O$ 来判定它计算的是常数函数还是平衡函数。算法的复杂度定义为调用 $O$ 的次数。

作为例子，考虑如下定义的两个布尔函数 $g_{1}, g_{2} : {0, 1}^{3} \to {0, 1}$ ：

\begin{matrix} g_{1} (000) = g_{1} (001) = g_{1} (010) = g_{1} (011) = g_{1} (100) = g_{1} (101) = g_{1} (110) = g_{1} (111) = 0; \\ (1) \end{matrix}

\begin{matrix} g_{2} (000) = g_{2} (100) = g_{2} (010) = g_{2} (110) = 0, g_{2} (001) = g_{2} (101) = g_{2} (011) = g_{2} (111) = 1. \\ (2) \end{matrix}

由定义可知 $g_{1}$ 是常数函数而 $g_{2}$ 是平衡函数。

经典算法

在这一节，我们分析使用经典计算机完成该任务需要调用 $O$ 的次数。

最好情况下，我们选取两个不同的输入调用 $O$ ，得到不同的调用结果。那么我们可以断定 $O$ 计算的是平衡函数。

最坏情况下，我们选取 $2^{n - 1}$ 个不同的输入调用 $O$ ，并得到相同的调用结果。此时无法判断 $O$ 计算的是常数函数还是平衡函数。我们需要再选取一个新输入调用 $O$ ，如果得到的调用结果和之前一样，那么可以断定 $O$ 计算的是常数函数；否则它计算的是平衡函数。因此在最坏情况下，需要调用 $O$ 共 $2^{n - 1} + 1$ 次才能确定性地判断出 $O$ 所计算的函数的性质。在上面的 $g_{1}, g_{2}$ 函数例子中（ $n = 3$ ），如果前 $4$ 次选择输入 $000 / 001 / 010 / 011$ 调用 $O$ ，由于 $g_{1}$ 和 $g_{2}$ 的输出值都为 $0$ ，我们无法判断 $O$ 计算的是 $g_{1}$ 还是 $g_{2}$ 。只有继续选取第 $5$ 个输入 $100$ 调用 $O$ ，因为 $g_{1} (100) = 0$ 而 $g_{2} (100) = 1$ ，我们才能根据调用结果判断 $O$ 计算的是常数函数 $g_{1}$ 还是平衡函数 $g_{2}$ 。

多伊奇-约萨算法

在这一小节，我们介绍多伊奇-约萨算法。该算法只需要对 $O$ 进行 $1$ 次调用即可确定性地判断出 $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) ⟩ . \\ (3) \end{matrix}

由于此量子黑盒与本章第二节伯恩斯坦-瓦兹拉尼算法中介绍的一致，此处我们不再过多赘述。

算法流程与算法分析

基于量子门 $U_{f}$ ，多伊奇-约萨算法的量子电路可以表示为：

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

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

\begin{matrix} | ψ_{0} ⟩ = | 0 ⟩^{\otimes n} \otimes | 1 ⟩ . \\ (4) \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 + 1}}} 2^{n} - 1 \sum x = 0 | x ⟩ (| 0 ⟩ - | 1 ⟩) . \\ (5) \end{matrix}

最后一步利用的技巧在上一节：伯恩斯坦-瓦兹拉尼算法中已有介绍。

步骤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 ⟩), \\ (6) \end{matrix}

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

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

其中 $x \cdot y$ 是点积运算，定义为 $x \cdot y = \oplus_{k = 0}^{n - 1} x_{k} y_{k}$ ， $x_{k}$ 表示比特串 $x$ 第 $k$ 个比特。

步骤5：主寄存器的所有量子比特分别执行计算基测量。 以下我们计算测量结果为长度为 $n$ 的全 $0$ 比特串（简记为 $0^{n}$ ）的概率：

\begin{matrix} p (0^{n}) & = {∣ ∣ ∣ ∣ ⟨ 0^{n} | (\frac{1}{2^{n}} 2^{n} - 1 \sum y = 0 (2^{n} - 1 \sum x = 0 (- 1)^{f (x)} (- 1)^{x \cdot y}) | y ⟩) ∣ ∣ ∣ ∣}^{2} = {∣ ∣ ∣ ∣ \frac{1}{2^{n}} 2^{n} - 1 \sum x = 0 (- 1)^{f (x)} ∣ ∣ ∣ ∣}^{2} = {\begin{matrix} 1, & 如果 f 是常数函数， 0, & 如果 f 是平衡函数。 \end{matrix} \\ (8) \end{matrix}

其中 $| c |$ 表示复数 $c$ 的模，推导过程中利用了 $x \cdot 0^{n} = 0$ 性质。以上表达式意味着，如果 $f$ 是常数函数的话，以上量子电路的测量结果为 $0^{n}$ 的概率为 $1$ ；如果 $f$ 是平衡函数的话，以上量子电路的测量结果为 $0^{n}$ 的概率为 $0$ 。因此，如果主寄存器测量结果为 $0^{n}$ ，我们断定 $O$ 计算的 $f$ 是常数函数；否则，我们断定 $O$ 计算的 $f$ 是平衡函数。

算法总结

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

简例与量易伏平台演示

在这一节，我们在量易伏平台上实现此算法。作为例子，我们先构造在问题描述部分给出的两个函数 $g_{1}$ 和 $g_{2}$ （式 $(1)$ , $(2)$ ）对应的量子黑盒，然后使用多伊奇-约萨算法来判断这两个黑盒计算的函数的性质。

QComposer 电路

注意到 $g_{1}$ 是输出结果为 $1$ 的常数函数，所以它对应的量子黑盒为 $U_{g_{1}} = I^{\otimes n} \otimes Z$ ，故整体算法在 QComposer 中的电路如下图 3 所示：

量易伏 QComposer 多伊奇-约萨算法量子黑盒 g_1 — 图 3：量易伏 QComposer 上对 $U_{g 1}$ 的电路

其对应的 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];
// 作用量子黑盒 U_g2
//
id q[0];
id q[1];
id q[2];
z 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];

复制

理想模拟器输出结果为：

{
    "000":1024
}

复制

由于测量结果均为0，故输出 “常数函数”。

对于函数 $g_{2}$ ，注意到可以等价表示为

\begin{matrix} g_{2} (x_{0} x_{1} x_{2}) = x_{2}; x_{0}, x_{1}, x_{2} \in {0, 1}, \\ (12) \end{matrix}

其中 $x_{i}$ 表示第 $i$ 个比特。即函数 $g_{2}$ 取输入比特串的最高位比特作为输出，因此对应的量子黑盒 $U_{g_{2}}$ 定义为

\begin{matrix} U_{g_{2}} (| x_{0} x_{1} x_{2} ⟩ \otimes | y ⟩) = | x_{0} x_{1} x_{2} ⟩ \otimes | y \oplus g_{2} (x_{0} x_{1} x_{2}) ⟩ = | x_{0} x_{1} x_{2} ⟩ \otimes | y \oplus x_{2} ⟩, \\ (13) \end{matrix}

即主寄存器的第 $2$ 个量子比特控制翻转辅助量子比特。量子黑盒 $U_{g_{2}}$ 的量子电路表示如下

布尔函数 g_2 的量子黑盒 — 图 4：布尔函数 $g_{2}$ 的量子黑盒。

此情况下，完整算法在 QComposer 中的电路如下图 5 所示：

量易伏 QComposer 多伊奇-约萨算法量子黑盒 g_2 — 图 5：量易伏 QComposer 上对 $U_{g 2}$ 的电路

其对应的 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];
// 作用量子黑盒 U_g2
id q[0];
id q[1];
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];

复制

理想模拟器输出结果为：

{
    "100":1024
}

复制

由于测量结果不均为0，故输出 “平衡函数”。

QCompute 程序

多伊奇-约萨算法基于混合语言编程的代码如下，推荐读者在本地使用 QCompute SDK 进行模拟实验。

"""
多伊奇-约萨算法演示文件
在这个脚本中，我们先实现多伊奇-约萨算法的量子电路，然后判断两个黑盒 O，他们分别计算以下函数：
1. 常数函数 g_1(x) = 1
2. 平衡函数 g_2(x) = x_2，其中 x_2 表示输入三比特串的最高位比特的值
参考资料：https://qlearn.baidu.com/chapter3/deutsch-jozsa.html
"""

from QCompute import *
import numpy as np

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

def oracle_g1(master, ancilla):
    """
    构造布尔函数 g_1 对应的量子黑盒
    布尔函数 g_1 是三比特输入，一比特输出，且满足 g_1(x) = 1

    :param master: n 量子比特主寄存器
    :param ancilla: 辅助量子比特
    """
    # 因为 g_1(x) = 1，所以要对辅助量子比特作用 Z 门
    Z(ancilla[0])
    pass


def oracle_g2(master, ancilla):
    """
    构造布尔函数 g_2 对应的量子黑盒
    布尔函数 g_2 的真值表为
    |  x  | g_2(x)|
    ---------------
    | 000 |   0   |
    | 100 |   0   |
    | 010 |   0   |
    | 110 |   0   |
    | 001 |   1   |
    | 101 |   1   |
    | 011 |   1   |
    | 111 |   1   |

    :param master: n 量子比特主寄存器
    :param ancilla: 辅助量子比特
    """
    # 由真值表可知，辅助比特的值完全由主寄存器最高位量子比特确定
    # 其对应的量子黑盒可以表示为
    CX(master[-1], ancilla[0])
    pass


def deutsch_jozsa(oracle, n):
    """
    多伊奇-约萨算法主程序，按照“图 2”的电路图实现。

    :param oracle: 用于计算布尔函数 f 的量子黑盒
    :param n: 布尔函数 f 输入比特串长度
    :return flag: flag = 0 表示黑盒计算的函数为常数函数；
                  flag = 1 表示黑盒计算的函数为平衡函数。
    """
    # 创建量子环境
    env = QEnv()
    # 选择随机数
    seed = int(2147483647*np.random.random())
    # 选择 Backend 为本地模拟器
    # 注：量易伏也支持云端模拟器和真机后端，访问 https://quantum-hub.baidu.com/ 获取更多信息。
    env.backend(BackendName.LocalBaiduSim2, '-s ' + str(seed))

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

    # 辅助量子比特初始状态为 |1>
    X(ancilla[0])

    # 步骤 2：所有量子比特作用 H 门
    for i in range(n):
        H(master[i])
    H(ancilla[0])

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

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

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

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

    # 分析本地模拟器的运行结果
    _analyze_output(output['counts'])


def _analyze_output(output):
    """
    多伊奇-约萨算法的数据后处理阶段
    从输出比特串 output 中分析并判断输入函数的类型

    :param output: 多伊奇-约萨算法量子线路的输出结果
    :return flag: flag = 0 表示黑盒计算的函数为常数函数；
                  flag = 1 表示黑盒计算的函数为平衡函数。
    """
    # 读取输出结果的比特串，长度为 n
    # 注意：模拟器在会后台强制测量所有寄存器！我们需要自行读取需要的测量结果
    output_seq = list(output.items())[0][0]
    # 目标比特串是常数函数对应的比特串 0...0
    constant_seq = '000'.zfill(len(output_seq))

    # 如果输出结果比特串与目标比特串相同，那么黑盒计算的函数为常数函数
    # 如果输出结果比特串与目标比特串不同，那么黑盒计算的函数为平衡函数
    if output_seq == constant_seq:
        print("输出比特串为 " + output_seq + ", 黑盒计算的函数是常数函数")
        return 0
    else:
        print("输出比特串为 " + output_seq + ", 黑盒计算的函数是平衡函数")
        return 1


def main():
    """
    main
    """
    # 测试 g_1 的函数性质
    print("测试黑盒1，判断黑盒计算的函数的性质 ...")
    deutsch_jozsa(oracle_g1, 3)

    print("============================")
    # 测试 g_2 的函数性质
    print("测试黑盒2，判断黑盒计算的函数的性质 ...")
    deutsch_jozsa(oracle_g2, 3)


if __name__ == '__main__':
    main()

复制

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

测试黑盒1，判断黑盒计算的函数的性质 ...
输出比特串为 000, 黑盒计算的函数是常数函数
============================
测试黑盒2，判断黑盒计算的函数的性质 ...
输出比特串为 100, 黑盒计算的函数是平衡函数

复制

这表示程序成功的判断出第一个黑盒计算的是常数函数 $g_{1}$ ，而第二个黑盒计算的是平衡函数 $g_{2}$ 。

参考资料

[1] Deutsch, David, and Richard Jozsa. "Rapid solution of problems by quantum computation." Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439.1907 (1992): 553-558.

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

背景介绍
经典算法
多伊奇-约萨算法
简例与量易伏平台演示
参考资料