ABSTRACT

Grover’s quantum search algorithm is the most famous quantum algorithm in the last twenty years, which exhibits a strong quantum speedup and has been proved not to be able to be outperformed by any classical algorithm. Grover’s quantum search algorithm can be implemented by two equivalent ways, which are circuit model Grover’s algorithm and adiabatic Grover’s algorithm, and the latter is the start point of the paper. We here apply the well-known brachistochrone problem in calculus of variations to investigate and obtain a necessary condition of Grover’s quantum search algorithm, which makes possible to design new efficient quantum algorithms.

Keywords:Grover’s Quantum Search Algorithm, Adiabatic Quantum Computation, Brachistochrone Problem

Grover量子搜索算法中的最速降线问题研究

崔晓东，刘存海，宿德志，柳叶

海军航空大学，航空基础学院，理化教研室，山东 烟台

收稿日期：2018年10月25日；录用日期：2018年11月6日；发布日期：2018年11月13日

摘 要

Grover量子搜索算法是近二十年最著名的量子算法，其已经被证明无法被任何经典算法所超越，展示出极强的量子加速特性。Grover量子搜索算法可以被两种等价的途径所实现，即线路模型Grover算法和绝热Grover算法。本文从绝热Grover算法的角度出发，运用变分法中广为人知的最速降线问题来探讨Grover量子搜索算法，得到了其量子加速特性的一个必要原因，这使得按照该算法的实质来设计其他量子算法成为可能。

关键词 :Grover量子搜索算法，绝热量子计算，最速降线问题

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

1982年，Feynman提出了量子计算机的想法，其目的是克服经典计算机在模拟量子力学过程中经典算法本质上存在的困难 [1] 。1994年，Shor提出了量子计算机的第一个量子算法 [2] ，用于求极大整数的因子分解，其效率明显优于目前的最先进的经典因子分解算法，但无法证明不存在经典算法比Shor量子因子分解算法更高效。1997年，Grover量子搜索算法横空出世 [3] ，打破了人们关于经典算法可以替代量子算法的疑惑 [4] 。Grover量子搜索算法可由量子线路模型和绝热量子计算两种等价的方法实现。简单地讲，量子线路模型通过各种通用量子酉门的时序组合来编码并求解得到最终结果；而绝热量子计算则通过制备初始哈密顿及其基态，并将结果编码进查询哈密顿的基态，在量子绝热定理的保证下来得到结果。本文从绝热量子计算角度来探讨Grover量子搜索算法，得到了其量子加速特性的一个必要原因，这一结果使得按照该算法的实质来设计其他量子算法成为可能。

2. 绝热Grover算法

在数据库中存在N个未排序的条目，这里N极大，目标是在这N个条目中找到指定的一个条目，并且查询的次数最少。处理该问题时，经典算法的平均查询次数为 $O\left(N\right)$ ，而Grover量子搜索算法的平均查询次数仅为 $O\left(\sqrt{N}\right)$ 。对n量子比特Grover量子搜索算法，其可搜索的条目总数为 $N=2^n$ 。按照绝热量子计算的方法 [5] ，初始哈密顿 $H_i$ 为

$H_i=1-|\varphi \rangle \langle \varphi |$

这里1表示单位矩阵，平均态 $|\varphi \rangle =\frac{1}{\sqrt{N}}{\displaystyle \sum _{x=0}^{N-1}|x\rangle }$ 表示初始时各条目 $|x\rangle \left(x=0,1,2,\cdots ,N-1\right)$ 处于等同地位，被搜索到的概率都为 $\frac{1}{N}$ ，同时 $\left\{|x\rangle |x=0,1,2,\cdots ,N-1\right\}$ 构成一组标准正交基。

假定 $|q\rangle \in \left\{|x\rangle |x=0,1,2,\cdots ,N-1\right\}$ 代表要搜索的结果，称为目标态，则将编码该目标态到查询哈密顿 $H_q$ 为

$H_q=1-|q\rangle \langle q|$

则绝热演化哈密顿 $H\left(z\right)$ 就可以描述为

$H\left(z\right)=\left(1-z\right)H_i+z{H}_q$

由于 $|q\rangle$ 与其他 $|x\rangle ,x\ne q$ 都正交，故可将绝热演化哈密顿 $H\left(z\right)$ 在 $|q\rangle$ 与其正交态 $|q^{\perp }\rangle =\frac{1}{\sqrt{N-1}}{\displaystyle \sum _{x\ne q}|x\rangle }$

构成的子空间上表示出来，有

$H\left(z\right)=\frac{1}{2}-\frac{1}{2}\left(\begin{array}{cc}-1+2\left(1-z\right)\left(1-\frac{1}{N}\right)& 2\left(1-z\right)\frac{1}{\sqrt{N}}\sqrt{1-\frac{1}{N}}\\ 2\left(1-z\right)\frac{1}{\sqrt{N}}\sqrt{1-\frac{1}{N}}& 1-2\left(1-z\right)\left(1-\frac{1}{N}\right)\end{array}\right)$

令

$\begin{array}{l}\Delta \left(z\right)=\sqrt{{\left(1-2z\right)}^2+\frac{4}{N}z\left(1-z\right)}\\ \cos \theta \left(z\right)=\frac{1}{\Delta \left(z\right)}\left[1-2\left(1-z\right)\left(1-\frac{1}{N}\right)\right]\\ \sin \theta \left(z\right)=\frac{2}{\Delta \left(z\right)}\left(1-z\right)\frac{1}{\sqrt{N}}\sqrt{1-\frac{1}{N}}\end{array}$

则 $H\left(z\right)$ 有如下紧凑形式

$H\left(z\right)=\frac{1}{2}+\frac{\Delta \left(z\right)}{2}\left(\begin{array}{cc}\cos \theta \left(z\right)& \sin \theta \left(z\right)\\ \sin \theta \left(z\right)& -\cos \theta (z)\end{array}\right)$

能量本征值和相应的本征态分别为

$\begin{array}{l}{E}_{-}=\frac{1}{2}\left(1-\Delta \left(z\right)\right),|E_{-}\rangle =\sin \frac{\theta \left(z\right)}{2}|q^{\perp }\rangle +\cos \frac{\theta \left(z\right)}{2}|q\rangle \\ E_{+}=\frac{1}{2}\left(1+\Delta \left(z\right)\right),|E_{+}\rangle =\cos \frac{\theta \left(z\right)}{2}|q^{\perp }\rangle -\sin \frac{\theta \left(z\right)}{2}|q\rangle \end{array}$

这里我们稍作讨论，当 $z=0$ 时绝热量子系统 $H\left(0\right)=H_i$ ，此时 $|\varphi \rangle =\frac{1}{\sqrt{N}}|q\rangle +\frac{\sqrt{N-1}}{\sqrt{N}}|q^{\perp }\rangle$ 是绝热量子系统的初始基态，相应的系统参数为 $\Delta =1,\cos \theta =-1+\frac{2}{N},\sin \theta =\frac{2\sqrt{N-1}}{N}$ ，当N足够大时，

$\cos \theta \approx -1,\sin \theta \approx 0$ 意味着 $\theta \approx \text{π}$ ；依据量子绝热定理， $|E_{-}\rangle$ 应始终是绝热演化过程的基态，且当 $z=1$ 时绝热量子系统 $H\left(1\right)=H_q$ 并查询到目标态 $|q\rangle$ ，相应的系统参数为 $\Delta =1,\cos \theta =1,\sin \theta =0$ ，意味着 $\theta =0\mathrm{mod}2\text{π}$ 。由于绝热演化的基态 $|E_{-}\rangle$ 是绝热量子计算唯一关心的态，那么我们将它稍作调整，令 $\theta \left(z\right)=\alpha \left(z\right)+\text{π}$ ，则变为

$H\left(z\right)=\frac{1}{2}-\frac{\Delta \left(z\right)}{2}(\begin{array}{cc}\cos \alpha \left(z\right)& \sin \alpha \left(z\right)\\ \sin \alpha \left(z\right)& -\cos \alpha (z))\end{array})$

相应地， $|E_{-}\rangle$ 变为

$|E_{-}\rangle =\cos \frac{\theta \left(z\right)}{2}|q^{\perp }\rangle -\sin \frac{\theta \left(z\right)}{2}|q\rangle$ (1)

这样的好处是当 $z=0$ 时绝热量子系统处于平均态 $|\varphi \rangle$ 上，而当 $z=1$ 时则恰处于所要查询的目标态 $|q\rangle$ 上。下面我们说明由(1)式所描述的绝热基态与变分法中广为熟知的最速降线问题的联系并给出本文结果。

3. 绝热Grover算法与最速降线问题

首先，我们给出Hilbert空间的最速降线问题。

问题：给定N维Hilbert空间 $\mathcal{H}\left({ℂ}^N\right)$ 中的两个量子态 $|{\psi }_1\rangle ,|{\psi }_2\rangle$ ，寻找一条测地线 $|\psi (\cdot )\rangle \in \mathcal{C}:=\left\{C\subset \mathcal{H}\left({ℂ}^N\right)|C\left({\tau }_1\right)=|{\psi }_1\rangle ,C\left({\tau }_2\right)=|{\psi }_2\rangle \right\}$ 使得 $\delta J\left(|\psi (\cdot )\rangle \right)=0$ ，其中 $J\left(|\psi (\cdot )\rangle \right)$ 是关于 $|\psi (\cdot )\rangle$ 的一个指标泛函。

上述问题是变分法中的最速降线问题在Hilbert空间中的一般描述，它的提出与绝热量子计算是有联系的，因为实际上问题中的 $|{\psi }_1\rangle$ 和 $|{\psi }_2\rangle$ 分别对应绝热量子计算的平均态 $|\varphi \rangle$ 和目标态 $|q\rangle$ ，找到了最速降线也就找到了使得平均态 $|\varphi \rangle$ 到达目标态 $|q\rangle$ 的最快路径。问题的核心在与如何确定指标泛函 $J\left(|\psi (\cdot )\rangle \right)$ ，而这需要考察量子态的物理。

由于归一化量子态的物理等价性，即 $|\psi \rangle$ 和 $c|\psi \rangle \left(\left|c\right|=1\right)$ 描述的是同一个物理态，因此对于N维Hilbert 空间 $\mathcal{H}\left({ℂ}^N\right)$ 的归一化非零子集 $\mathcal{N}:=\left\{|\psi \rangle \in \mathcal{H}\left({ℂ}^N\right)-\left\{0\right\}|\langle \psi |\psi \rangle =1\right\}$ 而言，我们需要引入复投影空间 $ℂ\text{P}=\mathcal{N}/\text{U}\left(1\right)$ 及其伴随的投影映射 $\Pi$ ，使得 $\Pi :\mathcal{N}\to ℂ\text{P}$ ，这里 $\text{U}\left(1\right):=\left\{c\in ℂ|\left|c\right|=1\right\}$ 。而复投影空间ℂP上两相邻两物理态 $\Pi \left(|\psi \left(\tau \right)\rangle \right)$ 和 $\Pi \left(|\psi \left(\tau +\text{d}\tau \right)\rangle \right)$ 间的度规恰是Fubibi-Study度规，即

$\text{d}{s}^2=\langle \frac{\text{D}\psi }{\text{d}\tau }|\frac{\text{D}\psi }{\text{d}\tau }\rangle \text{d}{\tau }^2$

这里 $|\frac{\text{D}\psi }{\text{d}\tau }\rangle =|\frac{\text{d}\psi }{\text{d}\tau }\rangle -\langle \psi |\frac{\text{d}\psi }{\text{d}\tau }\rangle |\psi \rangle$ 表示量子态 $|\psi \rangle$ 的局域协变导数。不难验证Fubibi-Study度规是U(1)

局域规范不变的。而连接Hilbert空间中的两个量子态 $|{\psi }_1\rangle$ 和 $|{\psi }_2\rangle$ 间的最速降线 $|\psi (\cdot )\rangle$ 在复投影空间ℂP上的投影 $\Pi \left(|\psi (\cdot )\rangle \right)$ 也应是物理态 $\Pi \left(|{\psi }_1\rangle \right)$ 和 $\Pi \left(|{\psi }_2\rangle \right)$ 间的最速降线，故指标泛函 $J\left(|\psi (\cdot )\rangle \right)$ 可定义为

$J\left(|\psi (\cdot )\rangle \right)={\displaystyle \underset{C}{\int }\text{d}s}={\displaystyle \underset{{\tau }_1}{\overset{{\tau }_2}{\int }}\text{d}\tau \Vert \frac{\text{D}\psi }{\text{d}\tau }\Vert }={\displaystyle \underset{{\tau }_1}{\overset{{\tau }_2}{\int }}\text{d}\tau \sqrt{\langle \frac{\text{D}\psi }{\text{d}\tau }|\frac{\text{D}\psi }{\text{d}\tau }\rangle }}$

这里 $\Vert ·\Vert$ 表示Hilbert空间的范数。计算 $\delta J\left(|\psi (\cdot )\rangle \right)$ 为

$\begin{array}{l}\delta J\left(|\psi (\cdot )\rangle \right)\\ =\delta {\displaystyle \underset{{\tau }_1}{\overset{{\tau }_2}{\int }}\text{d}\tau \sqrt{\langle \frac{\text{D}\psi }{\text{d}\tau }|\frac{\text{D}\psi }{\text{d}\tau }\rangle }}\\ =-{\displaystyle \underset{{\tau }_1}{\overset{{\tau }_2}{\int }}\text{d}\tau \frac{1}{2\sqrt{\langle \frac{\text{D}\psi }{\text{d}\tau }|\frac{\text{D}\psi }{\text{d}\tau }\rangle }}\left[\langle \delta \psi |\frac{{\text{D}}^2\psi }{\text{d}{\tau }^2}\rangle +\langle \frac{{\text{D}}^2\psi }{\text{d}{\tau }^2}|\delta \psi \rangle \right]}\end{array}$

根据变分问题的条件 $\delta J\left(|\psi (\cdot )\rangle \right)=0$ 并考虑归一化条件 $\langle \psi |\psi \rangle =1$ 所给出的约束条件 $\langle \delta \psi |\psi \rangle +\langle \psi |\delta \psi \rangle =0$ ，那么依Lagrange未定乘子法可得，

$\frac{{\text{D}}^2}{\text{d}{\tau }^2}|\psi \left(\tau \right)\rangle +{\omega }^2|\psi \left(\tau \right)\rangle =0$ (2)

其中 ${\omega }^2$ 是待定参数。对方程(2)左乘 $\langle \psi \left(\tau \right)|$ 并利用归一化条件 $\langle \psi \left(\tau \right)|\psi \left(\tau \right)\rangle =1$ ，不难得到

${\omega }^2=\langle \frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }|\frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }\rangle$ ，事实上

$\begin{array}{c}\frac{\text{d}{\omega }^2}{\text{d}\tau }=\langle \frac{{\text{d}}^2\psi \left(\tau \right)}{\text{d}{\tau }^2}|\frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }\rangle +\langle \frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }|\frac{{\text{d}}^2\psi \left(\tau \right)}{\text{d}{\tau }^2}\rangle \\ =\langle \frac{{\text{D}}^2\psi \left(\tau \right)}{\text{d}{\tau }^2}|\frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }\rangle +\langle \frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }|\frac{{\text{D}}^2\psi \left(\tau \right)}{\text{d}{\tau }^2}\rangle \end{array}$

$\begin{array}{c}={\omega }^2\langle \psi \left(\tau \right)|\frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }\rangle +{\omega }^2\langle \frac{\text{d}\psi \left(\tau \right)}{\text{d}\tau }|\psi \left(\tau \right)\rangle \\ =0\end{array}$

因此惨数 ${\omega }^2$ 是常数。进一步地，方程(2)具有局域U(1)规范形式不变性，即当 $|\psi \left(\tau \right)\rangle \mapsto |{\psi }^{\prime }\left(\tau \right)\rangle =e^{i\phi \left(\tau \right)}|\psi \left(\tau \right)\rangle$ 时，方程(2)变为

$\frac{{{\mathrm{D}}^{\prime }}^2}{\text{d}{\tau }^2}|{\psi }^{\prime }\left(\tau \right)\rangle +{\omega }^2|{\psi }^{\prime }\left(\tau \right)\rangle =0$

这里 $|\frac{{\mathrm{D}}^{\prime }{\psi }^{\prime }}{\text{d}\tau }\rangle =|\frac{\text{d}{\psi }^{\prime }}{\text{d}\tau }\rangle -\langle {\psi }^{\prime }|\frac{\text{d}{\psi }^{\prime }}{\text{d}\tau }\rangle |{\psi }^{\prime }\rangle$ 。这表明满足具有局域U(1)规范形式不变性的方程(2)的任意曲

线都是最速降线，它们在复投影空间ℂP上的投影相同。方程(2)在满足量子平移条件 $\langle \psi |\text{d}\psi \rangle =0$ 时又可化为

$\frac{{\text{d}}^2}{\text{d}{\tau }^2}|\psi \left(\tau \right)\rangle +{\omega }^2|\psi \left(\tau \right)\rangle =0$ (3)

从微分几何和量子几何相位的角度讲，满足方程(3)的各量子态都具有与初始量子态相同的相位。令

${\tau }_1=0,{\tau }_2=\frac{3\text{π}}{2\omega }$ ，则对如下常微分方程的边值问题，

$\{\begin{array}{l}\frac{{\text{d}}^2}{\text{d}{\tau }^2}|\psi \left(\tau \right)\rangle +{\omega }^2|\psi \left(\tau \right)\rangle =0\\ |\psi \left({\tau }_1\right)\rangle =|{\psi }_1\rangle ,|\psi \left({\tau }_2\right)\rangle =|{\psi }_2\rangle \end{array}$

这里 ${\omega }^2=\langle \frac{\text{d}{\psi }_1}{\text{d}\tau }|\frac{\text{d}{\psi }_1}{\text{d}\tau }\rangle$ ，其解为所要求的最速降线，即

$|{\psi }^o\left(\tau \right)\rangle =\cos \omega \tau |{\psi }_1\rangle -\sin \omega \tau |{\psi }_2\rangle$ (4)

比较(1)式和(4)式，若令 $\omega \tau =\frac{\alpha \left(z\right)}{2}$ ，则不难发现Grover量子搜索算法有明显的量子加速效果的一个

必要原因是其绝热量子计算方法中的绝热演化基态恰处于一条连接初始平均态 $|\varphi \rangle$ 和目标态 $|q\rangle$ 的最速降线上。

4. 结论及展望

本文从变分法中的最速降线问题的角度出发，利用变分法的成熟方法，得到了绝热Grover算法的绝热基态的演化路径是在由单一目标态和其正交态构成的子二维Hilbert空间中的一条最速降线，这也是Grover量子搜索算法有明显的量子加速效果的一个必要原因。文献 [6] 从量子信息几何的角度采用Wigner-Yanase度规研究了量子混态的情况，当其退化为量子纯态时与我们的结果相同。对于同时查询多个目标的问题，绝热Grover算法也可以实现，文献 [7] 从纯分析的角度给出了解答。然而，与查询单一目标的问题相比，多目标态和其正交态所构成的空间将更为复杂，绝热基态的演化路径也不再是一条曲线，但也可以通过最速降线问题来给出几何解释，只是几何解释的难度将加大。此外，运用变分法中的最速降线方法，我们还可以讨论近几年来热门的量子速度极限等问题 [8] 。

文章引用

崔晓东,刘存海,宿德志,柳 叶. Grover量子搜索算法中的最速降线问题研究
Study on Brachistochrone Problem for Grover’s Quantum Search Algorithm[J]. 应用物理, 2018, 08(11): 455-460. https://doi.org/10.12677/APP.2018.811058

参考文献