纸质出版日期:2024-01-25,
网络出版日期:2023-12-18,
收稿日期:2023-09-07,
录用日期:2023-11-02
扫 描 看 全 文
引用本文
阅读全文PDF
本文探讨了图属性测试问题的量子加速:对于给定的图和整数k,图中是否存在一个度数为k的顶点?该问题的量子复杂度在邻接矩阵oracle模型下被证明为𝒪(N√k),而其经典复杂度为Ω(N2),其中N是图中顶点的数量. 为了证明该结果,得出了一个技术性结论,即对于给定的函数g : [N]→{0,1}和整数k,存在一个量子算法可以在𝒪(√Nk)次查询内判定|{x:g(x)=1}|是否等于k.文中的结果基于量子奇异值变换(QSVT)和有误差输入的量子搜索技术.
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√k) 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.
属性测试是一个重要且广泛研究的领域,受到经典计算和量子计算社区的广泛关注(
对于一个N个顶点的图,如果任何经典算法在最坏情况下都需要探查邻接矩阵中的所有条目,以确定某个属性,则该属性被称为难以捉摸的(
在本文中,我们考虑的问题是确定一个图是否具有特定度数的顶点,这是一个难以捉摸且非单调的图属性.更具体的问题描述如下.
问题 给定一个N个顶点的无向图G=(V,E)和一个非负整数k,目标是确定图G是否具有度数为k的顶点.如果存在这样的顶点,则找出它.
假设一个图G=(V,E) 可以通过邻接矩阵查询模型进行访问.它的量子版本用 OG 表示:
OG|vi>|vj>|b>={|vi>|vj>|b>,if (vi,vj)∉E,|vi>|vj>|b⊕1>,if (vi,vj)∈E, |
其中(vi,vj)∈E表示顶点 |vi> 和 |vj> 之间存在一条边.
本文旨在探讨使用最少的查询次数来解决上述问题的量子算法.我们的主要结果如下.
定理1 对于一个由N个顶点组成的无向图G=(V,E),可以通过邻接矩阵Oracle OG访问该图,同时给定一个正整数k>0.存在一个量子算法,使用𝒪(N√k)次对OG的查询,如果图中存在度数为k的顶点,则该算法能够找到这样的顶点;否则,算法输出“不存在这样的顶点”.
一种直接解决上述问题的方法是首先使用精确量子计数算法(
定理2 给定一个函数 g : [N]→{0,1},以及满足1≤k≤N的整数k,令M=|{x : g(x)=1}|. 则存在一个量子算法,使用𝒪(√Nklog(12δ))次对g的查询,并以至少为1-δ的概率判断M=k或M≠k.
为了证明定理2,我们将使用量子奇异值转换(QSVT)技术(Gilyén et al.,2019).此外,基于定理2和有限误差输入的量子搜索(Høyer et al.,2003),我们将证明定理1.
寻找顶点度数的经典算法.
图问题上的量子算法. 目前大多数解决图问题的量子算法都基于两种查询模型:邻接矩阵和邻接表.其中,邻接矩阵查询模型被用于许多图问题,如最短路径、连通性、最小生成树等等,而邻接表查询模型则被用于某些需要实现全局变换的问题,如判定二分图、判定可遍历性等等.最近,一些新的查询模型也被研究了,如割问题和独立集问题.另外,在量子模型中,也有一些出色的工作涉及到图的性质检测,包括二分图性检测、扩展性检测等等.目前还没有关于量子算法来判断一个图是否有一个特定度数顶点的工作.
在本文中,定义[N]≔0,1,⋯,N-1.我们将使用两个函数:一个是误差函数
erf(x)=2√π∫x0e-η2dη, |
另一个是符号函数
sgn(x)={-1,x<0,0,x=0,1,x>0. |
接下来,简要介绍两个稍后将会用到的工具.
量子奇异值变换(QSVT,quantum singular value transformation)技术最初在Gilyén et al.(2019)中被提出,为我们设计量子算法提供了一种新方法.然后,参考
定理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/2∏t=1UBϕ2t-1U†Aϕ2t]U|B0>=Poly(a). |
这个定理类似于
普通的 Grover 搜索只能在正确定义的oracle上生效,当对带有误差的oracle进行查询时,将会失败.于是Høyer et al.(2003)提出了以下有界误差输入的量子搜索技术.
定理4 (Høyer et al., 2003;
我们将本文考虑的问题规约为确定给定顶点的度数是否为 k 的问题,这进一步推广为在第 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,M≠k | (2) |
是一个区别M=k还是M≠k的指示器. 然后,我们可以构造一个多项式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>=M∑i=11√M|mi>,其中|mi>是满足g(mi)=1的状态.定义Aϕ如下:
Aϕ|j>={|j>,f(j)=1,ei ϕ|j>,f(j)≠1, |
如
<A0|UQSVT|B0>=Poly(√MN). |
注意到|f(√MN)-Poly(√MN)|≤δ2和 f(√MN)={1,M=k,0,M≠k.因此,当M=k时,有以下结果:
<A0|UQSVT|B0>=Poly(√MN)≥1-δ2. |
用当前态作为输入查询g的结果为0以1-δ的概率成立,当M≠k时:
<A0|UQSVT|B0>=Poly(√MN)≤δ2. |
用当前态作为输入查询g的结果为1以1-δ的概率成立.因此,构造的量子电路可以以至少1-δ的概率判断M=k是否成立.
本文的目的是证明引理3,该引理说明存在一个期望的多项式Ploy(x)来逼近式(1)中的函数f(x).在此之前,需要使用
引理1(关于符号函数sgn(x)的整体逼近(
|fΔ,ϵ(x)|≤1,max|x|≥Δ/2|fΔ,ϵ(x)-sgn(x)|≤ϵ. |
引理2 (误差函数erf(lx)的多项式逼近(
perf,l,n(x)=2le-l2/2√π(I0(l2/2)x+(n-1)/2∑j=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-√kN≥√1(k+1)N,且δ=12ϵ,Poly(x)的次数是𝒪(√Nklog(12δ)). 因此,得到了性质(ii).
最后,容易发现Poly(x)是奇函数,这可以通过perf,l,n是奇多项式这一事实直接验证.因此,证明了性质(i).
现在我们可以展示用于确定给定图是否存在度数为k的顶点的量子算法.
推论1 给定一个由N个顶点组成的无向图G=(V,E),可以通过邻接矩阵Oracle OG 访问该图,同时给定一个正整数k>0.则对于每个顶点 vi∈V,存在一个量子算法𝒜i,使用𝒪(√Nklog(12δ))次对OG的查询,以至少1-δ的概率决定vi的度数是否为 k.其中δ是给定的概率误差限.
证明 设g(x)=OG(vi,x),其中x∈V.根据定理2,存在一个量子算法,可以决定vi的度数是否为k.
这时,定理1可以由定理4和推论1推导得出.
注1 在上述定理中,要求k>0.当k=0时,我们也可以构造一个消耗𝒪(N)次查询的量子算法.实际上,如果将式(1)替换为f(x)=sgn(x),则可以通过类似的思路得到k=0的算法.
我们提出了一个量子算法,可以在𝒪(N√k)次查询内解决判断一个N个顶点的图中是否存在度数为 k 的顶点的问题,而其经典复杂度为Ω(N2). 为了完成该算法,我们使用了QSVT技术构建了一个算法,可以在𝒪(√Nk)次查询内判断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. [百度学术]
163
浏览量
142
下载量
0
CSCD
相关文章
相关作者
相关机构