Loading [MathJax]/jax/output/HTML-CSS/jax.js
欢迎访问《中山大学学报(自然科学版)(中英文)》! English Version 维普资讯 中国知网 万方数据
特约论文 | 更新时间:2024-01-25
    • 求图中点度数的量子算法

    • Quantum algorithm for finding degrees

    • 郎健翔

      ,  

      李绿周

      ,  
    • 中山大学学报(自然科学版)(中英文)   2024年63卷第1期 页码:1-9
    • 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. 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模型下被证明为𝒪(Nk),而其经典复杂度为Ω(N2),其中N是图中顶点的数量. 为了证明该结果,得出了一个技术性结论,即对于给定的函数g : [N]{0,1}和整数k,存在一个量子算法可以在𝒪(Nk)次查询内判定|{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 𝒪(Nk) under the adjacency matrix oracle model, whereas its classical complexity is Ω(N2), 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 𝒪(Nk) queries, for a given function g: [N]{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, 2017Montanaro et al.,2016).其目的是确定给定对象是否具有预先确定的属性.研究对象包括函数、概率分布、图等.本文关注图的属性.

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

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

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

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

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

    OG|vi>|vj>|b>={|vi>|vj>|b>,if  (vi,vj)E,|vi>|vj>|b1>,if  (vi,vj)E,

    其中(vi,vj)E表示顶点 |vi>|vj> 之间存在一条边.

    1.1 结果和技术

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

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

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

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

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

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

    1.2 相关工作

    寻找顶点度数的经典算法.

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

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

    2 预备知识

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

    erf(x)=2πx0e-η2dη,

    另一个是符号函数

    sgn(x)={-1,x<0,0,x=0,1,x>0.

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

    2.1 量子奇异值变换

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

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

    定理3   给定一个酉矩阵U、它的逆U以及算符Aϕ=eiϕ|A0><A0|Bϕ=eiϕ|B0><B0|,定义a=<A0|U|B0>. 如果一个多项式 Poly(a) 满足以下条件:i) deg(Poly(a))d;ii) 当x[-1,1]时,|Poly(a)|1;iii) Poly(a) 是奇函数,那么我们可以利用 QSVT 技术构建一个电路,使得

    <A0|[d/2t=1UBϕ2t-1UAϕ2t]U|B0>=Poly(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个算法(无论是量子还是经典的),每个算法都以有界的出错概率给出一个布尔值,并且给定一个整数T1.那么存在一个量子算法,它使用𝒪(n/T) 次查询,并且以常数的概率:如果n个值中至少有T个值为 1,则返回一个对应值为1的索引;如果没有值为 1,则返回NULL.(当解的数 [T] 未知,期望查询次数也为𝒪(n/T)) .

    3 量子算法

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

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

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

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

    首先我们定义以下函数:

    f(x)=12sgn(x-kN+k-1N2)+12sgn(x+kN+k-1N2)-12sgn(x-kN+k+1N2)-12sgn(x+kN+k+1N2)={-1,-12(kN+k+1N)<x<-12(kN+k-1N),1,12(kN+k+1N)>x>12(kN+k-1N),0,其他.                                                              (1)

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

    f(MN)={1,M=k,0,Mk (2)

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

    (i)Poly(x)是奇函数;

    (ii)Poly(x)的次数为𝒪(Nklog(12δ))

    (iii)当x[-1,1]时,|Poly(x)|1

    (iv)当x=MN时,|f(x)-Poly(x)|δ2.

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

    现在我们将构造一个量子电路来实现Poly(x).设|A0>=Mi=11M|mi>,其中|mi>是满足g(mi)=1的状态.定义Aϕ如下:

    Aϕ|j>={|j>,f(j)=1,ei ϕ|j>,f(j)1,

    Yoder et al.(2014)所示,可以通过使用一个或两个Oracle查询来实现Aϕ. 此外,设|B0>=|0>,即全零状态,U=Hn.不需要查询Oracle即可实现Bϕ.根据定理3中的变量a,我们有<A0|U|B0>=MN. 根据定理3,可以构造一个量子电路[d/2t=1UBϕ2t-1UAϕ2t]U,记作UQSVT,其中d=𝒪(kNlog(12δ)),满足以下条件:

    <A0|UQSVT|B0>=Poly(MN).

    注意到|f(MN)-Poly(MN)|δ2f(MN)={1,M=k,0,Mk.因此,当M=k时,有以下结果:

    <A0|UQSVT|B0>=Poly(MN)1-δ2.

    用当前态作为输入查询g的结果为01-δ的概率成立,当Mk时:

    <A0|UQSVT|B0>=Poly(MN)δ2.

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

    3.2 关键引理的证明

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

    Low et al.(2017)中的两个引理.

    引理1(关于符号函数sgn(x)的整体逼近(

    Low et al.,2017Lemma 10) 对任意Δ>0xRϵ(0,2/(eπ)], 令 l=2Δlog1/2(2πϵ2). 则函数 fΔ,ϵ(x)erf(lx) 满足

    |fΔ,ϵ(x)|1,max|x|Δ/2|fΔ,ϵ(x)-sgn(x)|ϵ.

    引理2  (误差函数erf(lx)的多项式逼近(

    Low et al.,2017Corollary 4) 对任意l>0ϵ(0,𝒪(1)],可定义奇次幂的多项式perf,l,n

    perf,l,n(x)=2le-l2/2π(I0(l2/2)x+(n-1)/2j=1Ij(l2/2)(-1)j(T2j+1(x)2j+1-T2j-1(x)2j-1)),

    使得

    maxx[-2,2]|perf,l,n(x)-erf(lx)|ϵ,

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

    n=𝒪((l2+log(1/ϵ))log(1/ϵ)).

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

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

    f(x)=12sgn(x-kN+k-1N2)+12sgn(x+kN+k-1N2)-12sgn(x-kN+k+1N2)-12sgn(x+kN+k+1N2),                                 (3)

    使得

    (i)Poly(x) 是奇函数;

    (ii)Poly(x) 的次数为 𝒪(Nklog(12δ))

    (iii)当x[-1,1]时,|Poly(x)|1

    (iv)当 x=MN 时,|f(x)-Poly(x)|δ2.

    证明  Δ=k+1N-kN,对于每个sgn(x±c)(其中c指代公式(3)中的常数),根据引理1和引理2,存在fΔ,ϵ(x)perf,l,n.现在,我们定义以下多项式

    Poly(x)=12(1+2ϵ)perf,l,n(x-kN+k-1N2)+12(1+2ϵ)perf,l,n(x+kN+k-1N2)-12(1+2ϵ)perf,l,n(x-kN+k+1N2)-12(1+2ϵ)perf,l,n(x+kN+k+1N2).

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

    Poly(x)12(1+2ϵ)(fΔ,ϵ(x-kN+k-1N2)+ϵ)+12(1+2ϵ)(fΔ,ϵ(x+kN+k-1N2)+ϵ)-12(1+2ϵ)(fΔ,ϵ(x-kN+k+1N2)-ϵ)-12(1+2ϵ)(fΔ,ϵ(x+kN+k+1N2)-ϵ)12(1+2ϵ)(fΔ,ϵ(x-kN+k-1N2)+2ϵ)+12(1+2ϵ)(fΔ,ϵ(x+kN+k-1N2)+2ϵ)1+2ϵ2(1+2ϵ)+1+2ϵ2(1+2ϵ)=1.

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

    -fΔ,ϵ(x-kN+k+1N2)-fΔ,ϵ(x+kN+k+1N2)0

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

    Poly(x)12(1+2ϵ)(fΔ,ϵ(x-kN+k-1N2)-ϵ)+12(1+2ϵ)(fΔ,ϵ(x+kN+k-1N2)-ϵ)-12(1+2ϵ)(fΔ,ϵ(x-kN+k+1N2)+ϵ)-12(1+2ϵ)(fΔ,ϵ(x+kN+k+1N2)+ϵ)-12(1+2ϵ)(fΔ,ϵ(x-kN+k+1N2)+2ϵ)-12(1+2ϵ)(fΔ,ϵ(x+kN+k+1N2)+2ϵ)-1+2ϵ2(1+2ϵ)-1+2ϵ2(1+2ϵ)=-1.

    由于 fΔ,ϵ(x-kN+k-1N2)+fΔ,ϵ(x+kN+k-1N2)0 可以通过解析验证. 当x[-1,0]时,可以对称地证明 |Poly(x)|1. 因此,性质(iii)得到验证.

    x=MN时,以下条件同时成立:

    |x-kN+k-1N2|Δ2|x+kN+k-1N2|Δ2
    |x-kN+k+1N2|Δ2|x+kN+k+1N2|Δ2.

    因此,有

    |f(x)-Poly(x)||(1+2ϵ)Poly(x)-Poly(x)|+|(1+2ϵ)Poly(x)-f(x)|2ϵ+12|perf,l,n(x-kN+k-1N2)-sgn(x-kN+k-1N2)|+12|perf,l,n(x+kN+k-1N2)-sgn(x+kN+k-1N2)|+12|perf,l,n(x-kN+k+1N2)-sgn(x-kN+k+1N2)|+12|perf,l,n(x+kN+k+1N2)-sgn(x+kN+k+1N2)|6ϵ.

    第二个小于号成立是因为: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)得到证明.

    将引理1中l的表达式代入引理2,我们可以看出Poly(x)的次数是𝒪(1Δlog(1ϵ)).由于Δ=k+1N-kN1(k+1)N,且δ=12ϵPoly(x)的次数是𝒪(Nklog(12δ)). 因此,得到了性质(ii).

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

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

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

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

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

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

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

    4 结 论

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

    参考文献

    AARONSON SBEN-DAVID SKOTHARI Ret al2021. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem[C]//Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing6 C: 1330-1342. [百度学术] 

    AMBAINIS ABALODIS KIRAIDS Jet al2020. Quantum lower and upper bounds for 2d-grid and Dyck language[C]//45th International Symposium on Mathematical Foundations of Computer Science8. [百度学术] 

    BALASUBRAMANIAN RRAMAN VSRINIVASARAGAVAN G1997. Finding scores in tournaments[J]. J Algorithms242): 380-394. [百度学术] 

    BERETTA LNARDINI F MTRANI Ret al2019. An optimal algorithm to find champions of tournament graphs[C]//International Symposium on String Processing and Information Retrieval267-273. [百度学术] 

    BRASSARD GHOYER PMOSCA Met al2002. Quantum amplitude amplification and estimation[J]. Contemp Math30553-74. [百度学术] 

    BUHRMAN HCLEVE Rde WOLF Ret al1999. Bounds for small-error and zero-error quantum algorithms[C]//Proceedings of the 40th Annual Symposium on Foundations of Computer Science358-368. [百度学术] 

    DEY P2017. Query complexity of tournament solutions[C]//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence311): 2992-2998. [百度学术] 

    GILYÉN ASU YLOW G Het al2019. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics[C]//Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing193-204. [百度学术] 

    GOLDREICH O2017. Introduction to property testing[M]. CambridgeCambridge University Press. [百度学术] 

    GOYAL DJAYAPAUL VRAMAN V2020. Elusiveness of finding degrees[J]. Discrete Appl Math286128-139. [百度学术] 

    GUTIN GMERTZIOS G BREIDL F2018. Searching for maximum out-degree vertices in tournaments[EB/OL]. arXiv:1801.04702. [百度学术] 

    HØYER PMOSCA Mde WOLF R2003. Quantum search on bounded-error inputs[M]//Baeten J C M, et al, Eds. Automata, Languages and Programming. HeidelbergSpringer291-299. [百度学术] 

    KULKARNI RPODDER S2015. Quantum query complexity of subgraph isomorphism and homomorphism[EB/OL]. arXiv: 1509.06361. [百度学术] 

    LOW G HCHUANG I L2017. Hamiltonian simulation by uniform spectral amplification[EB/OL]. arXiv: 1707.05391. [百度学术] 

    MAGNIEZ FSANTHA MSZEGEDY M2007. Quantum algorithms for the triangle problem[J]. SIAM J Comput372): 413-424. [百度学术] 

    MARTYN J MROSSI Z MTAN A Ket al2021. Grand unification of quantum algorithms[J]. PRX Quantum24): 040203. [百度学术] 

    MONTANARO Ade WOLF R2016. A survey of quantum property testing[J]. Theory Comput71-81. [百度学术] 

    ROSENBERG A L1973. On the time required to recognize properties of graphs: A problem[J]. ACM SIGACT News54): 15-16. [百度学术] 

    SUN XYAO A CZHANG S2004. Graph properties and circular functions: How low can quantum query complexity go?[C]//Proceedings of 19th IEEE Annual Conference on Computational Complexity286-293. [百度学术] 

    YODER T JLOW G HCHUANG I L2014. Fixed-point quantum search with an optimal number of queries[J]. Phys Rev Lett11321): 210501. [百度学术] 

    163

    浏览量

    142

    下载量

    0

    CSCD

    文章被引用时,请邮件提醒。
    提交
    工具集
    下载
    参考文献导出
    分享
    收藏
    添加至我的专辑

    相关文章

    暂无数据

    相关作者

    暂无数据

    相关机构

    暂无数据
    0