量子科技中心_量科网

邻近搜索是一个计算密集型问题，通常既耗时又消耗内存。此类算法的主要问题在于缓存未命中导致的执行时间过长。该研究团队提出了一种基于固定半径邻近搜索问题（FRANS）的量子算法，该算法采用格罗弗算法的固定点版本。研究人员推导出一个高效量子电路，能以线性查询复杂度（与粒子数量N成正比）解决FRANS问题。该量子电路会返回固定半径范围内所有邻近粒子对及其距离的列表，从而规避缓存未命中造成的减速现象。 研究团队详细构建了格罗弗算子并分析了其门复杂度。在最坏情况下，该算法整体复杂度为𝒪(M^(1/2)N^2)，其中M表示邻近对数量，所需量子比特数为𝒪(logN)。通过引入额外辅助量子比特，可将电路深度降低至𝒪(NlogN)——对于非结构化数据集需付出𝒪(N)量子比特的代价，而对于结构化数据集仅需𝒪(poly(logN))量子比特。最后，该工作评估了模型对读取错误的鲁棒性，并提出了一种无需纠错的验证结果准确性策略。