论文标题
使用量子和随机验证者模拟证明系统的时空下限
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers
论文作者
论文摘要
Fortnow于1997年发起的一项工作已证明了与$ \ Mathsf {SAT} $问题和多项式时间层次结构中的相关问题的独立时间空间下限。例如，对于$ \ mathsf {sat} $问题，最新的是，在$ n^c $ time中随机计算机和$ n^{o（1）} $ space不能通过$ c <2 \ cos（\ 2 \ cos（\fracπ{7}）\ 1.801 $来解决问题。 我们将这种下限方法扩展到量子和随机域。将Grover的算法与来自$ \ Mathsf {SAT} $时空下限的组件结合在一起，我们表明存在$ o（n）$ time在$ o（n）$ time中使用Quantum Merlin-Arthur协议中的问题，这些协议无法以$ n^c $ time和$ n^c $ n^{o（1）} $ C <$ c <c <c < \ frac {3+ \ sqrt {3}} {2} \大约2.366 $，一个超季度时间下限。该结果以及对$ \ mathsf {sat} $的先前工作都可以看作是时间下限对小空间算法的更一般公式的结果，小空间算法我们全面研究了它们的渐近学。 我们还显示了针对随机算法的下限：在$ o（n）$时间内使用（经典）Merlin-Arthur协议在$ o（n）$时间中存在问题，这些协议无法在$ n^c $随机时间和$ n^{o（1）} $ space同时使用$ c <1.465 $，改善dieHll的结果。对于量子Merlin-Arthur协议，此设置中的下限可以提高到$ C <1.5 $。
A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$ problem, the state-of-the-art is that the problem cannot be solved by random-access machines in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < 2\cos(\fracπ{7}) \approx 1.801$. We extend this lower bound approach to the quantum and randomized domains. Combining Grover's algorithm with components from $\mathsf{SAT}$ time-space lower bounds, we show that there are problems verifiable in $O(n)$ time with quantum Merlin-Arthur protocols that cannot be solved in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < \frac{3+\sqrt{3}}{2} \approx 2.366$, a super-quadratic time lower bound. This result and the prior work on $\mathsf{SAT}$ can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in $O(n)$ time with (classical) Merlin-Arthur protocols that cannot be solved in $n^c$ randomized time and $n^{o(1)}$ space simultaneously for $c < 1.465$, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to $c < 1.5$.
