量子科技中心_量科网

该研究团队对伪确定性量子算法展开了系统性研究。这类量子算法能以高概率为任意输入输出规范解。在查询复杂度模型框架下，主要贡献包括以下需要专门针对伪确定性设计新下界技术的复杂性分离成果： - 提出“规避加密字符串”(AOES)问题，其经典随机查询复杂度为O(1)，但对伪确定性量子算法具有最大难度(Ω(N)查询复杂度) - 提出“量子锁定估计”(QL-Estimation)问题，其伪确定性量子算法较经典伪确定性算法实现指数级加速(O(logN) vs Θ(√N))，而随机查询复杂度仅为O(1) 作为补充，研究证明对于任何完全问题R，伪确定性量子算法较确定性算法至多具有五次方优势，即D(R)=Õ(psQ(R)⁵)。在算法层面，识别出一类能以较小开销实现伪确定性的量子搜索问题，包括Grover搜索、元素独特性、三角形查找、k-求和及图碰撞问题。