Subexponential-Time Quantum Advantage beyond Double-Logarithmic Space

Abstract

We prove that subexponential-time quantum Turing machines are superior to their classical counterparts within common space bounds in $\Omega (\log \log n)$. For that purpose, we define infinitely many sets of ``padded palindromes'' that are distinguished from each other by the precise relationships between the lengths of the palindromic prefixes and the paddings. We exhibit an infinite family $\mathcal{F}$ of functions in $(\log n{)}^{\omega (1)}\cap n^{o(1)}$ such that for every ${\tilde{f}}_i\in \mathcal{F}$, there exists another function ${\tilde{f}}_{i+1}\in \mathcal{F}$ such that ${\tilde{f}}_{i+1}(n)\in o({\tilde{f}}_i(n))$, and each such ${\tilde{f}}_i$ corresponds to a different quantum advantage statement, i.e. a proper inclusion of the form $\mathsf{BPTISP}(2^{O({\tilde{f}}_i(n))},o(\log {\tilde{f}}_i(n)))⊊\mathsf{BQTISP}(2^{O({\tilde{f}}_i(n))},o(\log {\tilde{f}}_i(n)))$ for a different pair of subexponential time and sublogarithmic space bounds. One can also obtain quantum advantage statements where the common space bound is $\Theta (\log \log n)$ and the time bound is ``almost'' quasi-polynomial, i.e., of the form $2^{(\log n{)}^{\Theta (f(n))}}$, where $f(n)\in \omega (1)$ is a function that can be selected to grow very slowly. Our results depend on a technique enabling polynomial-time quantum finite automata to control the amount of padding with very fine asymptotic granularity.