학술논문
求图中点度数的量子算法 / Quantum algorithm for finding degrees
Document Type
Academic Journal
Author
Source
中山大学学报（自然科学版）（中英文） / Acta Scientiarum Naturalium Universitatis Sunyatseni. 63(1):1-9
Subject
Language
Chinese
ISSN
2097-0137
Abstract
本文探讨了图属性测试问题的量子加速:对于给定的图和整数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.
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.