量子算法:Deutsch 算法

煤油灯科技2022-08-31 09:32

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

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

推理

量子干涉是叠加的结果。在量子计算机中,这允许将多个状态折叠成所需结果的概率。

Deutsch的算法结合了量子并行性和量子力学中的干涉特性。

设置:

有一个单变量函数 ,在二进制字母 上定义,输出范围在相同的字母0,10,1 中,即f(x):{0,1}→{0,1}f(x):\left\{0,1\right\}→\left\{0,1\right\} 。

如何在量子电路模型中建模f(x)f(x) ?

使这项任务变得困难的原因是,根据量子力学的假设,所有的量子操作必须是酉的,因此是可逆的。然而,一般来说,给定一个函数的输出f(x)f(x)  ,并不总是可以反转ff 以获得输入xx  。换句话说,我们必须以保证计算可以撤消的方式计算f(x)f(x) 。

这是通过以下设置实现的:

图 1:UfUf 是酉算子,将∣⟩∣⟩→∣⟩∣x⊕y⟩∣⟩∣⟩→∣⟩∣x⊕y⟩ 映射为任何x,y∈{0,1}x,y∈\left\{0,1\right\} (即∣x⟩,∣y⟩∣x⟩,∣y⟩ 表示标准基态),其中⊕⊕ 表示异或或模 2 加法。注意,通过线性,一旦我们在标准基状态上定义UfUf 的动作,我们立即知道它如何作用于任何输入状态∣ψ⟩∣ψ⟩ 。

现在UfUf 是可逆的,这是因为在其输出端再次运行UfUf ,∣⟩∣y⊕f(x)⟩∣⟩∣y⊕f(x)⟩ ,产生状态∣⟩∣y⊕f(x)⊕f(x)⟩=∣⟩∣y⟩∣⟩∣y⊕f(x)⊕f(x)⟩=∣⟩∣y⟩ ,因为f(x)⊕f(x)=0f(x)⊕f(x)=0 (将相同的位相加两次,除以 2,余数为零)。我们没有具体说明UfUf 的内部工作原理(即我们没有给出实现上述功能的电路)。我们将UfUf 视为一个“黑匣子”或“预言机”,我们认为我们可以运行它,但不能“查看内部”以查看其实现细节。

问题:

通过一些检查,并且不对f(x)f(x) 做任何假设,函数f(x)f(x) 有四种可能的配置:

  • 两个输入0、10、1 都映射到输出0:f(0)=f(1)=0f(0)=f(1)=0 。
  • 两个输入0、10、1 都映射到输出1:f(0)=f(1)=11:f(0)=f(1)=1 。
  • 输入通过f(x)f(x) 不变:f(0)=0和f(1)=1f(0)=0和f(1)=1 。
  • 输入在通过f(x)f(x) 后交换:f(0)=1和f(1)=0f(0)=1和f(1)=0 。

我们将前两种情况称为f(x)f(x) 是常数(即,无论我们插入什么输入,函数的行为方式都相同),后两种情况称为f(x)f(x) 是平衡的。

问题如下:

给定一个函数f(x):{0,1}→{0,1}f(x):\left\{0,1\right\}→\left\{0,1\right\} ,并且在不知道更多内容的情况下,确定f(x)f(x) 是一个常数还是有最小函数求值数的平衡函数。

经典算法会怎么做?

图2:经典if else

在经典意义上,解决这个问题的算法将实现一个 if-then-else 语句,如图 2 所示。如您所见,我们需要两个函数评估来找出答案。因此,对UfUf 最多两个查询就足以解决这个问题。

我们可以只用一个查询来完成吗?

经典的方法是无法实现的。但从数量上看,Deutsch 展示了如何通过单个查询来实现这一目标。

在量子查询复杂性的研究中,我们给出了一个实现某些函数的ff 的黑盒UfUf ,并询问UfUf 所需查询的最小数量是多少,以确定ff 的某个所需属性。

我们感兴趣的是最小化成本函数,以解决Deutsch的问题,如上定义的那样,对UfUf 的量子查询数量。

算法:

首先尝试一种更简单、更纯朴的方法——因为我们可以批量查询UfUf  ,(如图 1 所示)

如果我们只是在输入寄存器的叠加中查询UfUf ,会发生什么?

换句话说,如果我们运行UfUf 的电路,输入状态∣x⟩∣x⟩ 替换为α∣0⟩+β∣1⟩α∣0⟩+β∣1⟩ ,输出状态∣y⟩∣y⟩ 替换为∣0⟩∣0⟩ ,会发生什么情况?

直观地说,这里我们将输入寄存器设置为可能的输入0和10和1  ,因此我们希望UfUf 返回两个可能输出的叠加,f(0)和f(1)f(0)和f(1) 。事实上,通过UfUf 的线性度,电路的输出将是

图 3:我们只用一个查询就获得了ff 的两个输出!

虽然我们的输出f(0)和f(1)f(0)和f(1) 都处于叠加状态,但我们不能指望通过测量来提取这两个答案。

幸运的是,Deutsch 的目标不是在单次查询后同时提取f(0)和f(1)f(0)和f(1) 。相反,想要一些可能更简单的东西,求表达式f(0)⊕f(1)f(0)⊕f(1) 的值。

这个表达式f(0)⊕f(1)f(0)⊕f(1) 从何而来?

从本文的XOR中说服自己,如果f(0)⊕f(1)=0f(0)⊕f(1)=0  ,ff 是常数,如果f(0)⊕f1=1f(0)⊕f1=1  ,则ff 是平衡的。因此,Deutsch 的问题等价于求f(0)⊕f(1)f(0)⊕f(1) 。

Deutsch算法:

图 4:Deutsch 提出的算法

那么有趣的问题是为什么∣0⟩∣0⟩ 和∣1⟩∣1⟩ ?

∣0⟩∣0⟩ 作为第一个量子比特输入,它可以是0、10、1 的任何值。一般而言,我们考虑第一个量子比特是∣x⟩∣x⟩ ,x∈{0,1}x∈\left\{0,1\right\} 在∣ψ1⟩|ψ1⟩ ,但是,∣1⟩∣1⟩ 作为第二个量子比特更有趣,因为要实现相位反冲的概念,∣0⟩∣0⟩ 作为第二个输入是不可能的。

综合以上考虑,波函数变为:

图 6:使用 Oracle 的波函数

现在,有两种可能性:要么f(x)=0f(x)=0 ,要么f(x)=1f(x)=1 。

如果f(x)=0f(x)=0 ,则方程简化为∣ψ⟩=∣x⟩⊗12∣0⟩−∣1⟩=∣x⟩∣−⟩∣ψ⟩=∣x⟩⊗12∣0⟩−∣1⟩=∣x⟩∣−⟩ 其中1⊕0=11⊕0=1  ,即输入状态不因UfUf 的作用而改变。

如果f(x)=1f(x)=1 ,则方程简化为∣ψ⟩=∣x⟩⊗12∣1⟩−∣0⟩=−∣x⟩∣−⟩∣ψ⟩=∣x⟩⊗12∣1⟩−∣0⟩=−∣x⟩∣−⟩ 其中 1⊕1=01⊕1=0 。

即产生−1 相位因子

我们可以用一个方程中总结这两种情况

图5:阶段井涌总结

在应用最后一个Hadamard门并假设ff 是常数,即图 5 中的f0=f1f0=f1  ,其结果为

图 6:∣ψ3⟩|ψ3⟩ 应用 Hadamard Gate 后

在应用最后一个 Hadamard 门并考虑初始输入为∣0⟩∣0⟩ 并假设现在ff 是平衡的,即图 5 中的f0!=f1f0!=f1  ,结果为

图 7:应用∣+⟩|+⟩ 后

从图 8 中得到,如果f0=0f0=0 则f(1)=1和f0=1f(1)=1和f0=1 ,那么f1=0f1=0 这会带来++ 或−term−term 并始终在中间留下−- ,这导致∣−⟩∣−⟩ 状态,如图 8 所示。

图 8:如果 f(0)=0f(0)=0 ,则 f(1)=1f(1)=1且f(0)=1f(0)=1 则f(1)=0f(1)=0

图9:应用最后一次Hadamard结果∣1⟩|1⟩

结论:如果ff 是常数,算法输出00  ,如果ff 是平衡的,算法输出11 。因此,该算法仅使用单个查询即可确定ff 是常数还是平衡!

用 Qiskit 和 Cirq 实现:

在图 10 中,我们可以观察到Oracle在常量和平衡条件下的所有可能的实现方式。

图 10:可能的预言机

使用 IBMQ Composer 实现:

在下面的 Imp 1 中,结果以100%的概率显示∣00⟩∣00⟩ ,其中q1q1 是∣0⟩∣0⟩ ,q2q2 也是∣0⟩∣0⟩ 。从∣0⟩∣0⟩ 的q1q1 开始,f(x)f(x) 或Oracle函数是常量。

Imp 1:第一个量子比特结果∣0⟩|0⟩ 表示常数函数

在下面的 Imp 2 中,结果以 100% 的概率显示∣00⟩∣00⟩  ,其中q1q1 是∣0⟩∣0⟩ 和q2q2  也是∣0⟩∣0⟩ 。从q1q1 作为∣0⟩∣0⟩ 得出f(x)f(x) 或 Oracle 函数是常数。 

Imp 2:第一个量子比特结果∣0⟩|0⟩ 显示联系功能

在下面的 Imp 3 中,结果以 100% 的概率显示∣01⟩∣01⟩  ,其中q1q1 是∣1⟩∣1⟩ 和q2q2 也是∣0⟩∣0⟩ 。从q1q1 作为∣1⟩∣1⟩ 得出f(x)f(x) 或 Oracle 函数是平衡的。

Imp 3:第一个量子比特结果∣1⟩|1⟩ 显示平衡函数

在下面的 Imp 4 中,结果显示∣01⟩∣01⟩ 有 100% 的概率,其中q1q1 是∣1⟩∣1⟩ 并且q2q2 也是∣0⟩∣0⟩ 。从q1q1 作为∣1⟩∣1⟩ 得出f(x)f(x) 或 Oracle 函数是平衡的。

Imp 4:第一个量子比特结果∣1⟩|1⟩ 显示平衡函数

使用 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:对于f(x)f(x) 为00 ,11 表示 oracle 为平衡

结果 2:对于f(x)f(x) 为00 ,00 表示 oracle 为常数

结果 3:对于f(x)f(x) 为11 ,11 将 oracle 显示为常数

结果 4:对于f(x)f(x) 为11 ,00 表示 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翻译整理---

你可能也喜欢这些文章