求图中点度数的量子算法*

郎健翔， 李绿周

中山大学计算机学院，广东 广州 510006

1 引言

属性测试是一个重要且广泛研究的领域，受到经典计算和量子计算社区的广泛关注（Goldreich，2017； Montanaro et al.，2016）.其目的是确定给定对象是否具有预先确定的属性.研究对象包括函数、概率分布、图等.本文关注图的属性.

对于一个N个顶点的图，如果任何经典算法在最坏情况下都需要探查邻接矩阵中的所有条目，以确定某个属性，则该属性被称为难以捉摸的（Rosenberg，1973）.也就是说，在邻接矩阵模型下的经典查询复杂度为Ω(N2).著名的Aanderaa-Karp-Rosenberg 猜想（也称为难以捉摸猜想）认为，任何非平凡的单调图属性都是难以捉摸的.然而，这个猜想目前还没有被证明.令人惊讶的是，在一系列工作（Buhrman et al.，1999； Magniez et al.，2007； Kulkarni et al.，2015）之后，所有非平凡单调图属性的量子查询复杂度的下界被证明为Ω(N)（Aaronson et al.，2021）.这个下界是最优的，因为非平凡单调图属性“至少包含一条边”可以使用Grover算法在O(N)次查询内确定.虽然量子计算领域的大部分关注点都集中在单调图属性上，但非单调图属性在量子模型中的理解还不够充分（一些非单调图属性在（Sun et al.，2004）中被研究）.

在本文中，我们考虑的问题是确定一个图是否具有特定度数的顶点，这是一个难以捉摸且非单调的图属性.更具体的问题描述如下.

问题给定一个N个顶点的无向图G=(V，E)和一个非负整数k，目标是确定图G是否具有度数为k的顶点.如果存在这样的顶点，则找出它.

假设一个图G=(V，E) 可以通过邻接矩阵查询模型进行访问.它的量子版本用OG表示：

1.1 结果和技术

本文旨在探讨使用最少的查询次数来解决上述问题的量子算法.我们的主要结果如下.

定理1对于一个由N个顶点组成的无向图G=(V，E)，可以通过邻接矩阵OracleOG访问该图，同时给定一个正整数k＞0.存在一个量子算法，使用次对OG的查询，如果图中存在度数为k的顶点，则该算法能够找到这样的顶点；否则，算法输出“不存在这样的顶点”.

一种直接解决上述问题的方法是首先使用精确量子计数算法（Brassard et al.，2002）以O(N)的查询次数获取每个顶点的度数，并且借助Grover 搜索在次查询中找到度数为k的顶点.这种方法的开销为).需要注意的是，我们仅需要知道目标顶点是否具有度数k，而不需要知道该顶点的确切度数.因此，我们将提出一种量子算法来确定一个顶点是否具有度数k，然后将上述问题规约为此问题.更一般地，我们可以得到一个有效的量子算法来解决精确计数的判定问题，具体方法如下.

定理2给定一个函数g： [N]→{0，1}，以及满足1 ≤k≤N的整数k，令M=|{x：g(x) = 1} |.则存在一个量子算法，使用次对g的查询，并以至少为1 -δ的概率判断M=k或M≠k.

为了证明定理2，我们将使用量子奇异值转换（QSⅤT）技术（Gilyén et al.，2019）.此外，基于定理2和有限误差输入的量子搜索（Høyer et al.，2003），我们将证明定理1.

1.2 相关工作

寻找顶点度数的经典算法.Goyal et al.（2020）证明了判断一个n个顶点的无向图是否有度为0 或1 或2的顶点是难以捉摸的性质，对于k＞2 的情况下的下界是0.42n2，这改进了之前的下界0.25n2（Balasubra‐manian et al.，1997）.此外，他们还证明了判断一个有向图是否有出度为k（对于非负整数k≤(n+ 1)/2）的顶点是难以捉摸的问题.这改进了之前k＞1 时n(n- 1 -k)/2 的下界（Balasubramanian et al.，1997）.一个非常相关的问题是在查询模型中寻找图中最大度数的顶点.在无向图（Balasubramanian et al.，1997； Goyal et al.，2020）、有向图（Balasubramanian et al.，1997； Goyal et al.，2020）和竞赛图（Balasubramanian et al.，1997； Gutin et al.，2018； Goyal et al.，2020； Beretta et al.，2019）方面取得了一些进展.竞赛图就是将完全无向图的边给定了方向，是社会学、投票等领域中使用的一个非常有用的模型.此外，Dey（2017）给出了在竞赛图中寻找一些明确定义的顶点集的难以捉摸的下界.

图问题上的量子算法.目前大多数解决图问题的量子算法都基于两种查询模型：邻接矩阵和邻接表.其中，邻接矩阵查询模型被用于许多图问题，如最短路径、连通性、最小生成树等等，而邻接表查询模型则被用于某些需要实现全局变换的问题，如判定二分图、判定可遍历性等等.最近，一些新的查询模型也被研究了，如割问题和独立集问题.另外，在量子模型中，也有一些出色的工作涉及到图的性质检测，包括二分图性检测、扩展性检测等等.目前还没有关于量子算法来判断一个图是否有一个特定度数顶点的工作.

2 预备知识

在本文中，定义[N]≔0，1，…，N- 1.我们将使用两个函数：一个是误差函数

另一个是符号函数

接下来，简要介绍两个稍后将会用到的工具.

2.1 量子奇异值变换

量子奇异值变换（QSⅤT，quantum singular value transformation）技术最初在Gilyén et al.（2019）中被提出，为我们设计量子算法提供了一种新方法.然后，参考Martyn et al.（2021）利用 QSⅤT 技术提出了一个统一的框架，解释了大部分已有算法.本文中的算法也将基于 QSⅤT，特别是以下结果.

定理3给定一个酉矩阵U、它的逆U†以及算符如果一个多项式 Poly(a) 满足以下条件：i） deg(Poly(a)) ≤d；ii） 当x∈[-1，1 ]时，|Poly(a)|≤1；iii） Poly(a) 是奇函数，那么我们可以利用 QSⅤT 技术构建一个电路，使得

这个定理类似于Martyn et al.（2021）的定理2，但方向相反.其正确性在Gilyén et al.（2019）中已经暗示.

2.2 有界误差输入上的量子搜索

普通的 Grover 搜索只能在正确定义的oracle 上生效，当对带有误差的oracle 进行查询时，将会失败.于是Høyer et al.（2003）提出了以下有界误差输入的量子搜索技术.

定理4（Høyer et al.， 2003； Ambainis et al.， 2020） 给定n个算法（无论是量子还是经典的），每个算法都以有界的出错概率给出一个布尔值，并且给定一个整数T≥1.那么存在一个量子算法，它使用次查询，并且以常数的概率：如果n个值中至少有T个值为 1，则返回一个对应值为1 的索引；如果没有值为 1，则返回NULL.(当解的数量 [T] 未知时，期望查询次数也为.

3 量子算法

我们将本文考虑的问题规约为确定给定顶点的度数是否为k的问题，这进一步推广为在第 3.1 节中的精确计数判定问题.

3.1 精确计数问题的判定问题

定理2是本文中至关重要的技术结果.

定理2 的证明该证明包括两个步骤：（i）首先构造一个多项式Ploy(x)来近似刻画问题的函数f(x)，（ii）然后针对多项式Ploy(x)，根据定理3构造一个量子电路来实现它.

首先我们定义以下函数：

注意到该函数满足以下条件：

是一个区别M=k还是M≠k的指示器.然后，我们可以构造一个多项式Poly(x)，满足以下条件：

用当前态作为输入查询g的结果为0以1 -δ的概率成立，当M≠k时：

用当前态作为输入查询g的结果为1以1 -δ的概率成立.因此，构造的量子电路可以以至少1 -δ的概率判断M=k是否成立.

3.2 关键引理的证明

本文的目的是证明引理3，该引理说明存在一个期望的多项式Ploy(x)来逼近式（1）中的函数f(x).在此之前，需要使用Low et al.（2017）中的两个引理.

引理1（关于符号函数sgn(x) 的整体逼近（Low et al.，2017）Lemma10） 对任意Δ＞0，x∈R，则函数fΔ，ϵ(x) ≔erf(lx) 满足

引理2（误差函数erf(lx)的多项式逼近（Low et al.，2017）Corollary4） 对任意l＞0，ϵ∈(0，O(1)]，可定义奇次幂的多项式perf，l，n：

使得

① 在Low et al.(2017)中, x ∈[-1,1 ], 但是当x ∈[-2,2 ]时引理也成立.

其中Ij(x)表示第一类修正贝塞尔函数，Tj(x)表示第一类切比雪夫多项式，

现在我们将证明一个引用在定理2证明中的引理.

引理3我们可以高效地构造一个多项式Poly(x)来逼近以下函数

使得

存在fΔ，ϵ(x)和perf，l，n.现在，我们定义以下多项式

当x∈[0，1]时，注意到x±c∈[-2，2 ]，因此有

上述第一个小于号是由引理2得出的；第二个小于号是由

推导出来的，这可以通过引理1中给出的fΔ，ϵ的表达式进行解析验证；第三个小于号成立是因为根据引理1，|fΔ，ϵ(x±c)|≤1.类似地，有

因此，有

第二个小于号成立是因为：i）|Poly(x)|≤1，ii） |perf，l，n(x) - sgn(x)|≤|perf，l，n(x) -fΔ，ϵ(x)|+|fΔ，ϵ(x) -sgn(x)|≤2ϵ.令δ/2 = 6ϵ，因此，性质（iv）得到证明.

最后，容易发现Poly(x)是奇函数，这可以通过perf，l，n是奇多项式这一事实直接验证.因此，证明了性质（i）.

3.3 判断一个图中是否存在度数为 k 的顶点

现在我们可以展示用于确定给定图是否存在度数为k的顶点的量子算法.

推论1给定一个由N个顶点组成的无向图G=(V，E)，可以通过邻接矩阵OracleOG访问该图，同时给定一个正整数k＞0.则对于每个顶点vi∈V，存在一个量子算法Ai，使用次对OG的查询，以至少1 -δ的概率决定vi的度数是否为k.其中δ是给定的概率误差限.

证明设g(x) =OG(vi，x)，其中x∈V.根据定理2，存在一个量子算法，可以决定vi的度数是否为k.

这时，定理1可以由定理4和推论1推导得出.

注1在上述定理中，要求k＞0.当k= 0时，我们也可以构造一个消耗O(N)次查询的量子算法.实际上，如果将式（1）替换为f(x) = sgn(x)，则可以通过类似的思路得到k= 0的算法.

4 结 论