用Q#介绍量子计算–第15部分,Deutsch-jozsa算法

上次,我们讨论了最初由David Deutsch陈述的问题,专注于确定功能是否恒定或平衡。我们发现,对于该特定问题,量子计算提供了比经典计算更好的查询复杂性–由于它可以在单个Blackbox功能评估中解决任务,而经典计算需要两个功能评估以提供相同的答案。

今天,我们将介绍这种简单问题的概括。

历史

1992年,大卫德国和理查德·乔兹莎出版了一份题为题为的论文量子计算快速解决问题在其中,他们提供了原始1985年德国的概括’s problem –我们讨论的那个最后一篇。如果你从上次回忆起,德意志’S问题处理未知(BlackBox)函数,将单个位为输入,并产生单个位作为输出$ f:\ {0,1 \} \ lightarrow \ {0,1 \} $。我们确定经典我们需要两个功能评估来确定该功能是否是 不变 或者 均衡 ,而在Quantum计算机上,单个Oracle查询就足够了。

德意雪的概括 ’S问题允许解决这不仅仅用于单位输入功能,而是对于任何$ N $ INPUT函数,它可以为每个输入值产生0或A 1作为输出。这可以写入$ f:\ {0,1 \} ^ n \ lightarrow \ {0,1 \} $。

完美明确,因为它在最后一篇文章中简要提到,德国的基本变种’我们最后一次解释的问题,并没有真正来自德意志’s original 1985年。相反,这种特定的制定是在技术上讲的,1992年的Deutsch-Jozsa纸的最简单情况(1985年版本是概率而不是确定性的)。然而,为了清楚起见,提高这种材料的消化率,分别解决两个变体,这就是我们在本系列中所做的感觉。

德意志和乔兹在1992年的论文中强调,古典计算依赖于基于函数评估的问题解决。

当经典的确定性(图灵)计算机解决问题时,它通过评估函数而始终这样做。例如,分解程序将始终找到给定输入的相同系数。它发现哪个因素可以通过额外的约束来指定,缩小任务到函数评估。因此,当解决问题时,经典计算机无法帮助执行比其设置的更难的计算任务。

特别是在德意曲的广义版本的情况下’S问题,通常称为Deutsch-jozsa算法,经典计算理论告诉我们,2美元^ {n-1} + 1 $函数评估需要以确定性获取问题的答案。 Deutsch和Jozsa意识到,由于能够在不需要评估该功能的情况下,在量子计算机上可以更有效地更有效地完成。在不需要评估该功能的情况下,可以更有效地完成–导致,我们将在单个Oracle查询中看到,问题解析。

这种[量子]计算还需要在解决问题时不一定评估功能,因为其输出的状态可能是与不同​​答案相对应的状态的相干叠加,每个状态都解决了问题。这允许量子计算机通过任何经典设备不可用的方法解决问题。

正如我们很快就会看到的那样,量子计算速度可以解决这个问题是非常戏剧性的。

数学背景

在我们能够完全理解Deutsch-Jozsa算法的解决方案之前,让’s回想一下,Hadamard门由以下矩阵表示:

$$ h = \ frac {1} {\ sqrt {2}} \ begin {bmatrix} 1& 1 \\ 1 &
-1 \结束{bmatrix} $$

并且它在确定基准状态$ \ KET {0} $或$ \ KET {1} $ \ \ KET {1} $时,它会在应用于QUBET时创建统一的叠加。

$$ h \ ket {0} = \ frac {1} {\ sqrt {2}} \ begin {bmatrix} 1& 1 \\ 1 &
-1 \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} =\frac{1}{\sqrt{2}}\ket{0} +\ frac {1} {\ sqrt {2}} \ ket {1} $$

$$ h \ ket {1} = \ frac {1} {\ sqrt {2}} \ begin {bmatrix} 1& 1 \\ 1 &
-1 \结束{bmatrix} \ begin {bmatrix} 0 \\ 1 \ neg {bmatrix} = \ frac {1} {\ sqrt {2}} \ ket {0}–\ frac {1} {\ sqrt {2}} \ ket {1} $$

这已经广泛讨论了part 2在这个系列中,如果事情尚不清楚,我建议您再次看看那篇文章。让’S现在考虑在发送两个QUBITS时会发生什么,使两个QUBit量子系统通过$ H $门。由于多QUBBit系统由各个QBits的张量产品表示,因此我们可以如下所述,假设我们从状态$ \ Ket {0} $中的两个Qubits开头。

$$ \ displaylines {h \ ket {0} \ otimes h \ ket {0} \\ =(\ frac {1} {\ sqrt {2}} \ ket {0} + \ frac {1} {\ sqrt { 2}} \ \ er {1})\ otimes(\ frac {1} {\ sqrt {2}} \ ket {0} + \ frac {1} {\ sqrt {2}} \ ket {1})= \ FRAC {1} {2}(\ KET {00} + \ KET {01} + \ KET {10} + \ KET {11})} $$

我们可以进一步扩展它并对计算基态的其他三种可能的组合进行类似的计算,其中差异将在标志中可见,或者,我们在量子计算中所谓的阶段。

$$ \ displaylines {h \ ket {0} \ otimes h \ ket {1} \\ =(\ frac {1} {\ sqrt {2}} \ ket {0} + \ frac {1} {\ sqrt { 2}} \ Ket {1})\ otimes(\ frac {1} {\ sqrt {2}} \ ket {0}–\ frac {1} {\ sqrt {2}} \ ket {1})= \\ \ FRAC {1} {2}(\ KET {00}–\ ket {01} + \ ket {10}– \ket{11})}$$

$$ \ displaylines {h \ ket {1} \ otimes h \ ket {0} \\ =(\ frac {1} {\ sqrt {2}} \ ket {0}–\ frac {1} {\ sqrt {2}} \ ers {1})\ otimes(\ frac {1} {\ sqrt {2}} \ ket {0}+\ frac {1} {\ sqrt {2}} \ ket {1})= \\ \ FRAC {1} {2}(\ KET {00}+ \ket{01} – \ket{10} – \ket{11})}$$

$$ \ displaylines {h \ ket {1} \ otimes h \ ket {1} \\ =(\ frac {1} {\ sqrt {2}} \ ket {0}–\ frac {1} {\ sqrt {2}} \ ers {1})\ otimes(\ frac {1} {\ sqrt {2}} \ ket {0}–\ frac {1} {\ sqrt {2}} \ ket {1})= \\ \ FRAC {1} {2}(\ KET {00}– \ket{01} –\ ket {10} + \ ket {11})} $$

在该观察中,我们现在处于一个职位来介绍概念克朗伯克产品矩阵,其是外产物的广义,并产生张量产品的基质。事实证明,我们可以以矩阵矩阵形式描述上面的转换,即新的$ H ^ {\ otimes 2} $矩阵,由$ H $矩阵组成。

$$ h ^ {\ otimes 2} = \ frac {1} {\ sqrt {2}} \ begin {bmatrix} h& H \\ H & -H\end{bmatrix}$$

我们可以进一步概括为$ H ^ {\ OTIMES N} $门,该门递归地行动了一系列数量的$ N $ QUBITS。

$$ h ^ {\ otimes n} = \ frac {1} {\ sqrt {2}} \ begin {bmatrix} h ^ {\ otimes(n-1)} &h ^ {\ otimes(n-1)} \\ h ^ {\ otimes(n-1)}&-h ^ {\ otimes(n-1)} \ neg {bmatrix} $$

我们在这里获得的通常被称为所谓的沃尔什(或在一些Lieterature,Walsh-Hadamard)转型$ w $。现在假设我们希望创建一个统一的叠加超过$ N $ Qubits,从所有这些都以州$ \ Ket {0} $开头。这相当于$(H \ OTIMES H \ OTIMES… \otimes H)\ket{00 …0} $,我们可以在缺口语法中写入:

$$ w \ ket {0} = \ frac {1}} \ sum_ {2 ^ n}} \ sum_ {x = 0} ^ {2 ^ n-1} \ ket {x}
$$

虽然这为使用$ N $ INPUTS提供了很好的概括,但它们仍然重新预定到$ \ KET {0} $初始状态。进一步迈出这一步,让’S重写公式以涵盖任何任意初始量子位状态。这将在Deutsch-jozsa问题中派上易于应用$ w $(或,写不同的,$ h ^ {\ otimes n} $)转换在$ \ ket {0中的一组Qubits上。 $状态,但随后在同一个集合上已经在叠加中。

为实现这一目标,我们需要引入一种新的优雅方式,可以表达在单个Qubit上表达的哈马德门,即:

$$ H \ KET {x} = \ FRAC {1} {\ SQRT {2}}(\ KET {0} +(-1)^ x \ ket {1})
$$

其中$ x \ in {0,1} $。这捕获了根据我们是否将$ h $ \ \ er {0} $或$ \ KET {1} $申请发生的相变。我们可以进一步将其重写为与任何任意计算基础相关的格式$ \ KET {x} $更紧凑的表单:

$$ h \ ket {x} = \ frac {1} {\ sum_ {z}} \ sum_ {z \ in \ {0,1 \}}( - 1)^ {xz} \ ket {z}
$$

如果我们现在考虑$ \ ket {x} $和$ \ ket {z} $长度为$ n $,它会导致我们的$ w $转换的最终概括(或者,再次编写,$ h ^ {\ otimes n} $)。公式如下:

$$ w \ ket {x} = \ frac {1} {\ sum_ {2 ^ n}} \ sum_ {z = 0} ^ {2 ^ n-1}( - 1)^ {x \ cdot z} \ Ket {z}
$$

其中$ x \ cdot z $是$ x $和$ z $的按位内部产品,modulo 2(二进制标量产品):

$$ x \ cdot z = x_0z_0 \ oplus x_1z_1 \ oplus…\ oplus x_ {n-1} z_ {n-1} $$

解决Deutsch-jozsa问题

为了最好了解Deutsch-jozsa问题,我们可以用纯矩阵转换链写入:

$$ (w \ otimes i)u_f(w \ otimes h)\ ket {0 ^ {\ otimes n}} \ ket {1} $$

在纯文本中,这意味着我们将以N $ \ Ket {0} $的$ n $ Qubits从State $ \ Ket {1} $中的一个Ancilla Qubit开始。然后,我们将以$ \ KET {0} $和$ H $ TRANFORATION将$ W $运算符应用于状态$ \ KET {1} $的QUBT。然后,我们将评估$ U_F $。此时,我们可以忽略Ancilla Qubit并将$ W $转换再次申请到最终将共同衡量的最终$ N $ Qubits。

在里面 上一部分本系列,在看德国的基本变体’问题,我们通过最初忽略$ \ ket {x} $并专注于当Ancilla Qubit $ \ Ket {1} $前往初始转换$ H $,然后通过Oracle $ u_f $来忽略会发生什么。这让我们抵达以下州:

$$ \ ket {\ psi_2} =(-1)^ {f(x)} \ ket {x} \ frac {1} {\ sqrt {2}}(\ ket {0}– \ket{1})
$$

然后我们注入$ H \ KET {x} $代替$ \ KET {x} $,并且能够从那里完成算法。由于Ancilla Qubit在Deutsch-jozsa泛化中的作用与上次讨论的特殊简单案例相同,因此只有其中一个,所以完全相同的方法将在这里为我们工作。

但是,在这种情况下,而不是以$ H \ KET {x} $交换$ \ ket {x} $我们需要记住现在$ \ ket {x} $实际上由$ n $ qubit组成,所以我们应该使用上述讨论了$ W $转型,以ALIBTRARY数量的$ N $ QUBITS(而不是单一)。此外,我们可以观察到$ \ KET { - } $语法的用法可以帮助我们在我们的方程中节省一点空间:

$$
\ ket { - } = \ frac {1} {\ sqrt {2}}(\ Ket {0}– \ket{1})
$$

拍摄所有这一切,我们可以重写$ \ ket {\ psi_2} $:

$$ $ \ {\ psi_2} = \ frac {1}} \ sum_ {2 ^ n}} \ sum_ {x \ in \ {0,1 \} ^ n}( - 1)^ {f(x)} \ ket {x} \ ket { - }
$$

接下来,我们可以使用前一节中提到的公式应用最终$ W \ OTS转换。这导致州$ \ Ket {\ psi_3} $:

$$ \ ket {\ psi_3} = \ frac {1}} \ sum_ {2 ^ n}} \ sum_ {x \ in \ {0,1 \} ^ n}( - 1)^ {f(x)} \左[\ frac {1} {\ sqrt {2 ^ n}} \ sum_ {y \ in \ {0,1 \} ^ n}( - 1)^ {x \ cdot y} \ ket {y} \右] \ ket { - }
$$

我们可以进一步重写它​​并省略尾随安氏\ \ Ket { - } $,因为它不需要测量,无论如何都不需要测量:

$$ \ ket {\ psi_3} = \ sum_ {y \ in \ {0,1 \} ^ n} \ left [\ frac {1} {2 ^ n} \ sum_ {x \ in \ {0,1 \ } ^ n}( - 1)^ {x \ cdot y + {f(x)}} \ rectle] \ ket {y}
$$

在这一点上,我们即将做出深刻的发现。我们感兴趣的概率幅度,州$ \ Ket {0} ^ {\ otimes n} $的概率幅度由以下系数表示:

$$
a_z = \ frac {1} {2 ^ n} \ sum_ {x \ in \ {0,1 \} ^ n}( - 1)^ {x \ cdot y + {f(x)}}
$$

如果我们现在考虑在$ y = 0 $的情况下,我们到达:

$$
a_0 = \ frac {1} {2 ^ n} \ sum_ {x \ in \ {0,1 \} ^ n}( - 1)^ {f(x)}
$$

如果functio $ f(x)$(我们的电路U $ u_f $)是常量的,我们有两种可能性:

$$
a_0 =
\ begin {案例}
1 &\ text {当f(x)= 0} \\时
-1 &\ text {当f(x)= 1} \\时
\结束{案例}
$$

这告诉我们,当该功能是恒定的时,我们初始Qubits $ \ Ket {0} ^ {\ otimes n} $的概率幅度$ a_0 $已减少到+1或-1,具体取决于恒定输出$ u_f $。这意味着对于整个寄存器的联合测量,当功能常量时,所有Qubits都必须产生0s结果。

相反,当该功能平衡时,幅度$ A_0 $将产生0,因为正数和负数+1和-1将相互取消。这导致经典概率等于0,用于接收我们初始QUBits $ \ Ket {0 ^ {\ otimes n}} $的所有零的测量结果。换句话说,至少一个Qubit将产生测量结果1。

这是一个显着的结论–我们已经设法将整个问题减少到简单的二进制结果。当Qubit寄存器的关节测量产生所有零时,我们具有常量函数,如果它没有’t,功能是平衡的。

本节中的数学形式主义在几个部分的优雅和清洁的方法中遵循伊斯勒和巴拉兹.

q#实现

Deutsch-jozsa泛化的Q#实现将在许多方面几乎与所使用的代码相同最后一篇。因此,我将避免讨论相同的零件,只关注重要内容。

就像上次一样,我们将准备四个Oracle函数,其中两个是恒定的,其中两个是平衡的。常量函数与前面的相同:

平衡功能将通过应用CNOT门来执行XOR逻辑,这也类似于最后一次。差异是自然的,先前的CNOT仅跨越两个QUBITS(输入和ancilla qubit),而在这里它将与辅助qubit纠缠在一起。

我们将用于调用不同的oracelles的orchestrator操作也将基于上一篇文章的代码,具有显着的差异是我们需要在整个输入寄存器上执行关节测量,并检查它是否产生零,或换句话说,$ \ ket {00.. 0} $结果。从$ Microsoft.quantum.measurement $命名空间,可以在Q#中轻松在Q#中可以轻松实现。在$ z \ otimes z \ otimes中测量整个寄存器。 z $依据。 Orchestrator的用法允许我们在测试不同的Oracle实现时重复使用代码,这是非常欢迎从纯粹编程的角度来看的。

这块代码分配了数量$ N $ Qubits(一个Qubit寄存器),它表示输入的ORACLES,以及ANCILLAQUBBit,以确保计算的可逆性。 $ ApplyToeacha $ operation的用法允许我们优雅地将$ H $门应用于整个量子位寄存器。在Qubits通常复位之后,$ MeasureAllz $为我们提供了相关结果,然后将其作为操作输出返回。

最后,运行到我们程序的入口点将调用乐队四次–每次Oracle函数一次。

这结论是我们的Q#实现了Deutsch-jozsa算法,具有四个示例Oracle函数。调用此程序生成以下输出:

这正是我们基于上述部分讨论的数学的预期–Q Q ORESS赋予我们的精湛功能来测试和验证量子计算概念,以最小的努力。

概括

要得出结论,我们需要说我们可以为自己感到骄傲。与其经典对应相比,Deutsch-jozsa算法的实现提供了指数加速–单一评估与Oracle的1美元^ {n-1} + 1 $评估。现在,为了没有太过携带,我们需要强调,这也是一个问题,这并没有真正的世界应用。首先,我们可以轻松找到我们提到的2 ^ {n-1} + 1 $函数评估的概率经典解决方案。

无论如何,该算法作为学习工具非常有用,并且可以用巧妙的算法接近相位变化和叠加的潜在潜力的说明。

在下一个帖子中,我们将继续使用一些最重要的量子算法。