求图中点度数的量子算法
Quantum algorithm for finding degrees
郎健翔 1李绿周1
作者信息
- 1. 中山大学计算机学院,广东 广州 510006
- 折叠
摘要
本文探讨了图属性测试问题的量子加速:对于给定的图和整数k,图中是否存在一个度数为k的顶点?该问题的量子复杂度在邻接矩阵oracle模型下被证明为O(N√k),而其经典复杂度为Ω(N2),其中N是图中顶点的数量.为了证明该结果,得出了一个技术性结论,即对于给定的函数g:[N]→{0,1}和整数k,存在一个量子算法可以在O(√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 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.
关键词
量子奇异值变换/量子算法/图属性测试Key words
quantum singular value transformation/quantum algorithm/graph property testing引用本文复制引用
基金项目
国家自然科学基金(62272492)
广东省基础与应用基础研究基金(2020B1515020050)
出版年
2024
国家科技期刊平台
NSTL
维普
万方数据