Subexponential-Time Quantum Advantage beyond Double-Logarithmic Space

A. C. Cem Say

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 i…