中山大学学报（自然科学版）（中英文）2024，Vol.63Issue(1)：1-9,9.DOI:10.13471/j.cnki.acta.snus.2023A070
求图中点度数的量子算法
Quantum algorithm for finding degrees
摘要
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分类
信息技术与安全科学引用本文复制引用
郎健翔,李绿周..求图中点度数的量子算法[J].中山大学学报（自然科学版）（中英文）,2024,63(1):1-9,9.基金项目
国家自然科学基金(62272492) （62272492）
广东省基础与应用基础研究基金(2020B1515020050) （2020B1515020050）
