Grover算法——量子搜索算法

假设N个数据中符合条件的数据有M个，则量子搜索算法的复杂度为 $O(\sqrt{\frac{N}{M}})$ ，远小于经典算法的复杂度。

黑箱

下面以N=2为例，介绍黑箱如何标记符合条件的数据。N=2意味着只有两个数据，可以用0和1来表示这两个数据，也就只需要一个量子比特表示。假设 $f(x):x\in {(0,1)}\rightarrow y\in(0,1)$ 是一个函数，若x是符合条件的数据，则f(x) = 1;若x不是符合条件的数据，则f(x) = 0。定义黑箱O具有如下功能：

$O(|x\rangle|y\rangle) = |x\rangle|f(x)\oplus y\rangle$ (1)

其中 $|y\rangle$ 为辅助量子比特。此处，不用 $|y\rangle=0$

$|y\rangle = \frac{|0\rangle-|1\rangle}{2}$ (2)

$O(|x\rangle\frac{|0\rangle-|1\rangle}{2}) = |x\rangle\frac{|0\oplus f(x)\rangle-|1\oplus f(x)\rangle}{2}=(-1)^{f(x)}|x\rangle(\frac{|0\rangle-|1\rangle}{2})$ (3)

黑箱作用前后， $|y\rangle$ 的状态不变，通常可以省略，则黑箱的作用记为

$O(|x\rangle) = |(-1)^{f(x)}|x\rangle$

Grover算法

Grover量子搜索算法是一个迭代的过程，主要思路是从初始状态出发，重复进行多次变换，让符合条件的解的振幅越来越大，最后进行测量，就能以很高概率得到正确的结果。

Grover算法共需要n+1个量子比特，初态为 $|\phi_{0} \rangle=|0\rangle^{\otimes (n+1)}$ 。前n个量子比特组成第一个寄存器，用于存储元素编号；另外1个构成第二寄存器，是辅助量子比特。Grover算法步骤如下：

第一步：使用n个H门作用于第一寄存器演化出元素编号的叠加态，并使用X门和H门作用于第二寄存器演化出量子态 $\frac{|0\rangle-|1\rangle}{2}$ 。 $|\phi_{0} \rangle$ 演化为

$|\phi_{1} \rangle=\frac{1}{\sqrt{n}}\sum_{x=0}^{N-1}|x\rangle(\frac{|0\rangle-|1\rangle}{\sqrt{2}})$

第二步：重复算子G以增大满足条件的解的概率，具体的重复次数之后说，每个算子G可以分为以下四步，量子线路图如图。

（1）使用黑箱算子O将符合条件的解的符号取反；

（2）使用 $H^{\bigotimes n}$ 作用于第一寄存器；

（3）使用条件相移算子 $2|0\rangle^{\bigotimes n}\langle0|^{\bigotimes n}-I$ ，将 $|0\rangle$ 以外的基态 $|1\rangle$ ， $|2\rangle$ ，...， $|N-1\rangle$ 取反；

（4）使用 $H^{\bigotimes n}$ 作用于第一寄存器；

 # Display inline
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, transpile
from qiskit_aer import Aer

import numpy as np
from qiskit.visualization import plot_histogram

circuit = QuantumCircuit(3,3)

#第一步
circuit.x(2)
for i in range(3):
    circuit.h(i)
    
#第二步
circuit.ccx(0,1,2)

#第三步
for i in range(2):
    circuit.h(i)
for i in range(2):
    circuit.x(i)
circuit.cz(0,1)
for i in range(2):
    circuit.x(i)
for i in range(2):
    circuit.h(i)
    
#测量
circuit.measure(0,0)
circuit.measure(1,1)

#绘制线路图
circuit.draw(output = 'mpl')