给定输入x，典型的量子计算机以这种方式计算$f（x）$如
$U_{f} :|x\rangle|0\rangle \longmapsto|x\rangle|f(x)\rangle$
其中$U_{f}$是用来实现函数$f$的幺正矩阵。
假设$U_{f}$是作用在叠加态上的输入。因此$U_{f}$是一个线性算符，它同时作用于构成叠加的所有向量。输出同样是所有结果的叠加；
$U_{f} : \sum_{x}|x\rangle|0\rangle \mapsto \sum_{x}|x\rangle|f(x)\rangle$
也即,当输入是n个态的叠加，$U_{f}$ 就会同时计算n个$f\left(x_{k}\right)(1 \leq k \leq n)$的值。这个特征也即所谓的量子并行性，且为量子计算机提供了巨大的算力。与经典计算机相比，量子计算的优势在于它能充分利用量子并行和量子纠缠。
在大多数量子算法中，幺正变换作用于所有可能状态的叠加。
这种叠加的制备是由作用在态$|00 \ldots 0\rangle=|0\rangle \otimes|0\rangle \otimes \ldots \otimes|0\rangle$中的n-qubit寄存器上的Walsh-Hadamard变换而得到的。变换如下所示：
$\frac{1}{\sqrt{2^{n}}}(|00 \ldots 0\rangle+|00 \ldots 1\rangle+\ldots|11 \ldots 1\rangle)=\frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1}|x\rangle$
此态是编码0到2n – 1之间所有整数的向量的叠加。由Uf的线性性质，就会得到：
$U_{f}\left(\frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1}|x\rangle|0\rangle\right)=\frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1} U_{f}|x\rangle|0\rangle=\frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1}|x\rangle|f(x)\rangle$
值得注意的是，这种叠加是由$2^{n}=e^{n \ln 2}$个态构成的。与此同时，这种叠加会使得在某种计算中量子计算的速度比经典计算快指数倍。
量子计算机的局限性是什么呢？让我们考虑一下CCNOT门。 当且仅当第一和第二量子位都处于$|1\rangle$时，该门翻转第三量子位，否则它将保持第三量子位不变。我们固定第三个输入比特处于$|0\rangle$.如下图所示：第三个比特的输出为$|x \wedge y\rangle$,其中$|x\rangle$和$|y\rangle$分别为第一个和第二量子比特输入态。假设输入态是所有可能态的叠加，而第三个量子位固定为$|0\rangle$.则可以通过Walsh-Hadamard 门，进行实现：
$$
\begin{aligned} U_{\mathrm{H}}|0\rangle \otimes U_{\mathrm{H}}|0\rangle \otimes|0\rangle &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \otimes|0\rangle \\ &=\frac{1}{2}(|000\rangle+|010\rangle+|100\rangle+|110\rangle) \end{aligned}
$$
通过CCNOT门作用在这个态上，我们可以得到：
$$
\begin{aligned} U_{\mathrm{CCNOT}}(U_{\mathrm{H}}|0\rangle \otimes U_{\mathrm{H}}|0\rangle \otimes|0\rangle) &=\frac{1}{2}(|000\rangle+|010\rangle+|100\rangle+|111\rangle) \end{aligned} （equation~A）
$$
这个输出可以被当做是 AND:$|x,y,x \wedge y\rangle$。非常重要的是要注意输出的是纠缠态，并且测量使得量子态投影到真值表的某一行。也即公式A，等式右边的单个项。其中三个比特的测量顺序并不影响结果。对第三个量子位的测量将量子态投影到具有第三量子位的给定值的叠加态上。对剩余的比特进行重复测量，将会导致输出态坍缩致态其中的一个。
在这个阶段，量子计算并不比经典计算有任何优势。这是因为一组测量值只能得到一个结果。更糟糕的是，我们无法选择想要的特定的向量$|x,y,x \wedge y\rangle$.因此，任何量子算法都能运行，以便我们想要观测的特定矢量比其他矢量具有更大的测量概率。这一步没有经典的类比，在量子计算中也非常特殊。处理此特征的编程策略如下：
-
放大我们想要观察的矢量的振幅，从而放大它的概率。该策略在Grover的数据库搜索算法中得到了应用。
-
找到所有f（x）的共同性质。 这个想法被用于量子傅立叶变换，以找到Shor中f的阶数分解算法
现在我们考虑纠缠的性能。假设我们拥有n比特的存贮器，其希尔伯特空间为2^n维。因为每个比特有两个基矢，$|0\rangle$和$|1\rangle$,那么就会有2n 个基矢（$n |0\rangle$’s and $n |1\rangle$’s）张成2^n维希尔伯特空间。假设我们有一个单量子系统，它具体相同的希尔伯特空间。有人可能会认为系统可能会像n-qubit寄存器那样进行相同的量子计算。一个可能的问题是，人们无法测量“第k数据”，而其他数据不受影响。更糟糕的是，需要考虑这个系统需要多少个不同的基矢。该单个系统必须具有许多组的2n个基矢。我们考虑20个自旋为1/2粒子在磁场中的情况。我们可以采用每个粒子自旋向上和自旋向下的能量本征态作为量子位基矢。因此仅仅只会涉及到40个能量本征态。假设我们用某个分子的能量本征态来代替这个寄存器。我们就不得不用到2^20~10^6个本征态。当前的技术是无法对如此多的本征态进行分离和调控的。这些简单的考虑表明，量子算法的多粒子实现需要的基矢数要比单粒子实现的基矢数少的多，因为前者利用纠缠作为计算资源。
参考文献：
1、 M. A. Neilsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000) .
2. Nakahara M, Ohmi T. Quantum computing: from linear algebra to physical realizations[M]. CRC press, 2008.
感谢，Sakura的编辑排版。
本作者已授权量子客独家网络首发，未经许可，禁止转载、摘编。
