Grover算法思想

@算法简介
Grover算法是相较于经典数据库搜索算法$O(n)$复杂度实现二次加速的量子算法，即复杂度为$O(\sqrt{N})$。

算法本质

Grover算法实质上是求解函数的逆问题的量子算法，即给定计算函数$y=f_1(x)$的黑盒（Orcale算子）和已知$y_0$,去求使函数满足$f_1(x)=y_0$的自变量$x$的值。

算法步骤：

该算法使用两个寄存器，第一个寄存器存储了n个量子比特，第二个寄存器是Oracle的工作空间。

量子态的制备
Step 1：初始化量子态，制备$|0{⟩}^{⨂n}$作为量子系统的初始状态。
Step 2: 第一步的结果使用H门变换为$H^{⨂n}$
Step 3：实施酉变换。首先，对前n量子比特实施H门变换，使其变成均衡叠加态$|\psi ⟩=\frac{1}{\sqrt{N}}{\sum }_{x=0}^{N-1}|x⟩$,其中$|\psi ⟩$包含函数逆问题解的状态$|{\psi }_0⟩$和非函数逆问题解的状态空间$|{\psi }_1⟩$。

1. 应用G迭代算子，分为四步

1.1 Oracle黑盒子的制备阶段（举例说明，此处的Oracle算子设置较为简单，实际环境设置复杂得多）
$y=f_1(x)$
$|00⟩\to 0$ $|01⟩\to 0$

$|01⟩\to 1$ $|11⟩\to 0$
此处只有$|01⟩$使得$f_1(x)=1$ ,其余态都为0，则Grover迭代的目标解为$|01⟩$。
1.2 对量子态制备阶段的叠加状态$|\psi ⟩$应用Oracle操作,查找叠加状态$|\psi ⟩$是否存在函数逆问题解状态。如果存在这个状态，标记这个状态，标记过程为步骤1.3
1.3 实施条件相位移操作，使状态$|01⟩$状态获得-1的相位

​ $|x⟩\to (-1{)}^{f(x)}|x⟩$
设计一个矩阵（等同于Oracle算子），使得对叠加态$|\psi ⟩$ 中使得$f(x)=1$的$x$添加一个负相位（ps做标记），这一步等同于Grover算法的Oracle算子部分
1.4 完成上述过程，对n个量子比特实施H门变换$H^{⨂n}$

一轮迭代完成， G迭代算子整体状态变化过程为：

$H^{⨂n}(2|0⟩⟨0|-I)H^{⨂n}=2|\psi ⟩⟨\psi |-I$

即G迭代算子作用是 $（2|\psi ⟩⟨\psi |-I）O$,（ $O$是Oracle算子）

解空间

即$O=I-2|\tau ⟩⟨\tau |$,状态$\tau$是函数逆问题的解状态。

M是$|\psi ⟩$中隐藏的解的个数，N=$2^n$,计算下列偏转角公式，计算出最优的迭代次数
$\sin \theta /2=2\sqrt{M/N}$ ，
$\cos \theta /2=2\sqrt{N-M/N}$

最终$|\psi ⟩=\sqrt{\frac{N-M}{N}}|\alpha ⟩+\sqrt{\frac{M}{N}}|\beta ⟩$

下面是我写的Matlab代码块

h=1/sqrt(2)*[1 1;1 -1];  %哈达玛门
I=[1 0;0 1];   %单位矩阵I 创建单位矩阵的函数eye(N)
x1=[0 1;1 0];
i2=[0;1;0;0;0;0;0;0];
i1=[0;0;0;0;1;0;0;0];
oracle=(eye(8)-2*kron(i2',i2)-2*kron(i1',i1));  %简单设置设置的oracle算子
c1=kron(h,I);
c1=kron(c1,I);
c2=kron(I,h);
c2=kron(c2,I);
c3=kron(I,I);
c3=kron(c3,h);  
H=c1*c2*c3;     %用做每一个qubit的H门变换  较繁琐
i=H*i0;         %制备好的待测状态
k4=2*kron(i0',i0)-eye(8);
Us=H*k4*H;
G=Us*oracle;   %Us算子和oracle算子
ix=G*H*i0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18