论文标题
（否）USTCON的量子时空权衡
(No) Quantum space-time tradeoff for USTCON
论文作者
论文摘要
无方向性的$ st $连接性对于其在网络问题中的应用以及其与Logspace复杂性的理论连接都很重要。从经典上讲，一长串的工作导致了任何$ s $的时间空间权衡$ t = \ tilde {o}（n^2/s）$，因此$ s =ω（\ log（n））$和$ s = o（n^2/m）$。令人惊讶的是，我们表明没有非平凡的时间空间权衡：有一种量子算法可以实现最佳时间$ \ tilde {o}（n）$和space $ o（\ log log（n））$。这可以改善先前的结果，这需要$ O（\ log（n））$空间和$ \ tilde {o}（n^{1.5}）$时间，或$ \ tilde {o} {o}（n）$空间和时间。为了补充这一点，我们表明，当在相应的随机步行的频谱间隙上有下限时，存在非平凡的时间空间折衷。
Undirected $st$-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of $T=\tilde{O}(n^2/S)$ for any $S$ such that $S=Ω(\log (n))$ and $S=O(n^2/m)$. Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time $\tilde{O}(n)$ and space $O(\log (n))$ simultaneously. This improves on previous results, which required either $O(\log (n))$ space and $\tilde{O}(n^{1.5})$ time, or $\tilde{O}(n)$ space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.
