4 papers
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 . For that purpose, we define i…
Short and useful quantum proofs for sublogarithmic-space verifiers
A. C. Cem Say
Quantum Merlin-Arthur proof systems are believed to be stronger than both their classical counterparts and ``stand-alone'' quantum computers when Arthur is assumed to operate in $Î…
Time hierarchies for sublogarithmic-space quantum computation
A. C. Cem Say
We present new results on the landscape of problems that can be solved by quantum Turing machines (QTM's) employing severely limited amounts of memory. In this context, we demonstr…
Unconditional proofs of quantumness between small-space machines
A. C. Cem Say, M. Utkan Gezer
A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a com…