在本文中,我们将讨论 Deutsch 算法的问题陈述及其功能。使用classical、Qiskit 和 Cirq 推导和实现 Deutsch 算法。

量子并行性是许多量子算法的基本特征。它允许量子计算机同时计算函数 的多个不同值。如红色方框所示

推理
量子干涉是叠加的结果。在量子计算机中,这允许将多个状态折叠成所需结果的概率。
Deutsch的算法结合了量子并行性和量子力学中的干涉特性。
设置:
有一个单变量函数 ,在二进制字母 上定义,输出范围在相同的字母 中,即 。
如何在量子电路模型中建模 ?
使这项任务变得困难的原因是,根据量子力学的假设,所有的量子操作必须是酉的,因此是可逆的。然而,一般来说,给定一个函数的输出 ,并不总是可以反转 以获得输入 。换句话说,我们必须以保证计算可以撤消的方式计算 。
这是通过以下设置实现的:

图 1: 是酉算子,将 映射为任何 (即 表示标准基态),其中 表示异或或模 2 加法。注意,通过线性,一旦我们在标准基状态上定义 的动作,我们立即知道它如何作用于任何输入状态 。
现在 是可逆的,这是因为在其输出端再次运行 , ,产生状态 ,因为 (将相同的位相加两次,除以 2,余数为零)。我们没有具体说明 的内部工作原理(即我们没有给出实现上述功能的电路)。我们将 视为一个“黑匣子”或“预言机”,我们认为我们可以运行它,但不能“查看内部”以查看其实现细节。
问题:
通过一些检查,并且不对 做任何假设,函数 有四种可能的配置:
- 两个输入 都映射到输出0: 。
- 两个输入 都映射到输出 。
- 输入通过 不变: 。
- 输入在通过 后交换: 。
我们将前两种情况称为 是常数(即,无论我们插入什么输入,函数的行为方式都相同),后两种情况称为 是平衡的。
问题如下:
给定一个函数 ,并且在不知道更多内容的情况下,确定 是一个常数还是有最小函数求值数的平衡函数。
经典算法会怎么做?

图2:经典if else
在经典意义上,解决这个问题的算法将实现一个 if-then-else 语句,如图 2 所示。如您所见,我们需要两个函数评估来找出答案。因此,对 最多两个查询就足以解决这个问题。
我们可以只用一个查询来完成吗?
经典的方法是无法实现的。但从数量上看,Deutsch 展示了如何通过单个查询来实现这一目标。
在量子查询复杂性的研究中,我们给出了一个实现某些函数的 的黑盒 ,并询问 所需查询的最小数量是多少,以确定 的某个所需属性。
我们感兴趣的是最小化成本函数,以解决Deutsch的问题,如上定义的那样,对 的量子查询数量。
算法:
首先尝试一种更简单、更纯朴的方法——因为我们可以批量查询 ,(如图 1 所示)
如果我们只是在输入寄存器的叠加中查询 ,会发生什么?
换句话说,如果我们运行 的电路,输入状态 替换为 ,输出状态 替换为 ,会发生什么情况?
直观地说,这里我们将输入寄存器设置为可能的输入 ,因此我们希望 返回两个可能输出的叠加, 。事实上,通过 的线性度,电路的输出将是

图 3:我们只用一个查询就获得了 的两个输出!
虽然我们的输出 都处于叠加状态,但我们不能指望通过测量来提取这两个答案。
幸运的是,Deutsch 的目标不是在单次查询后同时提取 。相反,想要一些可能更简单的东西,求表达式 的值。
这个表达式 从何而来?
从本文的XOR中说服自己,如果 , 是常数,如果 ,则 是平衡的。因此,Deutsch 的问题等价于求 。
Deutsch算法:

图 4:Deutsch 提出的算法
那么有趣的问题是为什么 和 ?
作为第一个量子比特输入,它可以是 的任何值。一般而言,我们考虑第一个量子比特是 , 在 ,但是, 作为第二个量子比特更有趣,因为要实现相位反冲的概念, 作为第二个输入是不可能的。
综合以上考虑,波函数变为:

图 6:使用 Oracle 的波函数
现在,有两种可能性:要么 ,要么 。
如果 ,则方程简化为 其中 ,即输入状态不因 的作用而改变。
如果 ,则方程简化为 其中 。
即产生−1 相位因子
我们可以用一个方程中总结这两种情况

图5:阶段井涌总结
在应用最后一个Hadamard门并假设 是常数,即图 5 中的 ,其结果为

图 6: 应用 Hadamard Gate 后
在应用最后一个 Hadamard 门并考虑初始输入为 并假设现在 是平衡的,即图 5 中的 ,结果为

图 7:应用 后
从图 8 中得到,如果 则 ,那么 这会带来 或 并始终在中间留下 ,这导致 状态,如图 8 所示。

图 8:如果 ,则 且 则

图9:应用最后一次Hadamard结果
结论:如果 是常数,算法输出 ,如果 是平衡的,算法输出 。因此,该算法仅使用单个查询即可确定 是常数还是平衡!
用 Qiskit 和 Cirq 实现:
在图 10 中,我们可以观察到Oracle在常量和平衡条件下的所有可能的实现方式。

图 10:可能的预言机
使用 IBMQ Composer 实现:
在下面的 Imp 1 中,结果以100%的概率显示 ,其中 是 , 也是 。从 的 开始, 或Oracle函数是常量。

Imp 1:第一个量子比特结果 表示常数函数
在下面的 Imp 2 中,结果以 100% 的概率显示 ,其中 是 和 也是 。从 作为 得出 或 Oracle 函数是常数。

Imp 2:第一个量子比特结果 显示联系功能
在下面的 Imp 3 中,结果以 100% 的概率显示 ,其中 是 和 也是 。从 作为 得出 或 Oracle 函数是平衡的。

Imp 3:第一个量子比特结果 显示平衡函数
在下面的 Imp 4 中,结果显示 有 100% 的概率,其中 是 并且 也是 。从 作为 得出 或 Oracle 函数是平衡的。

Imp 4:第一个量子比特结果 显示平衡函数
使用 IBMQ Qiskit 实现:
在以下代码块中,我们将介绍图 10 中提到的 Oracle 和使用q iskit 的 Deutsch 算法的实现。
如下 qiskit 1 所示,为给定的秘密函数生成 Oracle

qiskit 1:生成随机预言机
如下 qiskit 2 所示,创建带有初始条件和 Oracle 的 Deutsch Algorithm

qiskit 2:创建 Deutsch 电路
如下面的 qiskit 3 所示,创建一个量子电路,分配量子比特数,生成随机布尔秘密函数并可视化电路。

qiskit 3:创建电路,没有量子比特并可视化电路
如下面的 qiskit4 所示,它在模拟器上运行电路并测量结果。

qiskit 4:通过在 qasm 模拟器上运行来测量结果
我们使用 IBM qiskit 从以下结果 1、结果 2、结果 3、结果 4 中实现了图 10

结果 1:对于 为 , 表示 oracle 为平衡

结果 2:对于 为 , 表示 oracle 为常数

结果 3:对于 为 , 将 oracle 显示为常数

结果 4:对于 为 , 表示 oracle 是平衡的
使用 Cirq 实现:
在以下代码块中,我们将介绍图 10 中提到的 Oracle 和使用Cirq的 Deutsch 算法的实现。

Cirq 1:导入所需模块
如下面的cirq 2所示,为给定的秘密功能生成Oracle

cirq 2:生成随机 Oracle
如下面的cirq3 所示,使用初始条件和 Oracle 创建 Deutsch 算法

cirq 3:创建 Deutsch 电路
如下面的 cirq 4 所示,创建一个量子电路,分配量子比特数,生成一个随机布尔秘密函数,在模拟器上运行电路并测量结果。

cirq 4:创建电路,没有量子比特并通过在模拟器上运行来测量结果
生成的结果如下图所示

img 1:对于所有 4 种可能的情况
原文链接:https://anonymousket.medium.com/quantum-algo-deutsch-algorithm-ccc119c69c08
---煤油灯科技victorlamp.com翻译整理---









