求图中点度数的量子算法

本文探讨了图属性测试问题的量子加速:对于给定的图和整数k,图中是否存在一个度数为k的顶点?该问题的量子复杂度在邻接矩阵oracle模型下被证明为O(N√k),而其经典复杂度为Ω(N^(2)),其中N是图中顶点的数量.为了证明该结果,得出了一个技术性结论,即对于给定的函数g:[N]→{0,1}和整数k,存在一个量子算法可以在O(√Nk)次查询内判定|{x:g(x)=1}|是否等于k.文中的结果基于量子奇异值变换(QSVT)和有误差输入的量子搜索技术.