量子计算机的算力可体现为量子计算机可实现并行计算, Grover算法(Quantum Search Algorithm)是量子计算领域的主要算法之一。Grover算法是由Grover于1996年提出的平方根加速的随机数据库量子搜索算法,旨在利用量子计算机进行比经典计算机更快的数据搜索。在数据库足够混乱且没有具体的数据结构限定的条件下,Grover算法可以快速解决从N个未分类的客体中寻找出某个特定个体的问题。除搜索时间远短于经典计算外,其强大之处还在于Grover算法的公式可适用于很多问题,比如:密码学、矩阵和图形问题、优化以及量子机器学习等。本文将从Grover算法的实现原理、应用与实践等方面介绍Grover算法。
## 1.Grover算法理论
Grover算法的量子线路有一个重要的基本单元,也称为Grover迭代。一个完整的Grover量子线路会包含一个或者多个Grover迭代单元。学习Grover算法需要具备基本的线性代数基础、数字电路概念和量子相关基本概念等知识。
假设某个地区人口总数为N,现需从N个人中找到一个特定的目标X。在经典计算机中需要对N个人进行遍历,时间复杂度为O(N),即最好情况下一次即可找到目标人物,最坏情况下需要寻找N次才能找到目标人物X。而利用Grover算法寻找目标X,时间复杂度为O(√N)。
Grover算法搜寻目标对象的逻辑大致为在无序的数据集合中寻找X,首先制备全部量子态的叠加态,然后循环进行操作使得目标态的符号反向(Oracle算符)且态的符号也反向(Grover算符);在执行次操作后,量子态被旋转至目标态;最后测量所得结果概率发现X出现的概率趋近于1,此时即可通过Grover算法找到目标X。一般地,如果想要在N个信息找到对应信息,进行4/pie*√N次操作,进行测量得到的概率趋于1。因此,Grover算法进行无序搜索主要步骤有三个:制备量子态、G迭代、测量。
## 2.Grover算法步骤
Grover算法总体分为三大步骤:制备量子态、标记目标进行相位翻转并放大概率振幅、测量。Grover算法利用量子特性将目标值与其余值进行区分,采用验证是否符合条件的方式而不是线性查找的方式逼近正确答案。
### 2.1量子态制备
首先在量子电路中准备n个搜索用的量子比特,则处于基态的个数为N。将这N个基态从0到N-1开始编号,构成集合{∣i⟩}={∣0⟩,∣1⟩,......∣N−1⟩}。设其中符合搜索条件的有M个,则不符合条件的个数为N-M个。编号后再对每个量子比特基态做Hadamard门变换构造均匀叠加态。此时,将所有不符合条件的N-M个基态叠加,组成一个叠加态的状态向量,记为|α〉;将所有符合条件的M个基态叠加,组成一个状态向量记为|β〉。|α〉与|β〉构成一组正交向量,|φ〉是所有基态无差别叠加的状态:
### 2.2Grover迭代
通过一系列Hadamard门操作创建量子叠加态之后,首先需要构建一个量子门Oracle。Oracle满足O†O = OO† = I,其中I为单位矩阵,O†表示,先对O做转置,再对O中的每个元素取共轭。Oracle主要作用是区分目标数据和其他数据,对量子状态做酉变换改变目标值的相位。具体操作如下公式:
此时,再引入一个判断函数f(x),设如果x满足f(x)=1,则x是符合条件的搜索目标;否则x不是搜索目标,即如果f(x)=0则x不是目标对象。
公式中当f(x)=1符号不变,f(x)=0时符号反向。
以上步骤已经完成标记目标对象操作,接下来需要做G迭代,主要作用是放大概率振幅。通过多次G迭代后,目标概率振幅被放大趋近于1。
其中O为Oracle算符,I为单位算符。实现多次G迭代的作用效果如下图:
### 2.3测量
在做完Grover变换后,对结果进行测量发现搜索目标的概率振幅最大趋近于1,即完成整个搜索过程。Grover算法是一种算法思想,旨在利用量子固有的特性在大量数据中进行搜索。但Grover算法在实际应用中也有一定局限性,比如在实际构造Oracle时,Oracle计算步骤数量超过算法所保存的步骤数量,从而导致Grover算法比经典算法慢;当数据库足够混乱且没有具体的数据结构时,Grover算法才能比经典算法更适用。
## 3.Grover算法应用与实践
Grover算法是量子算法的典型算法之一,如IBM推出的Qiskit、本源量子公司推出的QPanda量子计算编程框架、启科量子的量子编程框架软件QuTrunk均在自主开发的量子产品中实现Grover算法。QuTrunk自主研发的Python量子编程语言框架,包括量子编程API、量子命令转译、量子计算后端接口等,所有支持Python编程的IDE均可安装使用。目前QuTrunk以QuSprout作为后端,还可扩展支持更多后端。QuTrunk对量子编程相关的基本概念做了代码层面的抽象封装和实现,如量子比特和量子门等等概念可对应到QuTrunk框架内相应的python模块。QuTrunk项目为量子编程工作提供量子底层的软件架构和体系,形成一套统一的量子编程规范。
### 3.1 IBM Qiskit Grover算法部分代码示例
Qiskit是IBM发布的一个专为量子电路与算法打造的开源框架,开发者可使用Qiskit用Python编写量子算法。
以下为Qiskit实现Grover算法部分代码示例:
**步骤1:设N=3,制备量子态**
```python
grover=QuantumCircuit(3,3)
grover.h(0)
grover.h(1)
grover.h(2)
```
**步骤2:确定搜索目标并实行相位翻转**
```python
target=input()
if target[-1]=='0':
grover.x(0)
if target[-2]=='0':
grover.x(1)
if target[-3]=='0':
grover.x(2)
```
**步骤3:运行grover算法放大搜索目标概率**
```python
grover.h([0,1,2])
grover.x([0,1,2])
grover.h(0)
grover.ccx(2,1,0)
grover.h(0)
grover.x([0,1,2])
grover.h([0,1,2])
```
**步骤4:进行结果测量**
```
grover.measure([0,1,2],[0,1,2])
```
#![image-5.png](./picture/image-5.png)
### 3.2 本源量子QPanda Grover算法部分代码示例
QPanda是由本源量子开发的开源量子计算编程框架,它可以用于构建、运行和优化量子算法。
以下为Qpanda实现Grover搜索算法代码示例:
**步骤1:设置算法条件**
```python
template <class T>
QProg grover_alg_search_from_vector(const std::vector<T> &data_vec,
ClassicalCondition condition,
std::vector<size_t> &result_index_vec,
QuantumMachine * qvm,
size_t repeat = 2)
QVec measure_qubits;
QProg grover_prog = build_grover_alg_prog(data_vec, condition, qvm, measure_qubits, repeat);
auto c = qvm->allocateCBits(measure_qubits.size());
grover_prog << MeasureAll(measure_qubits, c);
```
**步骤2:测量**
```python
//measure
//PTrace("Strat pmeasure.n");
const double _shot = 2048;
auto result = qvm->runWithConfiguration(grover_prog, c, _shot);
prob_dict _double_result;
for (auto const& _i : result) {
_double_result.emplace(std::make_pair(_i.first, (double)_i.second / _shot));
}
```
**步骤3:输出结果**
```python
//get result
result_index_vec = search_target_from_measure_result(_double_result, measure_qubits.size());
return grover_prog;
QPANDA_END
```
## 4.启科量子QuTrunk Grover算法的应用于实践
### 4.1启科量子QuTrunk产品简介
QuTrunk是启科量子自主研发的量子编程框架,基于Python提供量子编程API,对量子编程相关的基本概念做了代码层面的抽象封装和实现。量子编程相关概念对应到QuTrunk框架内相应的Python模块,比如QCircuit可实现量子线路,Qubit可实现量子比特,Qureg可实现量子寄存器;Command对应每个量子门操作的指令,Backend代表运行量子线路的后端模块,Gate模块里面实现了各类基础量子门操作,下面对这些主要模块做进一步说明:
- QCircuit: 表示量子线路,维护对所有量子比特的各种门操作及操作时序,代表了整个量子算法的实现,在QuSprout编辑器中输入`from QuTrunk.core.circuit import QCircuit, InitState`。
- Qubit:代表单个量子比特,每个量子比特默认持有一个经典比特,方便存放量子比特对测量结果,例如`num_qubits = 15`,输出`print("num_qubits:", num_qubits, "num_elems:", num_elems, "num_reps:", num_reps)`。
- Qureg: 维护若干个量子比特,用于实现一个具体的量子算法。为了获取n量子位量子寄存器的实例,必须以量子位数为参数调用主引擎的函数allocate_qureg(n),代码操作为`qureg=eng.allocate_qureg(n)`。
- Command: 每个量子门操作其背后都会转换成一个基础指令,这些指令按照时间顺序存放在QCircuit中,当整个算法结束或者需要计算当前量子线路的某种状态取值时,这些指令会被发送到指定的后端去执行。
- Backend: 后端模块,用于执行量子线路,支持本地后端,QuBox后端等,可以通过指定backend参数来更改默认的模拟后端。
- Gate: 量子算法基本组成单元,提供各类量子门操作,包括:H, Measure, CNOT, Toffoli, P, R, Rx, Ry, Rz, S, Sdg, T, Tdg, X, Y, Z, NOT, Swap, SqrtSwap, SqrtX, All, C, Rxx, Ryy, Rzz。在QuBranch编辑器中进行们操作所需代码输入为`from QuTrunk.core.gates import H, X, C, Z`。
QuTrunk目前已经完成第一版开发工作,通过接入QuBox(量子计算后端设备)实现量子算法的运行,已预留API接口将可接入真实量子计算设备。
### 4.2启科量子QuTrunk的下载与安装
* 步骤一:下载并安装QuBranch
* 步骤二:点击【查看】-【命令面板】或快捷键Ctrl Shift P
* 步骤三:输入【>quan:一键安装所需要依赖】安装Qutrunk开发包。
### 4.3QuTrunk实现Grover算法步骤
**步骤1 首先在QuBranch中导入随机数模块和QuTrunk中的部分模块**
```python
import math
import random
from numpy import pi
from qutrunk.circuit import QCircuit
from qutrunk.circuit.gates import Measure, All
from qutrunk.circuit.ops import QSP, QAA
```
* 步骤2 调用量子相位准备运算符QSP和量子振幅这么大运算符QAA
```python
class QSP(Operator): ...
class QAA(Operator): ...
```
* 步骤3 运行Grover算法,不断进行G迭代直至搜索出目标值
```python
num_qubits = 10
num_elems = 2**num_qubits
num_reps = math.ceil(pi / 4 * math.sqrt(num_elems))
print("num_qubits:", num_qubits, "num_elems:", num_elems, "num_reps:", num_reps)
sol_elem = random.randint(0, num_elems - 1)
print(f"target state: |{str(sol_elem)}>")
...
QSP(" ") * qureg
QAA(num_reps, sol_elem) * qureg
```
* 步骤4 输出运行结果
从结果中可观察到搜索的量子比特数为10Qubit、量子门数为11726个、总的运行时间为0.2063s(其中QuBox运行时间为0.1982s,QuTrunk运行时间仅为0.0081s)。
```python
Counter(quit=10)
qubits = 10
quantum_gates = 1320
total_time = 0.20626401901245117
qutrunk_time = 0.008100509643554688
backend_time = 0.19816350936889648
```
以上Grover算法中生成随机数目标为303,最终搜索结果概率峰值为0.9927接近于1。在搜索过程中,当此概率出现峰值且第一次下降时即停止搜索,认为已经找到目标值即为303。
```python
...
prob of state |303> = 0.9732419406366319
prob of state |303> = 0.9896710602298116
prob of state |303> = 0.9984565412943175
prob of state |303> = 0.9994612447443189
prob of state |303> = 0.9926694874189682
measure result: 303
```
## 4.结尾
总体而言,Grover算法只有在满足数据未分类的情况下,其计算时间才会优于经典计算。其次,执行Grover算符需要对唯一的量子态做相位翻转,这通常需要一个尺度正比于比特数平方的算法,在实际实现中比较困难并不利于Grover算法实现。然而,Grover算法思想的精髓之处正是利用量子的叠加特性对大量数据进行验证。因此面对足够庞大且没有数据结构的数据库时,Grover算法才能充分发挥其算力优势。启科量子已经自建了量子算法库QuFlower,包括基础、中级、高级三个级别的量子算法,以供程序调用,从而降低量子编程难度。