Fine-grained quantum advantage beyond double-logarithmic space

A. C. Cem Say · 2026

Read Fine-grained quantum advantage beyond double-logarithmic space by A. C. Cem Say (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16695.txt.

Introduction

A. C. Cem Say probes where quantum machines beat plain ones by a hair. Space is the scarce good in his tests, not time. Below a small space cap, quantum tools are known to win. Past that cap, just one win was known. His 2026 preprint sharpens that edge with finer tools.

The space caps here grow slower than log of log of input size. At those caps, quantum steps can solve tasks plain steps can't. Say's math keeps the gap true for crisp time bounds too. Such fine wins map the true edge of quantum power. They guide where small quantum gear may first pay off.

Catalog record

CREATORA. C. Cem Say
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16695

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fine-grained quantum advantage beyond double-logarithmic space A. C. Cem Say Abstract Polynomial-time quantum Turing machines are provably superior to their classical counterparts within a common space bound in o ⁡ ( log ⁡ log ⁡ n ) o(\log\log n) . For Ω ⁡ ( log ⁡ log ⁡ n ) \Omega(\log\log n) space, the only known quantum advantage result has been the fact 𝖡𝖯𝖳𝖨𝖲𝖯 ⁡ ( 2 O ⁡ ( n ) , o ⁡ ( log ⁡ n ) ) ⊊ 𝖡𝖰𝖳𝖨𝖲𝖯 ⁡ ( 2 O ⁡ ( n ) , o ⁡ ( log ⁡ n ) ) \mathsf{BPTISP}(2^{O(n)},o(\log n))\subsetneq\mathsf{BQTISP}(2^{O(n)},o(\log n)) , proven by exhibiting an exponential-time quantum finite automaton (2QCFA) that recognizes L p ​ a ​ l L_{pal} , the language of palindromes, which is an impossible task for sublogarithmic-space probabilistic Turing machines. No subexponential-time quantum algorithm can recognize L p ​ a ​ l L_{pal} in sublogarithmic space. We initiate the study of quantum advantage under simultaneous subexponential time and Ω ⁡ ( log ⁡ log ⁡ n ) ∩ o ⁡ ( log ⁡ n ) \Omega(\log\log n)\cap o(\log n) space bounds. We exhibit an infinite family ℱ \mathcal{F} of functions in ( log ⁡ n ) ω ⁡ ( 1 ) ∩ n o ⁡ ( 1 ) (\log n)^{\omega(1)}\cap n^{o(1)} such that for every f i ∈ ℱ f_{i}\in\mathcal{F} , there exists another function f i + 1 ∈ ℱ f_{i+1}\in\mathcal{F} such that f i + 1 ​ ( n ) ∈ o ⁡ ( f i ​ ( n ) ) f_{i+1}(n)\in o(f_{i}(n)) , and each such f i f_{i} corresponds to a different quantum advantage statement, i.e. a proper inclusion of the form 𝖡𝖯𝖳𝖨𝖲𝖯 ⁡ ( 2 O ​ ( f i ​ ( n ) ) , o ⁡ ( log ⁡ f i ​ ( n ) ) ) ⊊ 𝖡𝖰𝖳𝖨𝖲𝖯 ⁡ ( 2 O ​ ( f i ​ ( n ) ) , o ⁡ ( log ⁡ f i ​ ( n ) ) ) \mathsf{BPTISP}(2^{O(f_{i}(n))},o(\log f_{i}(n)))\subsetneq\mathsf{BQTISP}(2^{O(f_{i}(n))},o(\log f_{i}(n))) for a different pair of subexponential time and sublogarithmic space bounds. Our results depend on a technique enabling polynomial-time quantum finite automata to control padding functions with very fine asymptotic granularity. Keywords: quantum Turing machines, quantum finite automata, time complexity, space complexity 1 Introduction Although it is widely believed that quantum computation is intrinsically more powerful than classical computation, this difference in power has been proven unconditionally in only a limited number of scenarios. Celebrated examples like Shor’s algorithm for integer factorization [ 12 ] do not constitute such proofs when the underlying computational problem is not known to be impossible for classical computers running under comparable time and space bounds. A theoretical demonstration of quantum advantage can be expressed as a proper inclusion in terms of simultaneous time-space complexity classes, i.e. in the form \mathsf{BPTISP}(t(n),s(n))\subsetneq\mathsf{BQTISP}(t(n),s(n)), where t(n) and s(n) are respectively the time and space complexity functions bounding the resource utilization of the compared classical and quantum machines. In this sense, unconditional quantum advantage proofs have only been obtained for sublogarithmic space bounds until now. It is known [ 2 ] that no probabilistic Turing machine (PTM) running within o(\log\log n) space and polynomial expected time can recognize a nonregular language with bounded error. In 2002, Ambainis and Watrous demonstrated a constant-space quantum Turing machine, i.e., a two-way finite automaton with quantum and classical states (2QCFA), that can recognize the nonregular language L_{eq}=\Set{0^{n}1^{n}}{n\geq 0} in polynomial expected time [ 1 ] , thereby proving \addcontentsline{lla}{section}{\numberline q:awpoly}\mathsf{BPTISP}(n^{O(1)},o(\log\log n))\subsetneq\mathsf{BQTISP}(n^{O(1)},o(\log\log n)). (1) Equation 1 is the only unconditionally proven quantum advantage statement where the common time bound is a polynomial function, and the memory budgets that it covers are extremely restricted. For larger common space bounds, namely, those in \Omega(\log\log n)\cap o(\log n) , Ambainis and Watrous presented another important result: They provided [ 1 ] a 2QCFA that recognizes L_{pal} , the language of palindromes on the alphabet \{0,1\} , in exponential expected time. Since no sublogarithmic-space PTM can recognize L_{pal} regardless of its time budget [ 3 ] , this lets one conclude \addcontentsline{lla}{section}{\numberline q:awpal}\mathsf{BPTISP}(2^{O(n)},o(\log n))\subsetneq\mathsf{BQTISP}(2^{O(n)},o(\log n)). (2) Recently, Remscrim showed that one cannot obtain a “tighter” quantum advantage result (with an improved common time bound) than Equation 2 by using L_{pal} to witness the separation: He proved [ 10 ] that no quantum Turing machine (QTM) running in space o(\log n) and expected time 2^{n^{1-\Omega(1)}} can recognize L_{pal} with bounded error. In this paper, we initiate the study of quantum advantage under simultaneous subexponential (i.e. 2^{n^{o(1)}} ) time and \Omega(\log\log n)\cap o(\log n) space bounds. For this purpose, we exhibit an infinite family \mathcal{F} of padding functions in (\log n)^{\omega(1)}\cap n^{o(1)} such that for every f_{i}\in\mathcal{F} , there exists another function f_{i+1}\in\mathcal{F} such that f_{i+1}(n)\in o(f_{i}(n)) , and each such f_{i} corresponds to a different quantum advantage statement of the form \addcontentsline{lla}{section}{\numberline q:sep}\mathsf{BPTISP}(2^{O(f_{i}(n))},o(\log f_{i}(n)))\subsetneq\mathsf{BQTISP}(2^{O(f_{i}(n))},o(\log f_{i}(n))) (3) for a different pair of subexponential time and sublogarithmic space bounds. Each member f_{i} of \mathcal{F} corresponds to a language L_{i} which will be used to witness the corresponding proper inclusion. Each L_{i} will be a collection of “padded palindromes” [ 4 , 11 ] , that is, each member w of L_{i} will have a prefix x that contains a member of L_{pal} , and the length |x| of the palindrome will be bounded by the value f_{i}(|w|) . Our results depend on a technique enabling polynomial-time 2QCFAs to verify this length relation on their input strings for all members of a rich set of padding functions with fine asymptotic granularity. The rest of the paper is structured as follows: Section 2 summarizes the machine definitions and previous work on some 2QCFAs that will be used as subroutines in our constructions. Section 3 describes the common syntax of the family \mathcal{L} of languages that will be used in our proofs, and shows that no member L of that family associated with the padding function f can be recognized by a PTM limited to using o(\log f(n)) space. We conclude the detailed description of \mathcal{L} and the construction of the 2QCFA M_{i} for the language L_{i} witnessing the separation of Equation 3 for any f_{i}\in\mathcal{F} in Section 4 . In Section 5 , we provide a different padding control template using which one can obtain quantum advantage statements where the common space bound is \Theta(\log\log n) and the time bound is “almost” quasi-polynomial, by adapting a technique of Karpinski and Verbeek [ 6 ] to control padding functions which are in (\log n)^{\Theta(f(n))} , where f(n)\in\omega(1) is a minorant of a computable function that can be selected arbitrarily to grow as slowly as desired. Section 6 is a conclusion. 2 PTMs, QTMs, and useful 2QCFAs We will be comparing the capabilities of PTMs and QTMs operating under the same time and space bounds. The formal machine models underlying our discussion are standard [ 2 , 13 , 1 , 9 ] , and the reader is directed to [ 11 ] for a detailed exposition where the definitions are aligned for ease of comparison and inter-model compatibility. The following is a brief overview of the points that are salient for

Read the complete text