量子力学：Fourier Sampling与量子计算

回顾

在经典物理下，$n$个量子的状态可以用一个$n$元字符串表示:$\{0,1\}^n$。但是在量子力学的框架下，$n$个量子的状态需要用$\mathbb{C}^{2^n}$刻画(每个量子的状态可以用$\alpha\left|0\right\rangle+\beta\left|1\right\rangle$刻画,即$\mathbb{C}^2$，$n$个量子需要用$\mathbb{C}^2\otimes\mathbb{C}^2\otimes\cdots\mathbb{C}^2=\mathbb{C}^{2^n}$刻画)。因此量子力学中量子的状态是有指数级的系数数目的。

另外一个量子力学区别于经典力学的方面是量子状态的测量。当我们对一个量子做测量后，量子将坍缩为一个能级状态，测量的结果也是一个能级状态（即概率波变成了粒子）。

对于量子的操作也是有限的，我们将这类变换称为unitary tranformation。其特点是变换矩阵是一个酉矩阵($UU^*=U^*U=I$)。

门

通常我们将对于输入为量子状态，输出为量子状态的操作叫做门。“门”的概念可以参照计算机科学中的理解，例如对于布尔型变量，我们有与门AND、或门OR、异或XOR等，量子中的门诸如Phase flip, bit flip, Hadamard tranform等。

我们知道，在计算机科学中，通过异或门，我们可以实现其它几乎所有的门，这样的门叫做universal gate。在量子力学中，也有这样的门的组合，例如下面的两组门

• X,Z,CNOT,$\frac{\pi}{8}$旋转,……
• H,CSWAP,……

---

CSWAP门

CSWAP门作用在3个量子状态上:当$x=1$时，交换$y,z$,输出$(x,z,y)$;否则输出$(x,y,z)$。CSWAP的矩阵可以写成

$$\begin{bmatrix} 1 & & & & & & & \\ & 1& & & & & & \\ & & 1 & & & & & \\ & & & 1& & & & \\ & & & & 1& & & \\ & & & & & 0 & 1& \\ & & & & & 1& 0 & \\ & & & & & & &1 \end{bmatrix}$$

可以验证CSWAP是一个unitary transformation，并且

$$\mbox{CSWAP}^2=I$$

---

使用这些universal gate可以“逼近”任何酉变换，即对于任意酉矩阵$U$及$\varepsilon>0$，存在由这些门组合成的$U_\varepsilon$，s.t.

$$\|U-U_\varepsilon\|<\varepsilon$$

量子计算是可逆的

由于量子力学的第三公理告诉我们，量子变换是一个酉变换，因此量子计算是一个可逆的过程。考虑函数$f:\{0,1\}^n\rightarrow\{0,1\}^m$,$f^{-1}$不一定存在，但是我们可以由$f$构造出一个可逆函数:

$$g:\{0,1\}^n\rightarrow\{0,1\}^{m+n}$$

$$g(x)=(x,f(x))$$

于是$g$可逆。在量子计算中，输入与输出的长度应该相同(酉变换不丢失或增加bit长度)，因此构造如下所示(用$\left|0\right\rangle$填充位):

但是考虑到$\left|f(x)\right\rangle$之外的量子状态可能对于结果产生干扰，通常我们将$\left|f(x)\right\rangle$复制一份:

Fourier Sampling

Hadamard变换将$\left|0\right\rangle$变为$\left|+\right\rangle$，将$\left|1\right\rangle$变为$\left|-\right\rangle$，如果我们对$n$个qubit的每个bit做Hadamard变换，例如$\left|0000\right\rangle$，我们得到$\left|++++\right\rangle$，展开后我们得到

$$\frac{1}{2^2}\sum\limits_{x\in\{0,1\}^4}\left|x\right\rangle$$

这样的变换叫做Fourier Sampling，用$H^{\otimes n}$表示，我们有

$$H^{\otimes n}\left|u\right\rangle = \frac{1}{2^{\frac{n}{2}}}\sum\limits_{x\in\{0,1\}^n}(-1)^{x\cdot u}\left|x\right\rangle$$

这个变换类似于微积分中的Fourier变换。容易验证

$$H^{\otimes n}H^{\otimes n}=I$$

下面用Fourier Sampling来解决Parity Problem，来阐述经典物理与量子力学的不同。

Parity Problem

已知函数$f:\{0,1\}^n\rightarrow \{0,1\}$,假设存在一个量子状态$u\in\{0,1\}^n$使得$f(x)=u\cdot x$。现在能够通过$f(x)$进行求值，我们需要找出这样的$u$。

在经典计算下，由于$u\in\{0,1\}^n$是一个确定的量，我们需要尝试至少$n$次求值:分别取$\left|100\cdots 0\right\rangle,\left|010\cdots 0\right\rangle,\cdots,\left|000\cdots 1\right\rangle$，依次得到$u_1,u_2,\cdots,u_n$的值。但是在量子计算的框架下，$u$是一个带有概率性的量，我们可以通过下面的算法得到$u$(Bernstein-Vazirani算法):

• 利用下面的酉变换得到$\frac{1}{2^{n/2}}\sum\limits_{x\in\{0,1\}^n}(-1)^{f(x)}\left|x\right\rangle$

• 对于$\frac{1}{2^{n/2}}\sum\limits_{x\in\{0,1\}^n}(-1)^{f(x)}\left|x\right\rangle=\frac{1}{2^{n/2}}\sum\limits_{x\in\{0,1\}^n}(-1)^{x\cdot u}\left|x\right\rangle$做Fourier Sampling，就得到$\left|u\right\rangle$