求图中点度数的量子算法OACSTPCD
Quantum algorithm for finding degrees
本文探讨了图属性测试问题的量子加速:对于给定的图和整数k,图中是否存在一个度数为k的顶点?该问题的量子复杂度在邻接矩阵oracle模型下被证明为O(N√k),而其经典复杂度为Ω(N2),其中N是图中顶点的数量.为了证明该结果,得出了一个技术性结论,即对于给定的函数g:[N]→{0,1}和整数k,存在一个量子算法可以在O(√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 O(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 O(√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.
郎健翔;李绿周
中山大学计算机学院,广东 广州 510006
计算机与自动化
量子奇异值变换量子算法图属性测试
quantum singular value transformationquantum algorithmgraph property testing
《中山大学学报（自然科学版）（中英文）》 2024 (001)
1-9 / 9
国家自然科学基金(62272492);广东省基础与应用基础研究基金(2020B1515020050)
评论