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 singular value transformationquantum algorithmgraph property testing
国家科技期刊平台
NSTL
万方数据
维普
