量子行走作为经典行走的推广, 是量子计算的基础, 被视为实现量子计算的一种主要工具. 量子行走利用量子态的叠加性, 能够实现同时行走在不同线路上的可能性, 因此与经典行走相比, 量子行走的效率有着指数级的增长. 并且行走者位置的概率分布也与经典行走有着截然不同的形式, 这些性质都有利于量子算法的实现. 量子行走最初是由Aharonov等^[1]及Farhi和Gutmann^[2]提出的. 其中Aharonov等^[1]提出了离散时间状态下的量子行走算法; Farhi和Gutmann^[2]提出了连续时间状态下的量子行走算法. 与经典行走相比, 这两种行走方法都提供了加速效果. Godsil等^[3]和Bose^[4]展示了如何将图论的思想应用到量子行走中来实现更好的状态传输; Childs^[5]证明了量子行走可以实现普适的量子计算. 这些成果都体现了量子行走在实际应用中的重要性. 此外, 基于量子行走的许多搜索算法都体现了量子行走在算法领域具有独特的优势^[6-12].

在搜索算法中, Grover算法是第二个量子革命的一个里程碑^[13]. 除了数据库搜索, 它还可以用于求解特征值问题, 这是目前最热门的课题之一. 2010年Childs^[14]提出基于连续时间量子漫步的算法, 在黑箱问题中量子行走成功实现了指数级的加速. Shenvi等^[15]也在超立方体的拓扑知识的基础上提出了基于离散时间量子漫步的搜索算法, 实现了多项式加速效果. 由于搜索算法以及可转化为搜索问题的算法具有广泛适用性的特点, 在这些开创性的工作之后, 学者们又进行了深入的研究^[14,16-23]. 在国内, Long等^[24-26]不断完善优化Grover搜索算法, 他们研究的算法是所有优化的Grover算法中最优的, 又称龙算法^[26]; Zhou等^[27-30]和Sheng等^[31,32]也分别在量子搜索算法和量子计算领域做出了贡献. 考虑到量子计算的优势, 学者们期待大量新的量子算法的出现, 但事实证明这项任务很难, 值得继续研究和探索.

基于量子行走寻找新的算法仍然是持续努力的方向, 本文提出了一种基于置换群的空间量子行走搜索算法, 将置换群作为搜素算法和量子行走相结合的桥梁, 目的是减少搜索时间, 提高目标搜索的精度, 提高空间内的搜索效果. 根据置换群中的元素在几何中可以形成环的性质, 将量子行走应用到置换群中, 从而实现在置换群中的量子搜索. 首先通过设置同构映射, 将数据点集合映射到由多个置换群组成的置换集合中的元素, 为了能够实现环上的量子行走, 在同构映射的作用下使数据点集合和置换集合具有一对一的对应关系. 然后, 构造Hilbert空间, 通过控制硬币算子, 给定初始状态, 将搜索空间中的元素作为节点, 进行量子行走. 接着根据函数$ \varPhi(w) = 1 $得到目标点, 并用量子态存储函数值. 最后根据函数的数值形成算法的反馈控制, 以此来判断量子行走的方向以及确定行走的状态. 本文有3个创新点: 1)将数据集同构到置换集, 实现了置换群上的量子行走; 2)多粒子受控的量子行走; 3)增加了反馈控制, 增强算法的可操作性与可控性.

本文结构如下: 第2节简要介绍置换群$ S_{3} $以及环上的量子行走; 第3节分析并实现量子行走搜索算法, 其中包括10个步骤; 第4节对量子行走搜索算法进行时间复杂度分析; 第5节根据时间复杂度进行数值仿真, 直观明了地体现数值结果; 第6节对算法进行总结.

定义2.1 (置换群): 有限集合到自身的一一映射称为一个置换. 有限集合S 上的一些置换组成的集合, 在置换的乘法下所组成的群, 称为置换群^[33]. 任何一个有限群都同构于一个置换群. 因此, 可以把一切有限群都看成置换群. 任一置换可表示成若干不相交循环的乘积, 如$(a_{1},\; a_{2},\;\cdots,\; a_{n}) = $$ \left(\begin{array}{cccc} \alpha_{1} \alpha_{2}\cdots \cdots\alpha_{n-1} \alpha_{n}\\ \alpha_{2} \alpha_{3} \cdots \cdots\alpha_{n} \alpha_{1}\\ \end{array}\right)$称为置换的循环表示. 由于每个循环首尾相连, 因此可以看成是一个闭环.

本文置换群的选择是根据搜索空间中目标态的维数决定的. 由于本文提出的搜索算法是在三维空间中进行的, 因此只对置换群$ S_{3} $进行研究, 若搜索空间是n维, 可以换成置换群$ S_{n} $, 置换群的选择并不会影响算法的时间复杂度. 其中

假设群$ \mathit{G} $是有限群, S是该群的生成集合, 环A和群$ \mathit{G} $存在一一对应关系, 若节点g和$ g^{\prime} $满足$ g^{\prime} = gh $, 则存在一条边$ (g, g^{\prime}) $, 其中$ g\in G $, $ h\in S $. 将环A中元素量子化:

其中, $ {\mathscr{H}}_{S} $为硬币算符所在的Hilbert空间, $ {\mathscr{H}}_{G} $为量子行走所处的位置空间. 环上量子行走的演化算符为$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}}) $, $ {\boldsymbol{I}} $为位置空间的单位算符, $ {\boldsymbol{C}} $为硬币算符, $ {\boldsymbol{T}} $为转移算符, 具体定义如下:

步骤1　应用置换群的对称运算

在介绍量子行走搜索算法之前首先利用对称运算证明置换群$ S_{3} $的每个子群在空间中形成一个闭环, 并且根据旋转角度, 规定群内元素的次序. 为了便于下文解释说明, 将群中元素$ a, b, c $替换为$ 1, 2, 3 $.

对于置换群$ S_{3} $, 有如下保持三角形不变的对称运算: $ (e) $是一个恒等变化; $ (123), (132) $分别为绕中心点逆时针旋转$ \dfrac{2\pi}{3} $和$ \dfrac{4\pi}{3} $; $ (12), (13), (23) $分别为围绕x, y, z轴逆时针旋转π. 每个元素旋转情况如图1所示. 同时可以得到置换群$ S_{3} $的4个子群:

按照元素的旋转角度, 以单位元为起点, 规定每个子群的元素排列顺序. 例如在子群$ H_{1} $中, 第一个元素是e, 第二个元素是$ (12) $. 同理可得其他子群元素之间的排列顺序. 置换群$ S_{3} $的每个子群内, 各元素在三维空间中的旋转关系如图2所示. 在图2中, 对于子群$ H_{1} $, 元素e绕X轴逆时针旋转π到达$ (12) $的位置, 同样地, 元素$ (12) $绕X轴逆时针旋转π到达e的位置; 同理可得其他子群元素之间位置的旋转关系. 从图2还可看出, 置换群$ S_{3} $中每个子群元素之间通过置换群特有的对称运算, 形成了一个闭环.

本节将数据点集与置换群元素通过同构映射实现一一对应, 从而构建量子行走的搜索空间.

步骤2　构建置换群元素新集合

定义3.1 (数据集): 由数据点$ d_{1} $, $ d_{2} $, $\cdots$, $ d_{N} $生成的集合称为数据集D, 其中 n 表示量子态数量, $ N = 2^{n} $.

定义3.2 (置换集): 集合$P \{p (i, j, k)\}, i, j, k\in Z$是由元素$ p (i, j, k) $生成的, 称为置换集. 其中元素$ p(i,\; j,\; k) $通过旋转一定角度变成元素$ p(i,\; j,\; k+1) $, 并且集合P中的元素数量大于等于数据集D中的元素数量.

构建置换集的具体过程: 由置换群的子群$ H_{i} $衍生出子群族$ H_{i}^{j} $. 对于固定的$ i, \;j $, 子群$ H_{i}^{j} $由$ p(i, j, k) $元素生成. 其中$ i = 1, \;2, \;3 $, $ j\in Z $. 对于子群$ H_{i}^{j} $, j表示第j个子群$ H_{i} $, $ k\in Z $表示子群$ H_{i}^{j} $第k个元素. 对于同一个i的值, 只要$ j_{1}\neq j_{2} $, 则$ H_{i}^{j_{1}}\neq H_{i}^{j_{2}} $. 同理, 只要$ k_{1}\neq k_{2} $, 则$ p (i, j, k_{1}) \neq p (i, j, k_{2}) $.

对于集合P和每个子群$ H_{i}^{j} $, 即使包含的元素数与元素的性质相同, 我们也规定, 只要j是不同的, 就被认为是不同的子群. 此外, 对于同一个元素(如e), 只要子群不同, 就被认为是不同的元素. 并且每个子群的元素顺序是逆时针方向. 如对于子群$ H_{1}^{j} $, 指定第一个元素为e, 第二个元素为$ (12) $. 对于$ H_{1}^{j} $的子群, 元素e标记为$ p (1, j, 1) $, $ (12) $标记为$ p (1, j, 2) $. 集合$ P = {p (i, j, k)} $中的每个元素都可以唯一地表示. 元素在置换集中的分布如表1所列.

又因为

因此得到置换集中的元素数满足$N = \displaystyle\sum\nolimits_{i = 1}^{4} j_{i}k_{i} = $$ 2^{n}$, 其中$ j_{i} $表示$ H_{i} $的子群数, $ k_{i} $表示元素数.

步骤3　建立置换集与数据集同构

假设映射$ {\mathscr{F}} $

$ p^{m}(i, \;j, \;k) $上标中的m无意义, 只是为了方便区分说明, 其中$ m = 1, \;2,\;\cdots,\;N $. 接下来证明, 映射$ {\mathscr{F}} $是同构的.

证明　令${\mathscr{F}} (d_{a}) = p^{a} (i, j, c),\;{\mathscr{F}} (d_{b}) = p^{b} (i, j, d).$ 由于$ p^{m} (i, j, d) $的位置只对应于数据点$ d^{m} $, 因此当$ a \neq b $时, $p (i, j, c) \neq p (i, j, d) \Rightarrow d_{a} \neq d_{b}$. 证得$ {\mathscr{F}} $是单射.

又因为$ d_{a} \neq d_{b} $ ($ a \neq b $), 由元素的唯一性得到$ p (i, j, c) \neq p (i, j, d) $, 所以映射$ {\mathscr{F}} $是同构映射.

步骤4　建立量子行走搜索空间

定义3.3 (搜索空间): 空间$ \mathscr{W} $是$ W = D \times P $集合生成, 其元素定义为$ w(d_{m},\; p^{m}(i, j, k)) \in \mathscr{W} $, 被称为搜索空间$ \mathscr{W} $. 每个元素$ w(d_{m}, p^{m}(i, j, k)) $包含排列集中的数据点$ d_{m} $和相应的位置$ p^{m}(i, j, k) $.

重新构造搜索函数$ \varPhi(w) = \varPhi(d) = \{0, 1\} $. 由于 $ p^{m}(i, j, k) $只充当$ w(d_{m}, \;p^{m}(i, j, k)) $中的位置坐标, 该函数对$ p^{m}(i, j, k) $不作用. 这样, 通过函数$ \varPhi(w) = 1 $得到$ w_{{\rm{tar}}}(d_{{\rm{tar}}},\; p^{{\rm{tar}}}(i, j, k)) $, 从而得到目标数据$ d_{{\rm{tar}}} $.

定义3.4 (集合$ W_{-1} $): 搜索空间$ \mathscr{W} $中定义了一个集合$ W_{-1} = \{w_{-1}(-1, \;p(i, j, k)) \} $. 该集合与W的集合相比, 在相同位置$ p(i, j, k) $上, 集合$ W_{-1} $中的数据$ d = 1 $. 集合W与$W _{-1} $的元素对应关系如图3所示.

集合W中的元素和集合$ W_{-1} $中的元素满足下列关系:

其中$ \varOmega_{0} $是转化函数; $ {\boldsymbol{\varphi}}_{{0}} $是矩阵并满足

步骤5　确定量子行走粒子数量

根据置换集合对应的子集数目, 确定量子行走过程中粒子的数量. 再根据前面的假设, 得到子集数$ j_{1}+j_{2}+j_{3}+j_{4} $. 为了方便计算, 选择 $j_{1}+j_{2}+ $$ j_{3}+j_{4}$的最大值$4 \times {\rm{max}}\{j_{1},\; j_{2}, \;j_{3}, \;j_{4} \}$. 在不失一般性的情况下, 令$j = {\rm{max}}\{j_{1},\; j_{2},\; j_{3},\; j_{4}\}$. 得到$j_{1}+ $$ j_{2}+j_{3}+j_{4}\leqslant 4 \times {\rm{max}}\{j_{1}, j_{2}, j_{3}, j_{4}\} = 4 \times j$.

因此, 得到子集的数目是 $ 4 \times j $, 即量子行走过程中粒子的数目是$ 4 \times j $, 其中$0\leqslant j \leqslant {N}/{4}$.

前文得出置换群$ S_{3} $的每个子群在空间中形成一个闭环, 并且置换群也与$ Z_{n} $的加法群同构. 根据已经提出的基于Cayley图的量子行走算法^[34], 可以得到置换群$ S_{3} $上的量子行走.

步骤6　置换群上量子行走

将置换群看成是闭环, 则它的数学描述如下: 假设G是一个有限群, S是该群的生成集合, 置换群$ S_{3} $的元素和群$ {G} $的元素之间存在一一对应关系. 并且如果两个节点g和$g'$满足$g' = gh$, 其中$ g\in G $和$ h\in S $, 则这两个节点之间存在一条边$ (g, gh) $. 将置换群的元素量子化, 则置换群上的量子行走可以有如下定义: 假设$ \mathscr{H}_{S} $是硬币算子所在的Hilbert空间, 它是由态$ {{ |h}}\rangle $, $ h\in S $生成的; $ \mathscr{H}_{G} $是行走者的位置空间, 它是由态$ |{{g}}\rangle $, $ g\in G $生成, 则演化算符$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}}) $ 的硬币算子$ {\boldsymbol{C}} $和转移算子$ {\boldsymbol{T}} $分别定义为

其中, 转移算子的作用是

从(9)式可以得到, 在置换群上进行量子行走时, 以g为起点位置, 当硬币算符为$ h_{1} $时, 行走者会由节点位置g转移到相邻节点$ gh_{1} $, 其中$gh_{1} = $$ g'$. 根据相邻节点的关系, 可以得到:

其中$\oplus$是模$ 2 $加运算或模$ 3 $加运算(在$H_{3} $中).

对群元素进行傅里叶变换^[35], 算子的形式如下:

其中, $\chi_{{{g}}}$为群的特征标, $\chi_{g} =\displaystyle \prod\nolimits_{j = 1}^{n} \omega_{N_{j}}^{\varepsilon, k_{j}}$, $\omega_{{N}_{j}} = {\rm{e}}^{\tfrac{2 \pi}{N_{j}}}$.

将位置空间的基态转换为傅里叶基态: $\left|\widetilde{{{\chi}}}_{{{k}}}\right\rangle= $$ \displaystyle \frac{1}{\sqrt{G}} \sum\nolimits_{k, g \in G} \chi_{g}\left(k^{-1}\right)|{g}\rangle$, 则在$ \mathit{t} $时刻量子行走的状态用傅里叶变换后的基态表示为

其中, 转移算符对傅里叶基态作用后的形式为

可以证明傅里叶基态下, 转移算符只改变基态的振幅.

最后, 得到傅里叶基态下$ \mathit{t} $时刻的振幅为$ \tilde{\psi}_{h, g}(t) $, 通过逆傅里叶变换求解离散时间的振幅:

步骤7　构造Hilbert空间并检测合理性

构造Hilbert空间$ \mathscr{H} = \mathscr{H}_{S}^{4 j}\otimes\mathscr{H}_{G}^{2^{n}}\otimes\mathscr{W} $. 其中$ \mathscr{H}_{S} $是硬币算子所在的Hilbert空间. 两个正交向量$ |{{1}}\rangle $和$ |{{-1}}\rangle $可以用来表示硬币算子的状态; ($ |{{1}} \rangle $表示顺时针方向, $ |{{-1}}\rangle $表示逆时针方向). $ \mathscr{H}_{G} $是量子行走的位置空间; $ 4 j $表示量子态的数量; $ N = 2^{n} $; $ \mathscr{W} $是搜索空间, 用来存储函数值$\varPhi(w) = $$ \{0, 1\}$.

确定硬币算符$ {\boldsymbol{C}} $, 通过硬币算符控制每一步行走. 这一步的目标是保证量子行走的方向一致, 不会往返. 然后通过迭代算子$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $, 进而通过迭代的方法得出迭代算子的数值解. 其中当算子$ {\boldsymbol{\varTheta}} $作用到元素$ w(d_{m}, \;p^{m}(i, j, k)) $时, 可以得到数值$ \delta = \{1, 0 \} $. 根据硬币算子$ {\boldsymbol{C}} $在本文中的作用, 其被定义为

其中$ S = \{-1, 1\} $. 并且令:

根据构建的Hilbert空间, 检验转移算子$ {\boldsymbol{T}} $、转换算子$ {\boldsymbol{\varTheta}} $和迭代算子$ {\boldsymbol{U_{i}} } $是酉算子, 其中$i = $$ 1, \;2,\; 3$. 推导结果如下:

因为转换算子

得到

又因为

根据$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $, 得到:

即${\boldsymbol{U}}_{{{i}}}^{\dagger }{{\boldsymbol{U}}_{{i}}}=\boldsymbol{I}$.

因此通过上述验证过程得出转移算子$ {\boldsymbol{T}} $、转换算子$ {\boldsymbol{\varTheta}} $和迭代算子${\boldsymbol U}_{i}$是酉算子.

步骤8　分析量子行走路径

给定初始态$|{{\psi}}_{{{0}}}\rangle = \dfrac{1}{\sqrt{ {N}/({4j})}}\displaystyle\sum\limits_{1}^{[{N}/({4j})]}|{{-1}} \rangle \otimes |{{0}} \rangle $$ \otimes |{{\delta}}\rangle$, 其中$ \delta = 1, 0 $, 符号$\left[\; \right]$表示取整函数. 通过迭代算子$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $可以得到:

从而控制了在置换群中的量子行走方向. 整个量子行走过程如图4所示.

图4中黄色的圆点表示数据点, 绿色的球体表示空间, 标有数字$ 1, 2, 3 $的蓝色圆圈表示数据点$ p^{m}(i, j, 1) $, $ p^{m+1}(i, j, 2) $, $ p^{m+2}(i, j, 3) $, 位置在某个子群$ H_{i}^{j} $中. 红色的虚线表示运动轨迹, 从$1\to 2\to 3$都是利用反馈控制继续前进的. 当$3\to 1$时, 运动轨迹就是黑色箭头所表示的方向, 通过反馈控制, 发现此方向是被禁止的, 于是设定硬币算符为$ {\boldsymbol{C}^{*}} = \dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) $, 随机选择行走方向(橙色箭头), 进行下一个子群中进行的量子行走.

步骤9　存储函数结果形成反馈控制

当$ \varPhi $作用于元素$ w(d_{m}, \;p^{m}(i, j, k)) $时, 得到函数的值$ \delta = 1 $或$ 0 $, 并将数值存储在量子态中. 其中对于量子态$ |{{1}}\rangle $, 表示所对应的数据d正是目标数据$ d_{{\rm{tar}}} $. 为了形成含有数值结果的量子态集合, 让δ替换$ W_{-1} $集合中的$ -1 $.

更换过程如下:

其中, $\varOmega_{i} ({\boldsymbol{\varTheta}}_{i})$表示转换函数, 使得数据$ d = -1(d) $成为δ, $ w_{mi}^{H_{i}} $表示$ H_{i} $中的一个元素, $ \delta_{mi}^{H_{i}} $表示$ w_{mi} $在函数Φ的作用下的函数值, $ i = 1, 2, 3, 4 $. ${\boldsymbol \phi}_{i}$是矩阵并满足

$ {\boldsymbol{\varphi}_{i}} $是矩阵并满足

当函数$ \varOmega_{i} $(图3中简称为Ω)在进行数据更新时, 存储函数值的量子态会出现3个数值, 分别是$ |{{1}}\rangle $, $ |{{0}}\rangle $和$ |{{-1}}\rangle $. 为了方便说明, 用量子态$ |{{\lambda}}\rangle $表示, 并且建立集合$ W_{\lambda} = \{ (\lambda, \;p(i, j, k))\} $ ($ W_{-1} \rightarrow W_{\lambda} $), 其中$ \lambda = 0, \;1, \;-1 $. 集合W, $ W _{-1} $和$ W _{\lambda} $三者之间的关系变化如图3所示.

步骤10　根据反馈结果判定后续方向

当量子行走进行到某步时, 设此时的迭代次数是t. 当迭代次数是$ t+1 $时, 判断量子行走过程是否继续或者停止. 判断过程如下:

当行走到位置$ p^{m}(i, j, k) $时, 判断相应集合$ W_{\lambda} $对应的数据λ, 如果$ \lambda < 0 $, 量子行走在此环(置换群)中继续进行; 如果$\lambda\geqslant 0$, 量子行走将在此置换群中停止, 设定硬币算符为 $ {\boldsymbol{C}^{*}} = \dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) $, 随机行走到其他置换群的位置.

本文采取多粒子的量子行走, 这样时间复杂度取决于数据点的数量N和量子行走的数量j, 即时间复杂度$ t = t_{{\rm{in}}}+t_{{\rm{out}}} $最终取决于参数j 和N.

对于量子态$|{{\chi}}\rangle = \dfrac{1}{\sqrt{N}}\displaystyle \sum\nolimits_{x = 1}^{N}|{{x }} \rangle \otimes |{{y }} \rangle \otimes |{{\delta }} \rangle$, 其中$ y = 1, 2, 3 $, $ \delta = 0, 1 $, 正交归一化后得到:

其中, M表示目标点的数量.

分析时间复杂度$t_{{\rm{in}}}$, 根据${\boldsymbol{C}} = \displaystyle\sum\nolimits_{h}|{{-1}}\rangle\langle {{h}}|, $$ h\in S$可以得到每一步的硬币算符是

其中, 两个正交向量$ |{{1}}\rangle $和$ |{{-1}}\rangle $可以用来表示硬币的状态. $ |{{1 }} \rangle $表示顺时针方向, $ |{{-1}}\rangle $表示逆时针方向.

通过迭代方法, 可以得到:

由于本文选择的是置换群$ S_{3} $, 因此完成一次置换群上行走次数为$t\leqslant 3$. 又因为在在置换群中完成一次量子行走时, 才进行一次硬币算符为$ {\boldsymbol{C}^{*}} $的量子行走. 即完成一次更换需要的时间$t = t_{{\rm{in}}}+ $$ t_{{\rm{out}}} \leqslant 3+1 = 4$, 因此完成所有行走过程时间复杂度为$ t = t_{{\rm{in}}}+t_{{\rm{out}}} \leqslant 4 t_{{\rm{out}}} $, 得到$ t = 4 t_{{\rm{out}}} $. 所以只需要计算时间复杂度$ t_{{\rm{out}}} $即可.

令

于是得到

令迭代算符$ {\boldsymbol{U}} = {\boldsymbol{T}}({\boldsymbol{C}^{*}}\otimes {\boldsymbol{I}})\otimes {\boldsymbol{\varTheta}} $作用到量子态$ |{{\chi}}\rangle $, 通过计算离散量子行走时刻连续叠加态的振幅得到时间复杂度$ t_{{\rm{out}}} $和参数N的关系.

其中, 当$ t_{{\rm{out}}} $为偶数时:

当$ t_{{\rm{out}}} $为奇数时:

$ \theta_{k} $满足$\sin \theta_{k} = \dfrac{1}{\sqrt{2}} \sin \dfrac{2 \pi k}{N}$.

搜索目的是为了找遍空间中所有子群, 即搜索到目标数据点的概率等于${M}/{N}$.

得到:

由于参数j与N有关, 若取 $ j = \sqrt[3]N $. 求解方程(28)可得

得出关于变量N的数值表达式$t_{{\rm{out}}}(N) = O(\sqrt[^3]N)$, 即得到关于变量N的数值表达式$t(N) = O(\sqrt[^3]N)$.

将本文提出的量子行走搜索算法与Grover搜索算法关于时间复杂度进行对比, 设定参数M = 10, $ N = 200 $, 得到图5所示的对比曲线. 从图5(a)得到量子行走搜索算法所用时间要比Grover搜索算法所用时间短, 即量子行走搜索算法的速率更高; 从图5(b)得到量子行走搜索算法是满足原点条件和下确界条件的, 即满足当$ N = 0 $时, $ t = 0 $; $ N = 1 $时, $ t = 1 $.

为了直观地体现算法的高效性, 下面用两种不同算法进行举例比较: 一个采用标准的Grover-Long算法^[36], 一个采用本文提出的量子行走搜索算法. $ N = 64 $时, Grover-Long算法需要$O(\sqrt[^2]N) = $$ 8$次搜索, 采用本文的方法, 最多需要$O(\sqrt[^3]N) = 4$次搜索.

进而又对参数j对搜索的时间复杂度的影响进行了分析. 选取了参数$ M = 10 $, $ N = 200 $分别对参数$ j = 1 $, $ j = 2 $, $ j = 3 $三条曲线进行分析, 得到图6所示曲线. 从图6(a)得到参数j与时间复杂度呈负相关, 即参数j的取值越大, 所用时间越短, 搜索速率越快; 从图6(b)得到参数j不影响量子行走搜索算法, 且满足原点条件和下确界条件.

最后分析了变量参数j, N与时间复杂度t的关系, 得到数值仿真结果如表2所列. 从表中数据进一步得出, 参数与时间复杂度不是呈负线性关系.

本文基于量子行走提出的搜索算法, 将时间复杂度减少到$O(\sqrt[^3]{N})$. 相对于Grover算法中时间复杂度等价于$O(\sqrt{N})$, 降低了时间消耗; 通过对硬币算符进行控制, 从而控制了整个行走过程, 增加了算法的可控性; 通过增加反馈控制, 使得算法更具有灵活性与可操作性. 最后通过模型仿真, 分析变量参数j与时间复杂度的关系得到, 参数j与时间复杂度呈非线性负相关; 提出的量子行走搜索算法符合零点条件与下确界条件, 即满足当$ N = 0 $时, $ t = 0 $; $ N = 1 $时, $ t = 1 $; 且不受参数j的影响.