Qiskit汉化-2.5 Proving Universality

Dora Dōjo
1

证明普遍性

[toc]

1.介绍

给定的计算机能做什么?一般来说，可计算的极限是什么?在我们对计算机有一个很好的概念或者如何建造计算机之前，艾伦·图灵就已经解决了这些问题。

要对我们的经典计算机，特别是标准数字计算机提出这个问题，我们需要去掉所有的屏幕、扬声器和花哨的输入设备。我们剩下的只是一台将输入位串转换为输出位串的机器。如果一个设备可以执行任何这样的转换，接受任意一组输入并将它们转换为任意选择的一组相应的输出，我们称之为通用。

量子计算机类似地获取输入状态并将其转换为输出状态。因此，我们将能够以类似的方式确定普遍性。更准确地说，为了能够证明什么时候可以实现通用性，什么时候不能实现通用性，使用量子门的矩阵表示是有用的。但首先我们需要复习一些技巧。

2.矩阵的乐趣

2.1 矩阵的外积

在前面几节中，我们计算了许多内积，例如 ⟨0|0⟩=1 美元。这些结合了bra和ket给我们一个单一的数字。我们也可以把它们组合成一个矩阵，只要把它们按相反的顺序排列就可以了。这被称为外积，通过标准的矩阵乘法运算。例如

|0\rangle\langle0|= \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1&0 \\ 0&0 \end{pmatrix},\\ |0\rangle\langle1| = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0&1 \\ 0&0 \end{pmatrix},\\ |1\rangle\langle0| = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 0&0 \\ 1&0 \end{pmatrix},\\ |1\rangle\langle1| = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0&0 \\ 0&1 \end{pmatrix}.\\

这也意味着我们可以将任何矩阵写成纯外积的形式。在上面的例子中，我们构建了四个矩阵，覆盖了单量子比特矩阵中的每个单元素，因此我们可以用它们来编写任何其他单量子比特矩阵。

M= \begin{pmatrix} m_{0,0}& m_{0,1} \\ m_{1,0}&m_{1,1} \end{pmatrix} = m_{0,0} |0\rangle\langle0|+ m_{0,1} |0\rangle\langle1|+ m_{1,0} |1\rangle\langle0|+ m_{1,1} |1\rangle\langle1|

这个性质也扩展到矩阵的任意数量的量子比特，$n$。我们只是使用相应的$n$比特字符串的外积。

2.2 酉矩阵和厄米特矩阵

矩阵 M 的厄米特共轭矩阵 M^\dagger 是矩阵的转置(将左下的元素替换为右上的元素，以此类推)和每个元素共轭复数的组合。两个对量子计算非常重要的矩阵族由它们与厄米特共轭的关系定义。一个是酉矩阵族，对于它

U U^\dagger = U^\dagger U = I.

这意味着一个酉的厄米特共轭是它的逆: 另一个一元的 U^\dagger 具有撤销 U 影响的能力。量子计算中，除测量和重置操作外，所有的门都可以用酉矩阵表示。

统一性的另一个结果是，它保留了两个任意状态之间的内积。具体来说，有两种状态 $\left| \psi_0 \right\rangle$和$\left| \psi_1 \right\rangle$。它们的内积是$\left\langle \psi_0 | \psi_1 \right\rangle$ 。如果我们对两者应用相同的幺正 U ，结果状态的内积是完全相同的,

\left( \left\langle \psi_0 \right| U^\dagger \right) \left( U \left| \psi_1 \right\rangle \right) = \left\langle \psi_0 \right|U^\dagger U\left| \psi_1 \right\rangle = \left\langle \psi_0 | \psi_1 \right\rangle.

这个性质为我们提供了一种思考这些门的有用方法。这意味着对于任何为我们的系统提供标准正交基的状态集合 \{\left| \psi_j \right\rangle \} ，状态集合 \{\left| \phi_j \right\rangle = U \left| \psi_j \right\rangle \} 也将是标准正交基。酉可以被认为是这些基之间的旋转，可以相应地写成

U = \sum_j \left| \phi_j \right\rangle \left\langle \psi_j \right|.

这本质上是描述经典布尔门行为的“真值表”的量子版本。

另一个重要的矩阵族是厄米特矩阵。这些是不受厄米特共轭影响的

H = H^\dagger.

矩阵 X,Y,Z,H 是你已经见过的厄米特矩阵的例子(巧合的是，它们也是酉矩阵，因为它们是自己的逆矩阵)。

所有酉矩阵和厄米矩阵都具有对角化的性质。这意味着它们可以写成这样的形式

M = \sum_j \lambda_j |h_j\rangle\langle h_j|,

其中 λ_j 是矩阵的特征值， |h_j\rangle 是对应的特征态。

对于一元函数，在对角线形式中应用 U U^\dagger=I 的条件意味着 \lambda_j \lambda_j^* = 1 。因此，特征值总是大小为1的复数，因此可以表示为 e^{ih_j} 对于某个实值 h_j 。对于厄米矩阵，条件 H = H^\dagger 意味着 \lambda_j = \lambda_j^* ，因此所有的特征值都是实数。

因此，这两种矩阵的不同之处在于，一种矩阵的特征值必须是实数，另一种矩阵的复指数必须是实数。这意味着，对于每一个酉，我们可以定义一个相应的厄米矩阵。为此，我们简单地重用相同的特征状态，并使用每个 e^{ih_j} 中的 h_j 作为相应的特征值。

类似地，对于每个厄米特矩阵存在一个酉。我们简单地重用相同的特征态，并对 h_j 求幂来创建特征值 e^{ih_j} 。这可以表示为

U = e^{iH}

这里我们使用了如何对矩阵求幂的标准定义，它正好具有我们需要的性质:保留特征状态并对特征值求幂。

2.3 泡利分解

正如我们在上面看到的，可以完全用外积来表示矩阵。

M= \begin{pmatrix} m_{0,0}&m_{0,1} \\ m_{1,0}&m_{1,1} \end{pmatrix} = m_{0,0} |0\rangle\langle0|+ m_{0,1} |0\rangle\langle1|+ m_{1,0} |1\rangle\langle0|+ m_{1,1} |1\rangle\langle1|

现在我们将看到，也可以完全用泡利算子来表示它们。为此，需要注意的关键是

\frac{1+Z}{2} = \frac{1}{2}\left[ \begin{pmatrix} 1&0 \\0&1 \end{pmatrix}+\begin{pmatrix} 1&0 \\0&-1 \end{pmatrix}\right] = |0\rangle\langle0|,\\\frac{1-Z}{2} = \frac{1}{2}\left[ \begin{pmatrix} 1&0 \\0&1 \end{pmatrix}-\begin{pmatrix} 1&0 \\0&-1 \end{pmatrix}\right] = |1\rangle\langle1|

由此可见， |0\rangle\langle0| 和 |1\rangle\langle1| 可以用单位矩阵和 Z 表示。现在，利用 X|0\rangle = |1\rangle 的属性，我们还可以得到

|0\rangle\langle1| = |0\rangle\langle0|X = \frac{1}{2}(1+Z)~X = \frac{X+iY}{2},\\\\ |1\rangle\langle0| = X|0\rangle\langle0| = X~\frac{1}{2}(1+Z) = \frac{X-iY}{2}.

由于我们有了所有的外积，我们现在可以用它来将矩阵写成泡利矩阵的形式:

M = \frac{m_{0,0}+m_{1,1}}{2}~1~+~\frac{m_{0,1}+m_{1,0}}{2}~X~+~i\frac{m_{0,1}-m_{1,0}}{2}~Y~+~\frac{m_{0,0}-m_{1,1}}{2}~Z.

这个例子是针对一般的单量子比特矩阵，但相应的结果也适用于任意数量量子比特的矩阵。我们只是从观察开始

\left(\frac{1+Z}{2}\right)\otimes\left(\frac{1+Z}{2}\right)\otimes\ldots\otimes\left(\frac{1+Z}{2}\right) = |00\ldots0\rangle\langle00\ldots0|,

然后可以像上面那样进行操作。最后可以证明，任何矩阵都可以表示为泡利矩阵的张量积:

M = \sum_{P_{n-1},\ldots,P_0 \in \{1,X,Y,Z\}} C_{P_{n-1}\ldots,P_0}~~P_{n-1} \otimes P_{n-2}\otimes\ldots\otimes P_0.

对于厄米特矩阵，注意系数 C_{P_{n-1}\ldots,P_0} 这里都是实数。

3.定义普遍性

正如每个量子门可以用酉来表示一样，我们也可以用一个(非常大的)酉操作来描述整个量子计算。这样做的效果是将输入状态旋转到输出状态。

这种情况的一个可能的特殊情况是，输入和输出状态描述了以量子形式表示的位串。每个输入 x 到其输出 f(x) 的映射可以通过一些(可逆)经典计算来描述。因此，任何这样的计算都可以表示为一个酉。

U = \sum_x \left| f(x) \right\rangle \left\langle x \right|.

如果我们能够实现任何可能的酉，这就意味着我们可以实现标准数字计算机意义上的通用性。

另一种特殊情况是输入和输出状态可以描述一个物理系统，我们执行的计算是为了模拟该系统的动力学。这是一个对经典计算机不切实际的重要问题，但却是量子计算机的一个自然应用。在这种情况下系统的时间演化对应于我们应用的酉函数，相关的厄米特矩阵是系统的哈密顿量。因此，实现任何酉都对应于模拟任何时间的演化，以及设计任何哈密顿量的效果。

结合这些见解，我们可以定义量子计算机普及的意义。它只是在任意数量的量子比特上实现任何所需酉的能力。如果我们有了这个，我们知道我们可以重现任何数字计算机可以做的事情，模拟任何量子系统，以及做量子计算机可能做的一切事情。

4.基本门组

我们是否可以从一组基本门构建任何一元，在很大程度上取决于我们可以访问哪些基本门。对于每一种可能的容错量子计算实现，都有一组最容易实现的量子操作。这些门通常由单量子位元门和双量子位元门组成，其中大部分对应所谓的克利福德门。这是一组非常重要的运算，在任何量子算法中，它们都做了很多繁重的工作。

4.1克利福德门

为了理解克利福德门，让我们从一个你已经见过很多次的例子开始:哈达玛。

H = |+\rangle\langle0|~+~ |-\rangle\langle1| = |0\rangle\langle+|~+~ |1\rangle\langle-|.

此门表示使用外部产品，如上所述。当以这种形式表示时，它著名的效果变得很明显:它接受 |0\rangle ，并将其旋转为 |+\rangle 。更一般地说，我们可以说它将z测量的基状态 \{|0\rangle，|1\rangle \} 旋转到x测量的基状态 \{|+\rangle，|-\rangle \} ，反之亦然。

以这种方式，哈达玛的效果是在量子比特周围移动信息。它将之前被x测量值访问的信息与被z测量值访问的信息进行交换。

哈达玛可以与其他门组合执行不同的操作，例如:

H X H = Z,\\\\ H Z H = X.

通过在 X 之前和之后执行哈达玛操作，我们将之前应用于z基状态的动作转移到X基状态。合并后的效果与 Z 相同。类似地，我们可以从哈达玛创建一个 X 和一个 Z 。

类似的行为可以在 S 门及其厄米特共轭中看到，

S X S^{\dagger} = Y,\\\\ S Y S^{\dagger} = -X,\\\\ S Z S^{\dagger} = Z.

这与哈达玛有相似的效果，除了它交换 X 和 Y ，而不是 X 和 Z 。结合哈达玛，我们可以制作一个复合门，在y和z之间移动信息。

这种把泡利变成另一个泡利的特性是克利福德门的标志性特征。对于单量子比特的情况，明确说明:如果 U 是一个克利福德， P 是一个泡利， UP U^{\dagger} 也将是一个泡利。对于厄米特门，比如哈达玛门，我们可以简单地用 UPU 。

单量子比特克利福德门的进一步例子是泡利本身。它们不会改变它们所作用的泡利。相反，他们只是将 −1 的相位分配给与他们与之相反的两个。例如,

Z X Z = -X,\\\\ Z Y Z = -Y,\\\\ Z Z Z= ~~~~Z.

你可能已经注意到，在 S 门的影响中也出现了类似的阶段。通过和泡利相结合，我们可以做一个复合门来取消这个阶段，并交换 X 和 Y 以一种更类似于哈达玛交换 X 和 Z 的方式。

对于多量子比特克利福德门，其定义性质是将泡利的张量积转换为泡利的其他张量积。例如，最著名的双量子比特特克利福德门是CNOT。本章要用到的性质是

{ CX}_{j,k}~ (X \otimes 1)~{ CX}_{j,k} = X \otimes X.

这有效地将 X 从控制量子比特“复制”到目标。

把一个矩阵夹在一个酉和它的厄米特共轭之间的过程叫做该酉的共轭。这个过程会变换矩阵的特征态，但特征值不变。为什么克利福德共轭可以在泡利之间变换的原因是因为所有的泡利都有相同的特征值。

4.2非-克利福德门

克利福德门非常重要，但它们本身并不强大。为了进行任何量子计算，我们需要的不是克利福德门。三个重要的例子是围绕量子比特的三个轴的任意旋转， R_x(\theta)，R_y(\theta)，R_z(\theta) 。

让我们关注 R_x(\theta) 。正如我们上面看到的，任何酉都可以用厄米特矩阵表示成指数形式。我们找到了这扇门

R_x(\theta) = e^{i \frac{\theta}{2} X}.

上一节还向我们展示了酉矩阵和它对应的厄米特矩阵具有相同的本征态。在这一节中，我们看到了由酉变换的共轭变换本征态并保持本征值不变。考虑到这一点，可以证明

U R_x(\theta)U^\dagger = e^{i \frac{\theta}{2} ~U X U^\dagger}.

通过克利福德共轭这个旋转，我们就可以把它转换成同样的绕另一个轴的旋转。因此，即使我们没有直接的方法来执行 R_y(\theta) 和 R_z(\theta) ，也可以使用 R_x(\theta) 和克利福德门的组合来执行。这种将非克利福德门电路与克利福德门电路相结合来增强运算能力的技术在量子计算中得到了广泛应用。

4.3 扩展门组

作为将 R_x(\theta) 与克利福德组合的另一个例子，让我们将其与CNOT共轭。

CX_{j,k} ~(R_x(\theta) \otimes 1)~ CX_{j,k} = CX_{j,k} ~ e^{i \frac{\theta}{2} ~ (X\otimes 1)}~ CX_{j,k} = e^{i \frac{\theta}{2} ~CX_{j,k} ~ (X\otimes 1)~ CX_{j,k}} = e^{i \frac{\theta}{2} ~ X\otimes X}

这将我们简单的单量子比特旋转转换为更强大的双量子比特门。这不仅仅等同于在两个量子比特上独立执行相同的旋转。相反，它是一个能够产生和操纵纠缠态的门。

我们不必就此打住。我们可以使用相同的技巧将操作扩展到任意数量的量子比特。所需要的是CNOT进行更多共轭，以不断将 X 复制到新的量子比特。

此外，我们可以使用单量子比特的克利福德变换不同量子比特上的泡利。例如，在我们的两个量子比特的例子中，我们可以在右边的量子比特上共轭 S ，将那里的 X 变成 Y :

\left( I \otimes S \right) ~e^{i \frac{\theta}{2} ~ X\otimes X}~\left( I \otimes S^\dagger \right) = e^{i \frac{\theta}{2} ~ X\otimes Y}.

有了这些技术，我们可以进行复杂的纠缠操作，这些操作可以作用于任意数量的量子比特

U = e^{i\frac{\theta}{2} ~ P_{n-1}\otimes P_{n-2}\otimes...\otimes P_0}, ~~~ P_j \in \{I,X,Y,Z\}.

这一切都表明，将单量子比特和双量子比特的克利福德门与围绕x轴的旋转结合起来，可以为我们提供一系列强大的可能性。剩下要证明的是，我们可以用它们做任何事情。

5.证明普遍性

至于经典计算机，我们将需要将这个大任务分成可管理的块。我们需要找到一组基本的门来实现这一点。正如我们将看到的，上一节的单量子比特门和双量子比特门已经足够完成这项任务。

假设我们想实现酉

U = e^{i(aX + bZ)},

但是我们仅有的门是 R_x(\theta) = e^{i \frac{\theta}{2} X} 和 R_z(\theta) = e^{i \frac{\theta}{2} Z} 。解决这个问题的最好方法是使用欧拉角。但让我们考虑一种不同的方法。

U 的指数中的厄米特矩阵就是 R_x(\theta) 和 R_x(\theta) 旋转的矩阵之和。这表明解决我们问题的方法很简单:我们可以应用 R_z(2b) = e^{i bZ} 后跟 R_x(2a) = e^{i a X} 。不幸的是，由于我们计算的是非交换矩阵的幂，这种方法是行不通的。

e^{i a X} e^{i b Z} \neq e^{i(aX + bZ)}

不过，我们可以使用如下修改后的版本:

U = \lim_{n\rightarrow\infty} ~ \left(e^{iaX/n}e^{ibZ/n}\right)^n.

在这里，我们将$U$分成$n$小块。对于每个切片，这是一个很好的近似值

e^{iaX/n}e^{ibZ/n} = e^{i(aX + bZ)/n}

这个近似的误差是 1/n^2 。当我们合并 n 切片时，我们得到了目标酉的近似，其误差范围为 1/n 。因此，通过简单地增加切片的数量，我们可以得到接近所需的 U 。创建序列的其他方法也可以得到目标酉的更精确版本。

这种方法的好处在于，它可以用于复杂的情况，而不仅仅是单个量子比特。例如，考虑一元函数

U = e^{i(aX\otimes X\otimes X + bZ\otimes Z\otimes Z)}.

我们知道如何从单个量子比特 R_x(\theta) 和两个受控的非量子比特创建酉元 e^{i\frac{\theta}{2} X\otimes X\otimes X} 。


qc.cx(0,2)

qc.cx(0,1)

qc.rx(theta,0)

qc.cx(0,1)

qc.cx(0,2)

使用一些哈达玛，我们可以对 e^{i\frac{\theta}{2} Z\otimes Z\otimes Z} 做同样的事情


qc.h(0)

qc.h(1)

qc.h(2)

qc.cx(0,2)

qc.cx(0,1)

qc.rx(theta,0)

qc.cx(0,1)

qc.cx(0,2)

qc.h(2)

qc.h(1)

qc.h(0)

这使我们能够复制新的三量子比特 U 的一小部分:

e^{iaX\otimes X\otimes X/n}e^{ibZ\otimes Z\otimes Z/n} = e^{i(aX\otimes X\otimes X + bZ\otimes Z\otimes Z)/n}

和之前一样，我们可以将这些切片组合在一起，以得到 U 的任意精确近似值。

随着我们增加量子比特的数量，以及需要模拟的项的数量，这种方法继续工作。必须小心确保近似保持准确，但这可以通过需要合理资源的方式实现。增加额外的项来模拟，或增加期望的精度，只需要方法的复杂度多项式地增加。

这种形式的方法可以重现任何一元 U = e^{iH} ，其中 H 可以表示为泡利张量积的和。由于我们之前已经证明了所有矩阵都可以用这种方式表示，这足以表明我们可以重现所有酉。虽然其他方法在实践中可能更好，但本章的主要概念是，肯定有一种方法可以仅使用Qiskit中的基本操作重现所有多量子比特单元。量子普适性可以实现!

这个门并不是唯一一个可以实现通用性的。例如，它可以表明，只有哈达玛和托佛利就足以具有普遍性。也考虑了多种其他的门集，并被证明是通用的，每个都有不同的实现门容错的途径。

本书中讨论的所有内容都遵循计算的电路模型。然而，电路模型并不是量子计算的唯一通用模型。还有其他形式的量子计算，如绝热量子计算或基于测量的量子计算。它们的普适性意味着已经被证明在多项式时间和资源内存在从电路模型到这些其他计算模型的映射。这些其他模型通常利用其他量子力学特性来进行计算。虽然存在这些其他形式的量子计算，但重要的是要注意，每种形式的好处只涉及物理和硬件问题。由于量子计算的通用模型可以执行任何量子算法，因此我们只需要坚持讨论电路模型，而可以忽略其他通用模型。

还有其他形式的量子计算，它们并不普遍，但适用于特定的应用。例如，量子退火可能对优化和采样问题有用。退火是将金属加热到高温，然后让它慢慢冷却的过程。这个过程会使熔融金属流过金属片的表面并重新分布;改变了金属的许多特性。量子退火在某种意义上类似于物理退火过程。它涉及到将问题编码成某种能量图景，然后让量子态探索这一图景。虽然正常波可能会被困在比周围低的波谷中(局部最小值)，但量子效应增加了量子态在景观中找到真正最低点的速度(全局最小值)。


import qiskit.tools.jupyter

%qiskit_version_table
Qiskit Software Version
Qiskit 0.27.0
Terra 0.17.4
Aer 0.8.2
Ignis 0.6.0
Aqua 0.9.2
IBM Q Provider 0.14.0
System information
Python 3.7.7 (default, May 6 2020, 04:59:01) [Clang 4.0.1 (tags/RELEASE_401/final)]
OS Darwin
CPUs 8
Memory (Gb) 32.0