Quantum Algorithm

2016-01-08

Quantum algorithm

量子算法一般是利用量子的并行性(not really)来达到加速计算的目的。一般的算法会分为以下几个步骤:

  • 制备初态,比如:\(|+\rangle|+\rangle|+\rangle...|+\rangle\)
  • 一些演化初态的操作
  • 读取结果

一般的,输出的结构并不是唯一的,正确的答案通常表现为较大的概率

Deutsch’s problem

对于以下两比特幺正变换: \[ U_f: |x\rangle |y\rangle\rightarrow |x\rangle |y \oplus f(x)\rangle \] 也就是当\(f(x)=1\)的时候翻转第二个qubit。我们的任务是来确定是不是有\(f(0)=f(1)\)。如果在传统的算法中,我们需要访问\(f\)两次,分别输入\(x=0,1\)来验证。但是如果我们被允许输入一个由这些经典状态组成的叠加态,那么一次就够了。

如果第二个Qubit被制备成\(\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle)\),那么 \[ \begin{aligned} U\_f:\|x\rangle \frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle) &\rightarrow \|x\rangle \frac{1}{\sqrt{2}}(\|f(x)\rangle - \|1\oplus f(x)\rangle) \\\ &= \|x\rangle (-1)^{f(x)}\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle) \end{aligned} \]

这样我们就将函数\(f\)独立到了一个由x决定的相位上,如果我们将第一个qubit制备成\(\frac{1}{\sqrt{2}}(\|0\rangle+\|1\rangle)\)这样就有

\[ U\_f: \frac{1}{\sqrt{2}}(\|0\rangle+\|1\rangle)\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle)\rightarrow \\\ \frac{1}{\sqrt{2}}[(-1)^{f(0)}\|0\rangle + (-1)^{f(1)}\|1\rangle]\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle)\\\ = \frac{1}{2}[((-1)^{f(0)}+(-1)^{f(1)})\|+\rangle+((-1)^{f(0)}-(-1)^{f(1)})\|-\rangle]\|-\rangle \]

最后我们对第一个比特在下面一组基上测量: \[ \|\pm\rangle=\frac{1}{\sqrt{2}} (\|0\rangle\pm \|1\rangle) \]

为啥我推出来是反的? 当函数平衡的时候\((f(0)\neq f(1))\),我们总能得到\(\|+\rangle\),相反为常数时\((f(0)=f(1))\)我们得到\(\|-\rangle\)

Deutsch-Josza algorithm

对于函数\(f:{0,1}^{n}\rightarrow {0,1}\),类似Deutsch问题的方法

Hadamard变换: \[ \mathbf{H}^{(n)}=\mathbf{H}\otimes\mathbf{H}\otimes ... \otimes\mathbf{H}\otimes\mathbf{H} \]

\[ H^n: \|x\rangle\rightarrow\prod\_{i=1\dots n}(\frac{1}{\sqrt{2}}\cdot \sum{y\_i}) \] - 对每一个qubit做Hadamard变换 \[ \|0\rangle^n \|1\rangle \rightarrow (\frac{1}{2^{n/2}}\cdot \sum\_{x=0}^{2^n-1}\|x\rangle)\cdot \frac{1}{\sqrt{2}}(\|0\rangle - \|1\rangle) \] - 最后一个qubit作为寄存比特来提供信息 - 做n-cntrolled unitary \(U\_f\) transformation

\[ U\_f: \|x\rangle \|y\rangle\rightarrow \|x\rangle\|y\oplus f(x)\rangle\\\ \rightarrow (\frac{1}{2^{n/2}}\cdot\sum^{2^n-1}\_{x=0} (-1)^{f(x)}\|x\rangle)\cdot \frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle) \]

  • 对除了最后一个以外的qubit做hadamrd变换 \[ (\|0\rangle^n \|1\rangle)\rightarrow (\frac{1}{2^{n/2}}\sum\_{x=0}^{2^n-1}\|x\rangle)\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle)\\\ \rightarrow (\frac{1}{2^{n/2}}\sum\_{x=0}^{2^n-1}(-1)^{f(x)}\|x\rangle)\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle)\\\ \rightarrow (\frac{1}{2^n}\sum\_{x=0}^{2^n-1}\sum\_{y=0}^{2^n-1}(-1)^{f(x)}(-1)^{x\cdot y}\|y\rangle)\frac{1}{\sqrt{2}}(\|0\rangle-\|1\rangle) \] 然后计算合,如果\(y=0\)那么就有 \[ \frac{1}{2^n}\sum\_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x\cdot y} = (-1)^{f(x)}\delta\_{y,0} \] 这样我们知道如果f是常数,那么我们测到\(\|y=0\rangle\)的概率为1,如果f平衡那么测到\(\|y=0\rangle\)是0

Grover search algorithm

在一个无序的数据库里寻找某一特定的物体(item)满足一些条件。(有序更简单) \[ f\_{\omega}(x) = 0,x\neq \omega\\\ f\_{\omega}(x) = 1,x= \omega \]

先定义一个类似与Deutch-Josza算法的黑盒子 \[ U\_{f\_{\omega}}:\|x\rangle \|y\rangle \rightarrow \|x\rangle \|y \oplus f(x)\rangle \] 然后,做这样的操作 \[ U\_{f\_{\omega}}:\|x\rangle (\|0\rangle - \|1\rangle) \rightarrow (-1)^{f\_{\omega}}\|x\rangle(\|0\rangle-\|1\rangle) \] 那么这个变换对x就是 \[ U\_{\omega}:\|x\rangle\rightarrow (-1)^{f\_{\omega}}\|x\rangle\\\ U\_{\omega}: I - 2 \|\omega\rangle \langle\omega\| \] 再定义另外一个变换 \[ U\_s:2\|s\rangle\langle s\|-I \] 这里,\(\|s\rangle=1/\sqrt{N}\cdot \sum\_{x=0,1,\dots,2^{N-1}}\|x\rangle\)

然后定义grover算法的算子 \[ R\_{grov}=U\_s\cdot U\_{\omega} \]

\(R\_{grov}\)的意义 将态\(\|s\rangle\)朝着末态\(\|\omega\rangle\)在由\(\|s\rangle\)\(\|\omega\rangle\)决定的平面上旋转\(2\theta,\quad\quad \sin{\theta}=\frac{1}{\sqrt{N}}=\langle s\|\omega\rangle\)

定义\(\sum\_{x}'\)表示所有搜索问题解的合,\(\sum\_{x}''\)表示所有其它的基的合 \[ \begin{aligned} &\|\alpha\rangle \equiv \frac{1}{\sqrt{N-M}}\sum\_{x}'' \|x\rangle \\\ &\|\beta\rangle \equiv \frac{1}{\sqrt{M}}\sum\_{x}' \|x\rangle\\\ &\|\phi\rangle = \sqrt{\frac{N-M}{N}} \|\alpha\rangle +\sqrt{\frac{M}{N}}\|\beta\rangle \end{aligned} \] 如果O是\(\|x\rangle \rightarrow (-1)^{f(x)}\|x\rangle\),那么就可以把O看作是对\(\|\alpha\rangle\)\(\|\beta\rangle\)定义的平面上的向量\(\|\alpha\rangle\)进行了一次反射,可以很巧妙地理解G,即\(O(a\|\alpha\rangle + b\|\beta\rangle)=a\|\alpha\rangle - b\|\beta\rangle\)。类似地,\(2\|\psi\rangle\langle\psi\|-I\)也执行了一次反射,将\(O\|\psi\rangle\)\(\|\psi\rangle\)为对称轴进行了一次反射。两个反射的积是一次旋转。所以 \[ G^k \|\psi\rangle = \cos{((2k+1)\theta)}\|\alpha\rangle+\sin{(2k+1)\theta}\|\beta\rangle \]

当运行了T步之后,应该更加接近\(\pi/2\)就有\((2T+1)\theta\approx\pi/2 \Rightarrow 2T+1\approx \pi/2\theta\)当N足够大,就有\(T=\frac{\pi\sqrt{N}}{4}\)

对多个解的情况应将\(\|\omega\rangle\)改为\(\frac{1}{\sqrt{r}}(\sum\_{i=0,1,\dots,r}\|\omega\_i\rangle)\)r是解的数量

Simon算法

对函数 \[ f:{0,1}^n \rightarrow {0,1}^m \] 有一个未知的周期r,并且r满足\(1\ll r \ll 2^n\),就有 \[ f(x) = f(x+mr) \] m是使得\(x\)\(x+mr\)属于\({0,1,2,\dots,2^n-1}\)的任意整数,我们的目标是找出周期r 对于经典的情况,_如果r是\(2^{n/2}\)阶的,那么我们就要查找至少查找\(2^{n/4}次才能找到两个相同的值来确定周期\)_(阶是什么意思?)

QFT

QFT定义为一组正交基上的线性算子,在基态上作用为 \[ \|j\rangle \rightarrow \frac{1}{\sqrt{N}} \sum\_{k=0}^{N-1} e^{2\pi ijk/N}\|k\rangle \]

或者可以写成 \[ \sum\_x f(x)\|x\rangle \rightarrow \sum\_y \frac{1}{\sqrt{N}} \sum\_x e^{2\pi i xy/N} f(x)\|y\rangle \]

上面式子在\(N=2^{n}\),并将状态j编码为二进制的小数也就是\(j=j\_1/2^{n-1}+j\_2/2^{n-2}+\dots+j\_n 2^0\),为了方便起见,记\(0.j\_l j\_{l+1}\dots j\_m=j\_l/2 + j\_{l+1}/4+\dots +j\_m/2^{m-l+1}\)

QFT的积形式: \[ \begin{aligned} \|j\rangle &\rightarrow \frac{1}{\sqrt{2^n}} \sum\_{k=0}^{N-1} e^{2\pi ijk/2^n}\|k\rangle\\\ &= \frac{1}{2^{n/2}}\sum\_{k\_1=0}^{1}\dots\sum\_{k\_n=0}^{1} e^{2\pi ij(\sum\_{l=1}^{n}k\_l 2^{-l})}\|k\_1\dots k\_n\rangle\\\ &=\frac{1}{2^{n/2}}\sum\_{k\_1=0}^{1}\dots \sum\_{k\_n=0}^{1}\otimes \_{l=1}^{n} e^{2\pi ijk\_l 2^{-l}} \|k\_l\rangle \\\ &= \frac{1}{2^{n/2}}\otimes\_{l=1}^{n} [\sum\_{k\_l=0}^{1}e^{2\pi ijk\_l 2^{-l}}\|k\_l\rangle]\\\ &= \frac{1}{2^{n/2}}\otimes\_{l=1}^{n} [\|0\rangle +e^{2\pi ij 2^{-l}}\|1\rangle]\\\ \end{aligned} \]

Hadamard gate \[ H: \|x\_k\rangle \rightarrow \frac{1}{2}(\|0\rangle + e^{2\pi i (.x\_k)}\|1\rangle)\\\ \]

\(R\_d\) gate \[ R\_d = \begin{pmatrix} 1 & 0\\\ 0 & e^{i\pi/2^d} \end{pmatrix} \] d是两个qubit之间的距离,注意\(R\_d\)门实现从\(e^{2\pi i 0.j\_1}\)\(e^{2\pi i 0.j\_1 j\_2}\)的转化是因为受\(\|j\_2\rangle\)控制,\(j\_2=1\)才进行\(R\_d\)变换

时间复杂度 \(O(log(N)^2)\)

相位估计(phase estimation)

设酉算子\(U\)具有一个特征值为\(e^{2\pi i \phi}\)的特征向量\(\|u\rangle\),而\(\phi\)的值未知。相位估计算法的目的是要估计\(\phi\)

假定可以制备状态\(\|u\rangle\),并且可以进行受控\(U^{2^j}\)运算的黑箱,j是适当的非负整数。

黑箱的使用表明,相位估计本身并不是一个完整的量子算法,而是一种和其它子程序结合后,可以完成有意义计算任务的子程序或模块

量子相位估计使用两个寄存器。第一个寄存器包含初态为\(\|0\rangle\)的量子比特。如何选择\(t\)和两件事有关:希望精确估计\(\phi\)的位数和相位估计过程希望成功的概率。t对这来那个个量的依赖可以从下面分析中得出

第二个寄存器初态为\(\|u\rangle\),且包含存储\(\|u\rangle\)所需要数目的量子比特。相位估计分为两个阶段。首先,应用图(p204)中的线路。该线路从对第一寄存器应用Hadamard门开始,接着应用受控\(U\)门到第二寄存器,\(U\)以2的次幂自乘,第一寄存器的最终状态是 \[ \frac{1}{2^{t/2}}(\|0\rangle+e^{2\pi i 2^{t-1}}\|1\rangle)(\|0\rangle + e^{2\pi i 2^{t-2}\phi}\|1\rangle)\dots (\|0\rangle + e^{2\pi i 2^0 \phi}\|1\rangle) = \frac{1}{2^{t/2}}\sum\_{k=0}^{2^t-1} e^{2\pi i \phi k}\|k\rangle \]

相位估计的第二阶段是应用逆Fourier变换到第一寄存器。这可以通过反转上面的Fourier变换的线路做到。并可以在\(O(t^2)\)内完成。

确定周期

函数\(f:{0,1}^n \rightarrow {0,1}^n\)有未知的正周期\(r:1\ll r \ll 2^n\)

\[ f(x)=f(x+mr) \]

输入 - 一个执行运算\(U\|x\rangle\|y\rangle = \|x\rangle \|y\oplus f(x)\rangle\)的黑箱 - 一个存储函数值的状态,初始化为\(\|0\rangle\) - 初始化为\(\|0\rangle\)\(t=O(L+log(1/\epsilon))\)的量子比特

输出 最小的\(r>0\)的整数,使得\(f(x+r)=f(x)\)

运行时间 利用U一次,和\(O(L^2)\)个运算,成功概率为\(O(1)\)

过程

\[ \begin{aligned} &(1)\ \|0\rangle \|0\rangle\\\ &(2)\ \rightarrow \frac{1}{\sqrt{2^t}} \sum\_{x=0}^{2^t-1} \|x\rangle \|0\rangle\\\ &(3)\ \rightarrow \frac{1}{\sqrt{2^t}} \sum\_{x=0}^{2^t-1} \|x\rangle \|f(x)\rangle\\\ &\approx \frac{1}{2^t}\sum\_{x=0}^{2^t-1} e^{2\pi ilx/r}\|x\rangle \|\hat{f}(l)\rangle &(4)\ \rightarrow \frac{1}{\sqrt{r}}\sum\_{l=0}^{r-1} \|l/r\rangle \|\hat{f}(l)\rangle \\\ &(5)\ \rightarrow l/r\\\ &(6)\ \rightarrow r \end{aligned} \]

Shor算法

大数因子分解的量子多项式算法。算法核心是利用数论的一些定理,将大数的因子分解转化为求某个函数的周期。

大数因子分解问题:N为已知大奇数,\(N=n\_1*n\_2\),求\(n\_1\)\(n\_2\)。Shor算法的主要步骤如下:

  • 随机取数a(优化:a为正整数,可将分解率相应地提高),\(a<N\),且与N互质,即\(gcd(a,N)=1\)
  • 用辗转相除计算a和N的最大公因数
  • 若最大公因数不是1,结束。否则
  • 找出下面函数的周期 \[ f(x)=a^x mod N \]
    • s
  • \(r\)是奇数,回到第一步
  • \(a^{r/2}\equiv -1 (mod N)\)回到第一步
  • \(a^{r/2}\pm 1\)和N的最大公因数是N的一个非平凡因子