深度优先搜索在量子人工智能中的应用

在第三章，我们曾经给出了Grover 算法的基本描述，该算法是一个量子搜索算法。本小节的深度优先搜索是基于Grover 算法进行的量子搜索深度优化方法。由于Grover 算法没有使用具体问题的特殊结构信息，对应于一类重要的应用，它为这类问题的求解实际上提供了一个普适的框架，是一种通用算法。Grover 的量子搜索算法比传统算法提供了一个二次加速，计算复杂度取决于对oracle 的查询次数。然而，对于噪声较大的中尺度量子（the noisy intermediate-scale quantum（简写为NISQ），也有翻译为噪声中型量子，或中等规模带噪声量子）的计算机来说，深度是一个更现代的度量标准，因此有研究者提出了量子搜索算法深度优化方法。【69】

1.几个概念的界定

噪声：量子位具有较强的不稳定性，如超导材料量子计算机目前只有80us 左右的稳定持续时间，超出后大概率会坍缩。

中型：100 以内的量子位数。

宽度：物理量子位的个数，用来表示量子计算机的大小。

算法深度：连续门操作的数目，用来表示算法的物理实现时间。

量子体积：宽度与深度的乘积，也可以作为NISQ计算机的一个度量标准。

通用量子门集：能近似任何幺正计算的门的集合。假设量子计算机配备有一个通用量子门集，那么深度是通过通用量子门操作来计算的。量子oracle Uf是由通用量子门集合中的量子门实现的。

最小期望深度：已知深度定义为连续并行门操作的次数，那么用符号α表示oracle 深度Ut与扩散算子Dn深度d（Dn）之比，（各个符号含义见【69】），α 是深度优化的一个重要参数，对于一项搜索算法，α 的实际最小值为1:α≥1。对于同一个问题，不同的数据库大小，比率α 可能不同；我们固定数据库大小n，那么比率α 对于一个问题是常数。已知d（Dn）和α，Grover 算法可以直接映射到深度复杂度。我们将Grover 算法的最小期望深度（Mininal Expect⁃ed Depth，简称MED）定义为：

如果oracle 可以用多项式深度d（Ut）=O（nk）来构造，那么Grover 算法的MED 可以按O（nk2n/2）来表示（假设k>1）。Grover 的算法在oracle 复杂度方面是最优的，最小期望迭代次数jexp也是最优的，因而尺度O（nk2n/2）对于深度复杂性也是最优的。然而如果前面公式中的α 是限定的，那么公式（8.2）里面的dG（α）就不是最优的。【69】

2.深度优化方法

由于局部扩散算子Dm 比全局扩散算子Dn 有较低的深度，因此最优化的思想就是用局部扩散算子替换全局扩散算子。全局Grover 算子Gn不能直接用局部Grover 算子Gm来替换，因为二者的顺序很重要。假设我们有下列数列：

其中（j1, j2…，jq）是一些非负整数，我们有针对oracle 的查询总数：

为了消除Sn，m（j1, j2…，jq）中符号表示的歧义性，我们约定最后一位jq一直为局部Grover 算子的数目。

从而我们也就可以定义Sn，m（j1, j2…，jq）算法的深度。通过定义一个新的MED（最小期望深度）(www.xing528.com)

其中{j1，j2，…，jq}为非负整数，我们可以像Grover 算法那样最小化期望深度。我们也能优化m 的值（正数）m<n，m 最小取值为2。这里d1（α）中的下标1 表示我们找到的目标状态为一级，也就是说，算法一直到最后也没有测量。在量子电路模型中，一级算法意味着只有三步：初始化、统一操作和测量。我们也能定义多级算法，它们是前面三个步骤的多个回合（或多次重复）。

3.多级量子搜索算法的深度优化

受层次（也称等级hierarchy）量子局部搜索算法的启发，有研究者提出对多级量子搜索算法进行深度优化，为了描述简单，本文仅讨论二级量子搜索算法。

假设目标状态分为两部分：∣t〉=∣t1〉⊗t2〉，其中t1 的位长为m1，t2 的位长为m2，这里m1+m2=n。搜索算法经过第一个阶段（或第一级回合）后能以较高的概率找到∣t1〉；基于第一阶段的结果，在数据库重新调节，并经过第二阶段后，算法能以较高概率找到∣t2〉（假设第一阶段找到∣t1〉）。

算法步骤如下：

步1 将状态初始化为∣Sn〉（前面公式中已经提到）。

步2 在初始状态∣Sn〉执行顺序操作，见公式（8.7）

局部扩散算子Dm2（前面已经定义）作用于m2量子位。

步5 在新的初始状态下执行顺序操作

这里m′<m2，扩散算子Dm2 作用于∣Sm2〉，而扩散算子Dm′作用于∣Sm2〉的子空间。

步1 到3 是第一阶段，我们以较高概率得到t1。步4 到6 是第二阶段，我们得到目标阶段的剩余量子位，步7 是用来验证的。不同的序列

得到不同的成功概率

从而得到二级搜索算法的MED：

有了二级（也称两阶段）量子搜索算法（具有深度优化的）可以很容易地推广到多级量子搜索算法,关于多级量子搜索算法，可以参看文献【70】。