量子科技中心_量科网

有向s-t连通性（dstcon）问题旨在判定输入有向图中两个指定顶点s与t之间是否存在有向路径。该问题不仅广泛存在于算法应用中，更因其𝖭𝖫完全性成为复杂性理论的基础问题。研究表明，对于任意S≥log₂(n)，存在一个量子算法能以空间S和时间T≤2^(½log(n)⋅log(n/S)+o(log²(n)))求解dstcon问题——该结果相较于经典算法实现了（最高达二次方的）改进，这一优势在S=o(n)时均成立。值得注意的是，该算法使用的S总量子空间中，仅O(log²(n))为量子空间，其余均为经典空间。这一发现实质上揭示了经典空间与量子时间可相互转换的特性。