求图中点度数的量子算法

郎健翔; 李绿周

doi:10.13471/j.cnki.acta.snus.2023A070

欢迎访问《中山大学学报(自然科学版)(中英文)》！ English Version 维普资讯中国知网万方数据

您当前的位置：

首页 >

文章列表页 >

求图中点度数的量子算法

特约论文 | 更新时间：2024-01-25

- 求图中点度数的量子算法
- Quantum algorithm for finding degrees
- 角色： First author , 第一作者 ,
  
  机构：
  中山大学计算机学院，广东广州 510006
  
  邮箱： langjx3@mail2.sysu.edu.cn
  
  简介：郎健翔（1999年生），男；研究方向：量子计算；E-mail：langjx3@mail2.sysu.edu.cn
  
  暂无本作者相关信息
  郎健翔
  ，
  角色： Corresponding author , 通讯作者 ,
  
  机构：
  中山大学计算机学院，广东广州 510006
  
  邮箱： lilvzh@mail.sysu.edu.cn
  
  简介：李绿周（1981年生），男；研究方向：量子计算；E-mail：lilvzh@mail.sysu.edu.cn
  
  暂无本作者相关信息
  李绿周
  ，
- 中山大学学报(自然科学版)(中英文) 2024年63卷第1期页码：1-9
- 作者机构：
  
  中山大学计算机学院，广东广州 510006
- 作者简介：
  
  郎健翔（1999年生），男；研究方向：量子计算；E-mail：langjx3@mail2.sysu.edu.cn
  李绿周（1981年生），男；研究方向：量子计算；E-mail：lilvzh@mail.sysu.edu.cn
- 基金信息：
  
  国家自然科学基金(62272492);广东省基础与应用基础研究基金(2020B1515020050)
- DOI：10.13471/j.cnki.acta.snus.2023A070
  中图分类号： TP301.6
- 纸质出版日期：2024-01-25，
  
  网络出版日期：2023-12-18，
  
  收稿日期：2023-09-07，
  
  录用日期：2023-11-02
扫描看全文
引用本文

阅读全文PDF
郎健翔,李绿周.求图中点度数的量子算法[J].中山大学学报(自然科学版)(中英文),2024,63(01):1-9.

LANG Jianxiang,LI Lüzhou.Quantum algorithm for finding degrees[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2024,63(01):1-9.
郎健翔,李绿周.求图中点度数的量子算法[J].中山大学学报(自然科学版)(中英文),2024,63(01):1-9. DOI： 10.13471/j.cnki.acta.snus.2023A070.

LANG Jianxiang,LI Lüzhou.Quantum algorithm for finding degrees[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2024,63(01):1-9. DOI： 10.13471/j.cnki.acta.snus.2023A070.

摘要

本文探讨了图属性测试问题的量子加速：对于给定的图和整数 $k$ ，图中是否存在一个度数为 $k$ 的顶点？该问题的量子复杂度在邻接矩阵oracle模型下被证明为 $𝒪 (N \sqrt[]{k})$ ，而其经典复杂度为 $Ω (N^{2})$ ，其中 $N$ 是图中顶点的数量. 为了证明该结果，得出了一个技术性结论，即对于给定的函数 $g : [N] \to {0,1}$ 和整数 $k$ ，存在一个量子算法可以在 $𝒪 (\sqrt[]{N k})$ 次查询内判定 $|\{x : g (x) = 1\}|$ 是否等于 $k$ .文中的结果基于量子奇异值变换（QSVT）和有误差输入的量子搜索技术.

译

Abstract

Quantum speedups for the graph property testing problem is studied： For a given graph and an integer $k$ ， does the graph have a vertex of degree $k$ ？ The quantum complexity of this problem is proven to be $𝒪 (N \sqrt[]{k})$ under the adjacency matrix oracle model， whereas its classical complexity is $Ω (N^{2})$ ， where $N$ is the number of vertexes in the graph. In order to prove the result， a technical result that there exists a quantum algorithm for deciding whether $|\{x : g (x) = 1\}|$ equals $k$ or not in $𝒪 (\sqrt[]{N k})$ queries， for a given function $g : [N] \to {0,1}$ and an integer $k$ is obtained. These results are based on the techniques of quantum singular value transformation（QSVT） and quantum search on bounded-error inputs.

译

关键词

量子奇异值变换; 量子算法; 图属性测试

译

Keywords

quantum singular value transformation; quantum algorithm; graph property testing

译

1 引言

属性测试是一个重要且广泛研究的领域，受到经典计算和量子计算社区的广泛关注（

Goldreich， 2017； Montanaro et al.，2016）.其目的是确定给定对象是否具有预先确定的属性.研究对象包括函数、概率分布、图等.本文关注图的属性.

译

对于一个 $N$ 个顶点的图，如果任何经典算法在最坏情况下都需要探查邻接矩阵中的所有条目，以确定某个属性，则该属性被称为难以捉摸的（

Rosenberg，1973）.也就是说，在邻接矩阵模型下的经典查询复杂度为

$Ω (N^{2})$ .著名的Aanderaa-Karp-Rosenberg猜想（也称为难以捉摸猜想）认为，任何非平凡的单调图属性都是难以捉摸的.然而，这个猜想目前还没有被证明.令人惊讶的是，在一系列工作（Buhrman et al.， 1999； Magniez et al.，2007； Kulkarni et al.，2015）之后，所有非平凡单调图属性的量子查询复杂度的下界被证明为

$Ω (N)$ （Aaronson et al.，2021）.这个下界是最优的，因为非平凡单调图属性“至少包含一条边”可以使用Grover算法在

$𝒪 (N)$ 次查询内确定.虽然量子计算领域的大部分关注点都集中在单调图属性上，但非单调图属性在量子模型中的理解还不够充分（一些非单调图属性在（Sun et al.，2004）中被研究）.

译

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

译

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

译

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

译

$O_{G} |v_{i}> |v_{j}> |b> = \{\begin{array}{l} |v_{i}> |v_{j}> |b>, & i f (v_{i}, v_{j}) \notin E, \\ |v_{i}> |v_{j}> |b \oplus 1>, & i f (v_{i}, v_{j}) \in E, \end{array}$

其中 $(v_{i}, v_{j}) \in E$ 表示顶点 $|v_{i}>$ 和 $|v_{j}>$ 之间存在一条边.

译

1.1　结果和技术

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

译

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

译

一种直接解决上述问题的方法是首先使用精确量子计数算法（

Brassard et al.，2002）以

$𝒪 (N)$ 的查询次数获取每个顶点的度数，并且借助Grover搜索在

$𝒪 (\sqrt[]{N})$ 次查询中找到度数为

$k$ 的顶点.这种方法的开销为

$𝒪 (N \sqrt[]{N})$ .需要注意的是，我们仅需要知道目标顶点是否具有度数

$k$ ，而不需要知道该顶点的确切度数. 因此，我们将提出一种量子算法来确定一个顶点是否具有度数

$k$ ，然后将上述问题规约为此问题.更一般地，我们可以得到一个有效的量子算法来解决精确计数的判定问题，具体方法如下.

译

定理2 给定一个函数 $g : [N] \to {0,1}$ ，以及满足 $1 \leq k \leq N$ 的整数 $k$ ，令 $M = |\{x : g (x) = 1\}|$ . 则存在一个量子算法，使用 $𝒪 (\sqrt[]{N k} l o g (\frac{12}{δ}))$ 次对 $g$ 的查询，并以至少为 $1 - δ$ 的概率判断 $M = k$ 或 $M \neq k$ .

译

为了证明定理2，我们将使用量子奇异值转换（QSVT）技术（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.42 n^{2}$ ，这改进了之前的下界

$0.25 n^{2}$ （Balasubramanian et al.，1997）.此外，他们还证明了判断一个有向图是否有出度为

$k$ （对于非负整数

$k \leq (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, \dots, N - 1$ .我们将使用两个函数：一个是误差函数

译

$e r f (x) = \frac{2}{\sqrt[]{π}} \int_{0}^{x} e^{- η^{2}} d η,$

另一个是符号函数

译

$s g n (x) = \{\begin{array}{l} - 1, & x < 0, \\ 0, & x = 0, \\ 1, & x > 0 . \end{array}$

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

译

2.1　量子奇异值变换

量子奇异值变换（QSVT，quantum singular value transformation）技术最初在Gilyén et al.（2019）中被提出，为我们设计量子算法提供了一种新方法.然后，参考

Martyn et al.（2021）利用 QSVT 技术提出了一个统一的框架，解释了大部分已有算法.本文中的算法也将基于 QSVT，特别是以下结果.

译

定理3 给定一个酉矩阵 $U$ 、它的逆 $U^{†}$ 以及算符 $A_{ϕ} = e^{i ϕ |A_{0}> <A_{0}|}$ 和 $B_{ϕ} = e^{i ϕ |B_{0}> <B_{0}|}$ ，定义 $a = <A_{0} |U| B_{0}>$ . 如果一个多项式 $P o l y (a)$ 满足以下条件：i） $d e g (P o l y (a)) \leq d$ ；ii）当 $x \in [- 1,1]$ 时， $|P o l y (a)| \leq 1$ ；iii） $P o l y (a)$ 是奇函数，那么我们可以利用 QSVT 技术构建一个电路，使得

译

$<A_{0} |[\prod_{t = 1}^{d / 2} U B_{ϕ_{2 t - 1}} U^{†} A_{ϕ_{2 t}}] U| B_{0}> = P o l y (a) .$

这个定理类似于

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 \geq 1$ .那么存在一个量子算法，它使用

$𝒪 (\sqrt[]{n / T})$ 次查询，并且以常数的概率：如果

$n$ 个值中至少有

$T$ 个值为 1，则返回一个对应值为1的索引；如果没有值为 1，则返回

$N U L L$ .

$(当解的数量 [T] 未知时, 期望查询次数也为$

$𝒪 (\sqrt[]{n / T}))$ .

译

3 量子算法

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

译

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

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

译

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

译

首先我们定义以下函数：

译

$\begin{array}{l} f (x) = \frac{1}{2} s g n (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + \frac{1}{2} s g n (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) \\ - \frac{1}{2} s g n (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - \frac{1}{2} s g n (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) \\ = \{\begin{array}{l} - 1, & - \frac{1}{2} (\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}) < x < - \frac{1}{2} (\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}), \\ 1, & \frac{1}{2} (\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}) > x > \frac{1}{2} (\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}), \\ 0, & 其他 . \end{array} (1) \end{array}$

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

译

$\begin{matrix} f (\sqrt[]{\frac{M}{N}}) = \{\begin{array}{l} 1, & M = k, \\ 0, & M \neq k \end{array} \end{matrix}$

（2）

是一个区别 $M = k$ 还是 $M \neq k$ 的指示器. 然后，我们可以构造一个多项式 $P o l y (x)$ ，满足以下条件：

译

（i） $P o l y (x)$ 是奇函数；

译

（ii） $P o l y (x)$ 的次数为 $𝒪 (\sqrt[]{N k} l o g (\frac{12}{δ}))$ ；

译

（iii）当 $x \in [- 1,1]$ 时， $|P o l y (x)| \leq 1$ ；

译

（iv）当 $x = \sqrt[]{\frac{M}{N}}$ 时， $|f (x) - P o l y (x)| \leq \frac{δ}{2}$ .

译

上述条件的证明将在后面的引理3中给出.

译

现在我们将构造一个量子电路来实现 $P o l y (x)$ .设 $|A_{0}> = \sum_{i = 1}^{M} \frac{1}{\sqrt[]{M}} |m_{i}>$ ，其中 $|m_{i}>$ 是满足 $g (m_{i}) = 1$ 的状态.定义 $A_{ϕ}$ 如下：

译

$A_{ϕ} |j> = \{\begin{array}{l} |j>, & f (j) = 1, \\ e^{i ϕ} |j>, & f (j) \neq 1, \end{array}$

如

Yoder et al.（2014）所示，可以通过使用一个或两个Oracle查询来实现

$A_{ϕ}$ . 此外，设

$|B_{0}> = |0>$ ，即全零状态，

$U = H^{\otimes n}$ .不需要查询Oracle即可实现

$B_{ϕ}$ .根据定理3中的变量

$a$ ，我们有

$<A_{0} |U| B_{0}> = \sqrt[]{\frac{M}{N}}$ . 根据定理3，可以构造一个量子电路

$[\prod_{t = 1}^{d / 2} U B_{ϕ_{2 t - 1}} U^{†} A_{ϕ_{2 t}}] U$ ，记作

$U_{Q S V T}$ ，其中

$d = 𝒪 (\sqrt[]{k N} l o g (\frac{12}{δ}))$ ，满足以下条件：

译

$<A_{0}| U_{Q S V T} |B_{0}> = P o l y (\sqrt[]{\frac{M}{N}}) .$

注意到 $|f (\sqrt[]{\frac{M}{N}}) - P o l y (\sqrt[]{\frac{M}{N}})| \leq \frac{δ}{2}$ 和 $f (\sqrt[]{\frac{M}{N}}) = \{\begin{array}{l} 1, & M = k, \\ 0, & M \neq k . \end{array}$ 因此，当 $M = k$ 时，有以下结果：

译

$<A_{0}| U_{Q S V T} |B_{0}> = P o l y (\sqrt[]{\frac{M}{N}}) \geq 1 - \frac{δ}{2} .$

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

译

$<A_{0}| U_{Q S V T} |B_{0}> = P o l y (\sqrt[]{\frac{M}{N}}) \leq \frac{δ}{2} .$

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

译

3.2　关键引理的证明

本文的目的是证明引理3，该引理说明存在一个期望的多项式 $P l o y (x)$ 来逼近式（1）中的函数 $f (x)$ .在此之前，需要使用

Low et al.（2017）中的两个引理.

译

引理1（关于符号函数 $s g n (x)$ 的整体逼近（

Low et al.，2017）^{Lemma 10}）对任意

$Δ > 0$ ，

$x \in R$ ，

$ϵ \in (0, \sqrt[]{2 / (e π)}]$ ，令

$l = \frac{\sqrt[]{2}}{Δ} l o g^{1 / 2} (\frac{2}{π ϵ^{2}})$ . 则函数

$f_{Δ, ϵ} (x) ≔ e r f (l x)$ 满足

译

$\begin{matrix} |f_{Δ, ϵ} (x)| \leq 1, & \underset{|x| \geq Δ / 2}{m a x} |f_{Δ, ϵ} (x) - s g n (x)| \leq ϵ . \end{matrix}$

引理2 （误差函数 $e r f (l x)$ 的多项式逼近（

Low et al.，2017）^{Corollary 4}）对任意

$l > 0$ ，

$ϵ \in (0, 𝒪 (1)]$ ，可定义奇次幂的多项式

$p_{e r f, l, n}$ ：

译

$p_{e r f, l, n} (x) = \frac{2 l e^{- l^{2} / 2}}{\sqrt[]{π}} (I_{0} (l^{2} / 2) x + \sum_{j = 1}^{(n - 1) / 2} I_{j} (l^{2} / 2) {(- 1)}^{j} (\frac{T_{2 j + 1} (x)}{2 j + 1} - \frac{T_{2 j - 1} (x)}{2 j - 1})),$

使得

译

$\underset{x \in [- 2,2]}{m a x} |p_{e r f, l, n} (x) - e r f (l x)| \leq ϵ,$ ^脚注

其中 $I_{j} (x)$ 表示第一类修正贝塞尔函数， $T_{j} (x)$ 表示第一类切比雪夫多项式，

译

$n = 𝒪 (\sqrt[]{(l^{2} + l o g (1 / ϵ)) l o g (1 / ϵ)})$ .

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

译

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

译

使得

译

（i） $P o l y (x)$ 是奇函数；

译

（ii） $P o l y (x)$ 的次数为 $𝒪 (\sqrt[]{N k} l o g (\frac{12}{δ}))$ ；

译

（iii）当 $x \in [- 1,1]$ 时， $|P o l y (x)| \leq 1$ ；

译

（iv）当 $x = \sqrt[]{\frac{M}{N}}$ 时， $|f (x) - P o l y (x)| \leq \frac{δ}{2}$ .

译

证明令 $Δ = \sqrt[]{\frac{k + 1}{N}} - \sqrt[]{\frac{k}{N}}$ ，对于每个 $s g n (x \pm c)$ （其中 $c$ 指代公式（3）中的常数），根据引理1和引理2，存在 $f_{Δ, ϵ} (x)$ 和 $p_{e r f, l, n}$ .现在，我们定义以下多项式

译

$\begin{array}{l} P o l y (x) = \frac{1}{2 (1 + 2 ϵ)} p_{e r f, l, n} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + \frac{1}{2 (1 + 2 ϵ)} p_{e r f, l, n} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) \\ - \frac{1}{2 (1 + 2 ϵ)} p_{e r f, l, n} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - \frac{1}{2 (1 + 2 ϵ)} p_{e r f, l, n} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) . \end{array}$

当 $x \in [0,1]$ 时，注意到 $x \pm c \in [- 2,2]$ ，因此有

译

$\begin{array}{l} P o l y (x) \leq \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + ϵ) + \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + ϵ) \\ - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - ϵ) - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - ϵ) \\ \leq \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + 2 ϵ) + \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + 2 ϵ) \\ \leq \frac{1 + 2 ϵ}{2 (1 + 2 ϵ)} + \frac{1 + 2 ϵ}{2 (1 + 2 ϵ)} = 1 . \end{array}$

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

译

$- f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) \leq 0$

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

译

$\begin{array}{l} P o l y (x) \geq \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) - ϵ) + \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) - ϵ) \\ - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) + ϵ) - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) + ϵ) \\ \geq - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) + 2 ϵ) - \frac{1}{2 (1 + 2 ϵ)} (f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) + 2 ϵ) \\ \geq - \frac{1 + 2 ϵ}{2 (1 + 2 ϵ)} - \frac{1 + 2 ϵ}{2 (1 + 2 ϵ)} = - 1 . \end{array}$

由于 $f_{Δ, ϵ} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) + f_{Δ, ϵ} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) \geq 0$ 可以通过解析验证. 当 $x \in [- 1,0]$ 时，可以对称地证明 $|P o l y (x)| \leq 1$ . 因此，性质（iii）得到验证.

译

当 $x = \sqrt[]{\frac{M}{N}}$ 时，以下条件同时成立：

译

$|x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}| \geq \frac{Δ}{2}$ ，

$|x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}| \geq \frac{Δ}{2}$ ，

$|x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}| \geq \frac{Δ}{2}$ ，

$|x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}| \geq \frac{Δ}{2}$ .

因此，有

译

$\begin{array}{l} |f (x) - P o l y (x)| \leq |(1 + 2 ϵ) P o l y (x) - P o l y (x)| + |(1 + 2 ϵ) P o l y (x) - f (x)| \\ \leq 2 ϵ + \frac{1}{2} |p_{e r f, l, n} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) - s g n (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2})| \\ + \frac{1}{2} |p_{e r f, l, n} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2}) - s g n (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k - 1}{N}}}{2})| \\ + \frac{1}{2} |p_{e r f, l, n} (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - s g n (x - \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2})| \\ + \frac{1}{2} |p_{e r f, l, n} (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2}) - s g n (x + \frac{\sqrt[]{\frac{k}{N}} + \sqrt[]{\frac{k + 1}{N}}}{2})| \\ \leq 6 ϵ . \end{array}$

第二个小于号成立是因为：i） $|P o l y (x)| \leq 1$ ，ii） $|p_{e r f, l, n} (x) - s g n (x)| \leq |p_{e r f, l, n} (x) - f_{Δ, ϵ} (x)| + |f_{Δ, ϵ} (x) - s g n (x)| \leq 2 ϵ$ . 令 $δ / 2 = 6 ϵ$ ，因此，性质（iv）得到证明.

译

将引理1中 $l$ 的表达式代入引理2，我们可以看出 $P o l y (x)$ 的次数是 $𝒪 (\sqrt[]{\frac{1}{Δ}} l o g (\frac{1}{ϵ}))$ .由于 $Δ = \sqrt[]{\frac{k + 1}{N}} - \sqrt[]{\frac{k}{N}} \geq \sqrt[]{\frac{1}{(k + 1) N}}$ ，且 $δ = 12 ϵ$ ， $P o l y (x)$ 的次数是 $𝒪 (\sqrt[]{N k} l o g (\frac{12}{δ}))$ . 因此，得到了性质（ii）.

译

最后，容易发现 $P o l y (x)$ 是奇函数，这可以通过 $p_{e r f, l, n}$ 是奇多项式这一事实直接验证.因此，证明了性质（i）.

译

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

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

译

推论1 给定一个由 $N$ 个顶点组成的无向图 $G = (V, E)$ ，可以通过邻接矩阵Oracle $O_{G}$ 访问该图，同时给定一个正整数 $k > 0$ .则对于每个顶点 $v_{i} \in V$ ，存在一个量子算法 $𝒜_{i}$ ，使用 $𝒪 (\sqrt[]{N k} l o g (\frac{12}{δ}))$ 次对 $O_{G}$ 的查询，以至少 $1 - δ$ 的概率决定 $v_{i}$ 的度数是否为 $k$ .其中 $δ$ 是给定的概率误差限.

译

证明设 $g (x) = O_{G} (v_{i}, x)$ ，其中 $x \in V$ .根据定理2，存在一个量子算法，可以决定 $v_{i}$ 的度数是否为 $k$ .

译

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

译

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

译

4 结论

我们提出了一个量子算法，可以在 $𝒪 (N \sqrt[]{k})$ 次查询内解决判断一个 $N$ 个顶点的图中是否存在度数为 $k$ 的顶点的问题，而其经典复杂度为 $Ω (N^{2})$ . 为了完成该算法，我们使用了QSVT技术构建了一个算法，可以在 $𝒪 (\sqrt[]{N k})$ 次查询内判断 $N$ 个元素的无序数据库中的目标状态数量是否为 $k$ . 需要注意的是，本文研究的图的性质是一种非单调图的性质，而这类性质在量子计算领域中的关注较少.另一个值得进一步研究的相关问题是考虑如何设计量子算法来找到图中具有最大度数的顶点.

译

参考文献

AARONSON S， BEN-DAVID S， KOTHARI R， et al， 2021. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem［C］//Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing， 6 C： 1330-1342. [百度学术]

AMBAINIS A， BALODIS K， IRAIDS J， et al， 2020. Quantum lower and upper bounds for 2d-grid and Dyck language［C］//45th International Symposium on Mathematical Foundations of Computer Science， 8. [百度学术]

BALASUBRAMANIAN R， RAMAN V， SRINIVASARAGAVAN G， 1997. Finding scores in tournaments［J］. J Algorithms， 24（2）： 380-394. [百度学术]

BERETTA L， NARDINI F M， TRANI R， et al， 2019. An optimal algorithm to find champions of tournament graphs［C］//International Symposium on String Processing and Information Retrieval： 267-273. [百度学术]

BRASSARD G， HOYER P， MOSCA M， et al， 2002. Quantum amplitude amplification and estimation［J］. Contemp Math， 305： 53-74. [百度学术]

BUHRMAN H， CLEVE R， de WOLF R， et al， 1999. Bounds for small-error and zero-error quantum algorithms［C］//Proceedings of the 40th Annual Symposium on Foundations of Computer Science： 358-368. [百度学术]

DEY P， 2017. Query complexity of tournament solutions［C］//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence， 31（1）： 2992-2998. [百度学术]

GILYÉN A， SU Y， LOW G H， et al， 2019. Quantum singular value transformation and beyond： Exponential improvements for quantum matrix arithmetics［C］//Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing：193-204. [百度学术]

GOLDREICH O， 2017. Introduction to property testing［M］. Cambridge： Cambridge University Press. [百度学术]

GOYAL D， JAYAPAUL V， RAMAN V， 2020. Elusiveness of finding degrees［J］. Discrete Appl Math， 286： 128-139. [百度学术]

GUTIN G， MERTZIOS G B， REIDL F， 2018. Searching for maximum out-degree vertices in tournaments［EB/OL］. arXiv：1801.04702. [百度学术]

HØYER P， MOSCA M， de WOLF R， 2003. Quantum search on bounded-error inputs［M］//Baeten J C M， et al， Eds. Automata， Languages and Programming. Heidelberg： Springer， 291-299. [百度学术]

KULKARNI R， PODDER S， 2015. Quantum query complexity of subgraph isomorphism and homomorphism［EB/OL］. arXiv： 1509.06361. [百度学术]

LOW G H， CHUANG I L， 2017. Hamiltonian simulation by uniform spectral amplification［EB/OL］. arXiv： 1707.05391. [百度学术]

MAGNIEZ F， SANTHA M， SZEGEDY M， 2007. Quantum algorithms for the triangle problem［J］. SIAM J Comput， 37（2）： 413-424. [百度学术]

MARTYN J M， ROSSI Z M， TAN A K， et al， 2021. Grand unification of quantum algorithms［J］. PRX Quantum， 2（4）： 040203. [百度学术]

MONTANARO A， de WOLF R， 2016. A survey of quantum property testing［J］. Theory Comput， 7： 1-81. [百度学术]

ROSENBERG A L， 1973. On the time required to recognize properties of graphs： A problem［J］. ACM SIGACT News， 5（4）： 15-16. [百度学术]

SUN X， YAO A C， ZHANG S， 2004. Graph properties and circular functions： How low can quantum query complexity go？［C］//Proceedings of 19th IEEE Annual Conference on Computational Complexity： 286-293. [百度学术]

YODER T J， LOW G H， CHUANG I L， 2014. Fixed-point quantum search with an optimal number of queries［J］. Phys Rev Lett， 113（21）： 210501. [百度学术]

摘要

本文探讨了图属性测试问题的量子加速：对于给定的图和整数

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=

1.43933344

2.28600001

，图中是否存在一个度数为

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=

1.43933344

2.28600001

的顶点？该问题的量子复杂度在邻接矩阵oracle模型下被证明为

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229668&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229665&type=

12.95400047

5.41866684

，而其经典复杂度为

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229674&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229671&type=

8.97466660

3.80999994

，其中

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229682&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229679&type=

2.28600001

是图中顶点的数量. 为了证明该结果，得出了一个技术性结论，即对于给定的函数

<math id="M6"><mi>g</mi><mtext> </mtext><mo>:</mo><mtext> </mtext><mfenced open="[" close="]" separators="|"><mrow><mi>N</mi></mrow></mfenced><mo>→</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0

1</mn><mo stretchy="false">}</mo></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229689&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229686&type=

22.18266678

3.30200005

和整数

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=

1.43933344

2.28600001

，存在一个量子算法可以在

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229702&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229699&type=

12.19200039

5.41866684

次查询内判定

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229711&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229706&type=

18.88066673

4.57200003

是否等于

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=

1.43933344

2.28600001

.文中的结果基于量子奇异值变换（QSVT）和有误差输入的量子搜索技术.

Abstract

Quantum speedups for the graph property testing problem is studied： For a given graph and an integer

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=

1.69333339

2.62466669

， does the graph have a vertex of degree

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=

1.69333339

2.62466669

？ The quantum complexity of this problem is proven to be

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229737&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229734&type=

15.15533447

6.34999990

under the adjacency matrix oracle model， whereas its classical complexity is

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229744&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229740&type=

10.41399956

4.31799984

， where

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229750&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229747&type=

2.62466669

is the number of vertexes in the graph. In order to prove the result， a technical result that there exists a quantum algorithm for deciding whether

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229757&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229753&type=

23.53733444

5.33400011

equals

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=

1.69333339

2.62466669

or not in

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229770&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229767&type=

14.22399998

6.34999990

queries， for a given function

<math id="M19"><mi>g</mi><mo>:</mo><mtext> </mtext><mfenced open="[" close="]" separators="|"><mrow><mi>N</mi></mrow></mfenced><mo>→</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0

1</mn><mo stretchy="false">}</mo></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229777&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229773&type=

25.06133461

3.80999994

and an integer

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=

1.69333339

2.62466669

is obtained. These results are based on the techniques of quantum singular value transformation（QSVT） and quantum search on bounded-error inputs.

关键词

量子奇异值变换量子算法图属性测试

Keywords

quantum singular value transformationquantum algorithmgraph property testing

references

BALASUBRAMANIAN R， RAMAN V， SRINIVASARAGAVAN G， 1997. Finding scores in tournaments［J］. J Algorithms， 24（2）： 380-394.

BRASSARD G， HOYER P， MOSCA M， et al， 2002. Quantum amplitude amplification and estimation［J］. Contemp Math， 305： 53-74.

DEY P， 2017. Query complexity of tournament solutions［C］//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence， 31（1）： 2992-2998.

GOLDREICH O， 2017. Introduction to property testing［M］. Cambridge： Cambridge University Press.

GOYAL D， JAYAPAUL V， RAMAN V， 2020. Elusiveness of finding degrees［J］. Discrete Appl Math， 286： 128-139.

GUTIN G， MERTZIOS G B， REIDL F， 2018. Searching for maximum out-degree vertices in tournaments［EB/OL］. arXiv：1801.04702.

HØYER P， MOSCA M， de WOLF R， 2003. Quantum search on bounded-error inputs［M］//Baeten J C M， et al， Eds. Automata， Languages and Programming. Heidelberg： Springer， 291-299.

KULKARNI R， PODDER S， 2015. Quantum query complexity of subgraph isomorphism and homomorphism［EB/OL］. arXiv： 1509.06361.

LOW G H， CHUANG I L， 2017. Hamiltonian simulation by uniform spectral amplification［EB/OL］. arXiv： 1707.05391.

MAGNIEZ F， SANTHA M， SZEGEDY M， 2007. Quantum algorithms for the triangle problem［J］. SIAM J Comput， 37（2）： 413-424.

MARTYN J M， ROSSI Z M， TAN A K， et al， 2021. Grand unification of quantum algorithms［J］. PRX Quantum， 2（4）： 040203.

MONTANARO A， de WOLF R， 2016. A survey of quantum property testing［J］. Theory Comput， 7： 1-81.

ROSENBERG A L， 1973. On the time required to recognize properties of graphs： A problem［J］. ACM SIGACT News， 5（4）： 15-16.

YODER T J， LOW G H， CHUANG I L， 2014. Fixed-point quantum search with an optimal number of queries［J］. Phys Rev Lett， 113（21）： 210501.

163

浏览量

142

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据