量子科技中心_量科网

在该论文中，研究人员探讨了在二维地图中搜索“最大空白矩形”的问题，其一维版本则是搜索“最大空白线段”问题。针对n×n矩形地图中的“最大空白正方形”和固定宽度d的“最大空白矩形”问题，该团队提出了一种量子算法。该算法的查询复杂度在正方形案例中为Õ(n^1.5)，在固定宽度d的矩形案例中为Õ(n√d)。与此同时，经典算法的下界分别为Ω(n²)和Ω(n√d)。对于该问题的一维版本，量子算法具有O(√n logn loglogn)的查询复杂度，其量子下界为Ω(√n)——该结果与对数因子修正后的上界几乎相等，而经典下界为Ω(n)。这表明该工作在该问题上实现了平方级加速。