量子科技中心_量科网

我们提出了一种针对新型黑箱问题的量子算法：通过访问一个经过混淆处理的隐藏 $d$-正则基础图 $G$（包含 $n$ 个顶点）的预言机（oracle），而非直接遍历该图，来识别该图。从 $G$ 出发，我们通过三步构建尖顶图 $G_{\rm spire}$：首先，每个顶点被提升为一个指数级大小的簇，相邻簇之间通过随机二分图连接；然后，每个簇顶部加上一个平衡的尖顶结构；最后，所有顶点被随机重新标记。当 $G=K_2$ 时，该结构退化为焊接树图（welded-trees graph）。我们的算法概念上十分简洁：在 $G_{\rm spire}$ 上执行连续时间量子游走，随后在经典预计算的时间 $t^*$ 处进行一次 Hadamard 测试；算法返回其预测振幅最接近测量结果的候选图。该设计基于严格的谱理论：从任意尖顶的顶点出发，量子游走被限制在一个多项式维度的不变子空间中，该子空间在更简单的塔式图 $G_{\rm tower}$ 的邻接矩阵下演化；该矩阵块对角化为 $n$ 个独立的、大小为 $n$ 的三对角系统，每个系统通过切比雪夫（Chebyshev）长期方程以闭合形式求解。这种分解使得高效数值计算成为可能，从而提供 $t^*$ 和预测振幅。在棱柱图 $Y_m$ 与莫比乌斯梯图 $M_m$（每个图包含 $n=2m$ 个顶点）的对比中，数值研究支持一个精确猜想：在演化时间约为 $m^2$ 时，约 $\widetilde O(n^2/\log n)$ 次测量足以区分这两类图；我们测试了 $4 \le m \le 5121$（$n$ 高达 $10242$）。通过与焊接树图下界类比，我们进一步猜想，任何经典算法都需要指数级（关于 $n$）的查询次数。综合这些猜想，表明在识别混淆基础图的问题上存在指数级的量子加速。