Unconditional proofs of quantumness between small-space machines

A. C. Cem Say; M. Utkan Gezer

arxiv: 2412.02662 · v1 · submitted 2024-12-03 · 💻 cs.CC · cs.FL· quant-ph

Unconditional proofs of quantumness between small-space machines

A. C. Cem Say , M. Utkan Gezer This is my paper

Pith reviewed 2026-05-23 08:14 UTC · model grok-4.3

classification 💻 cs.CC cs.FLquant-ph

keywords proof of quantumnesssmall space complexityunconditional protocolsquantum vs classicalinteractive proofsspace-bounded computationTuring machines

0 comments

The pith

New problems let classical verifiers confirm quantum computation unconditionally under o(log log n) space bounds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a new class of computational problems that quantum machines solve in polynomial time with space o(log log n). These problems are impossible for probabilistic Turing machines under the same space bound, a fact established by prior unconditional results. The problems also admit small-space quantum proofs of their solutions to classical verifiers that use matching resources. This combination yields a protocol in which a polynomial-time classical verifier decides whether the tested machine is quantum, without depending on any unproven hardness assumptions. A sympathetic reader cares because existing proofs of quantumness always required such assumptions, limiting their reliability.

Core claim

The authors introduce problems that quantum machines solve in polynomial time, that probabilistic Turing machines cannot solve under space o(log log n), and whose solutions a small-space quantum machine can prove to a classical machine with the same space bound. These problems support a protocol in which the verifier's verdict on quantumness holds unconditionally.

What carries the argument

A new class of problems that are quantum-solvable in polynomial time, classically impossible under o(log log n) space, and admit small-space quantum proofs to classical verifiers.

If this is right

A classical polynomial-time verifier can decide quantumness of a small-space machine without any unproven assumptions.
Both the tested machine and the verifier can operate under identical o(log log n) space bounds.
Quantum machines can demonstrate solutions that classical machines provably cannot mimic in this space regime.
The protocol applies to any setting where unconditional classical impossibilities under small space are already known.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same construction might apply in other resource-bounded models where unconditional separations between classical and quantum computation exist.
Device designers could use these problems to certify quantum hardware that must operate with extremely limited memory.
The approach may connect to broader questions about interactive proofs when both parties face strict space limits.

Load-bearing premise

The new problems must remain unsolvable by probabilistic Turing machines under the o(log log n) space bound.

What would settle it

Exhibiting a probabilistic Turing machine that solves one of the new problems while using only o(log log n) space would falsify the protocol's unconditional claim.

Figures

Figures reproduced from arXiv: 2412.02662 by A. C. Cem Say, M. Utkan Gezer.

**Figure 1.** Figure 1: A verifier V for a language recognized by 2dfa(2) M. V does not trust P, which may lie about H1’s readings in attempts to trick V into accepting or even looping forever without reaching a halting state when the input is not in L. V will therefore rely on P’s messages with a very low probability p ∈ (0, 0.5), and validate that P is indeed transmitting N1’s head readings with the remaining high probability, … view at source ↗

**Figure 2.** Figure 2: depicts an “honest” prover algorithm that leads V to acceptance with probability 1 whenever the input string w is in L: No matter what sequence of random choices is made by V , all rounds will be completed without rejection, since the prover is faithful to N1, and simulations of M based on its transmissions for the readings of H1 end in acceptance by M. The runtime of V in this case is polynomially bounded… view at source ↗

**Figure 3.** Figure 3: A verifier based on a DS-FK problem PAD(L), PAD L , where L ∈ 2DFA(2s). On input xy of length n, such that x ∈ Σ ∗ , |x| = log2 n, and y ∈ ⋆ ∗ for ⋆ /∈ Σ: Run the qtm QL (codified to treat only the x segment on the tape as its input string) to decide whether x is in L or not. At every step during this procedure, give the answer still computing to each question of the verifier. When QL halts, send its res… view at source ↗

**Figure 4.** Figure 4: A quantum prover based on PAD(L), PAD L , where L ∈ BQTISP∗(2kn, s(n)) ∩ 2DFA(2s). 112DFA(2s) is closed under complementation. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗

**Figure 5.** Figure 5: A verifier V based on (PAD(SQUARE), PAD(SUBSQUARE)) the number of symbols that V will request from P. That algorithm’s expected runtime is O(m2 r ), where m is the length of the string it is working on, r is the number of coins it tosses during a single pass of that string, and the parameters cF and dF determine the constant of proportionality “hidden” by the big-O notation [8]. In this case, the promise o… view at source ↗

**Figure 6.** Figure 6: A quantum prover based on (PAD(SQUARE), PAD(SUBSQUARE)) strategies about which symbols to transmit in response to the verifier’s subsequent requests: Strategy 1: Transmit a sequence which fails to match the “expected” pattern (z i−1#)+ in at least one position among the first iK2 kF i symbols Strategy 2: Transmit a sequence whose first iK2 kF i symbols match the “expected” pattern (z i−1#)+ If P C employs … view at source ↗

read the original abstract

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 computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds $\mathit{o}(\log \log n)$. Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems, and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be "proved" by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds new problems on prior unconditional classical space separations to get an assumption-free proof-of-quantumness protocol in the o(log log n) regime.

read the letter

The central claim is a protocol for testing quantumness between small-space machines without relying on unproven assumptions. The authors take prior unconditional results showing that probabilistic Turing machines can't solve certain problems in o(log log n) space and build new problems on top of that. These new problems are solvable by quantum machines, and solutions can be verified via a small-space quantum proof to a classical verifier with matching space bounds. The verifier itself runs in polynomial time. This approach is new in combining those elements for an unconditional setting in the small-space regime. It builds directly on existing classical separations rather than introducing new assumptions. The paper does a reasonable job framing the problem and stating the properties the new problems must satisfy. However, the actual definitions of the problems and the proofs that they inherit the hardness, admit quantum solutions within space, and support the proof system are not visible in the abstract. The stress-test concern is on point: the reduction must be tight enough that a classical o(log log n)-space machine solving the new problem would contradict the known result, the quantum algorithm must not use more space, and the verification must not be bypassable by classical means. The poly-time classical verifier must also operate within the space constraint during verification. If those pieces are handled correctly in the full paper, the result stands. If there's a gap in how the hardness transfers or in the space accounting for the proof, the unconditional guarantee weakens. This kind of work is aimed at researchers in quantum complexity theory who care about resource-bounded verification and unconditional separations. A reader looking for new protocols in restricted models would find value if the technical details hold. It is coherent on its own terms and engages with the literature on space-bounded computation. I think it deserves a serious referee to check the constructions and proofs.

Referee Report

3 major / 2 minor

Summary. The paper defines a new class of problems that are polynomial-time solvable by quantum machines with o(log log n) space, unconditionally impossible for classical probabilistic Turing machines under the same space bound (by reduction from known unconditional classical separations), and admit small-space quantum proofs verifiable by a classical machine with matching space. These problems are used to construct a protocol allowing a polynomial-time classical verifier to test quantumness of a device with comparable resources, without relying on unproven hardness assumptions.

Significance. If the reductions and protocol hold, this yields the first unconditional proof-of-quantumness result in the o(log log n)-space regime. It leverages existing unconditional classical lower bounds rather than cryptographic or average-case assumptions, providing a concrete separation that is falsifiable via the space-bounded model.

major comments (3)

[§3] §3 (Problem Definitions): The reduction showing that any classical o(log log n)-space solver for the new problems yields a solver for a known unconditionally hard instance must be checked for exact space preservation; if the reduction increases space by even a log log log n factor, the unconditional claim fails.
[§4.2] §4.2 (Quantum Algorithm): The claimed quantum algorithm must be shown to run in o(log log n) space while solving the problem in polynomial time; the space analysis for the quantum circuit or QTM simulation is load-bearing for the quantum solvability claim.
[§5] §5 (Proof System): The small-space quantum proof must be verified by a classical verifier also restricted to o(log log n) space; if verification requires more space or allows a classical prover to bypass the hardness, the protocol does not establish quantumness.

minor comments (2)

Notation for space bounds (o(log log n)) should be defined explicitly at first use, including whether it is worst-case or average-case over input length n.
The abstract claims 'polynomial-time solvable for quantum machines' but the space bound is the distinguishing resource; clarify the time bound for the quantum solver in the main text.

Simulated Author's Rebuttal

3 responses · 0 unresolved

Thank you for the thorough review of our paper on unconditional proofs of quantumness in the o(log log n) space regime. We address each of the major comments point by point below, providing clarifications and indicating where revisions will be made to strengthen the manuscript.

read point-by-point responses

Referee: [§3] §3 (Problem Definitions): The reduction showing that any classical o(log log n)-space solver for the new problems yields a solver for a known unconditionally hard instance must be checked for exact space preservation; if the reduction increases space by even a log log log n factor, the unconditional claim fails.

Authors: We agree that precise space preservation is crucial for the unconditional result. Upon re-examination, our reduction in Section 3 maps instances using a function computable in O(1) space, without introducing any additional log log factors. To address the concern, we will add a dedicated paragraph and a lemma explicitly proving that the space complexity remains o(log log n) after reduction. This will make the argument fully rigorous. revision: yes
Referee: [§4.2] §4.2 (Quantum Algorithm): The claimed quantum algorithm must be shown to run in o(log log n) space while solving the problem in polynomial time; the space analysis for the quantum circuit or QTM simulation is load-bearing for the quantum solvability claim.

Authors: The quantum algorithm presented in Section 4.2 is based on a quantum circuit that operates with o(log log n) qubits in the workspace, utilizing techniques from small-space quantum computation. The simulation on a quantum Turing machine preserves this bound. We acknowledge that the space analysis could be more explicit, so in the revision we will include a step-by-step accounting of the space usage to confirm it stays within o(log log n) while achieving polynomial time. revision: yes
Referee: [§5] §5 (Proof System): The small-space quantum proof must be verified by a classical verifier also restricted to o(log log n) space; if verification requires more space or allows a classical prover to bypass the hardness, the protocol does not establish quantumness.

Authors: In Section 5, both the quantum prover and the classical verifier are restricted to o(log log n) space. The verification protocol is designed such that the classical verifier uses only o(log log n) space, and we prove soundness against classical provers by reduction to the classical hardness result. We will revise the section to include an explicit statement of the verifier's space bound and a brief argument why a classical prover cannot succeed beyond the negligible probability. revision: yes

Circularity Check

0 steps flagged

No circularity; protocol inherits unconditional classical hardness from external prior results

full rationale

The paper's central claim rests on formulating new problems that inherit impossibility for classical o(log log n)-space PTMs from previously established unconditional separations (cited as external facts), while adding quantum solvability and small-space proof systems. No step in the abstract or described chain reduces a prediction or theorem to a self-fit, self-citation load-bearing premise, or definitional renaming; the verifier verdict is explicitly not conditional on unproven assumptions. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of a new problem class with three simultaneous properties (quantum solvability, classical impossibility, and small-space provability) whose details are not supplied in the abstract.

axioms (1)

domain assumption Probabilistic Turing machines with o(log log n) space cannot solve certain computational problems (unconditionally proven).
Invoked in the abstract as the foundation for classical impossibility.

pith-pipeline@v0.9.0 · 5705 in / 1152 out tokens · 20415 ms · 2026-05-23T08:14:52.392491+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We formulate a new class of problems... impossible for classical machines... proved by a small-space quantum machine to a classical machine with the same space bound.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

no o(log log n)-space ptm can recognize a nonregular language in polynomial expected time (Dwork-Stockmeyer)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Ambainis and J

A. Ambainis and J. Watrous. Two-way ﬁnite automata with q uantum and classical states. Theoretical Computer Science, 287(1):299–311, 2002

work page 2002
[2]

Ambainis and A

A. Ambainis and A. Yakaryılmaz. Automata and quantum com puting. In J. Pin, editor, Handbook of Automata Theory , pages 1457–1493. European Mathematical Society Publishi ng House, Zürich, Switzerland, 2021

work page 2021
[3]

Arora and B

S. Arora and B. Barak. Computational Complexity: A Modern Approach . Cambridge University Press, USA, 2009

work page 2009
[4]

Bernstein and U

E. Bernstein and U. Vazirani. Quantum complexity theory . SIAM Journal on Computing , 26: 1411–1473, 1997

work page 1997
[5]

Brakerski, V

Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. Sim pler proofs of quantumness. In S. T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Commun ication and Cryptography (TQC 2020) , volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14, Dagstuhl, Germany, 2020. Schloss Dagstuh l – Leibniz-Zent...

work page 2020
[6]

J. F. Clauser, M. E. Horne, A. Shimony, and R. A. Holt. Prop osed experiment to test local hidden-variable theories. Physical Review Letters , 23:880–884, 1969

work page 1969
[7]

Condon and R

A. Condon and R. Ladner. Interactive proof systems with p olynomially bounded strategies. Journal of Computer and System Sciences , 50(3):506–518, 1995. 19In fact, the protocol described in [ 15] is one-way, that is, the prover simply sends the veriﬁer a si ngle proof string, with no further interaction. 21 Unconditional proofs of quantumness between smal...

work page 1995
[8]

Dwork and L

C. Dwork and L. Stockmeyer. A time complexity gap for two- way probabilistic ﬁnite-state automata. SIAM Journal on Computing , 19(6):1011–1023, 1990

work page 1990
[9]

Dwork and L

C. Dwork and L. Stockmeyer. Finite state veriﬁers I: The p ower of interaction. J. ACM , 39(4): 800–828, Oct. 1992

work page 1992
[10]

Freivalds

R. Freivalds. Probabilistic two-way machines. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science , pages 33–45, 1981

work page 1981
[11]

Freivalds and M

R. Freivalds and M. Karpinski. Lower space bounds for ra ndomized computation. In Automata, Languages and Programming. ICALP 1994 , Lecture Notes in Computer Science 820. Springer, 1994

work page 1994
[12]

M. U. Gezer and A. C. C. Say. Constant-space, constant-r andomness veriﬁers with arbitrarily small error. Information and Computation , 288:104744, 2022

work page 2022
[13]

M. U. Gezer and A. C. C. Say. P has polynomial-time ﬁnite-state veriﬁers, 2024. URL https://arxiv.org/abs/2306.09542

work page arXiv 2024
[14]

M. U. Gezer, Ö. Dolu, N. Ersoy, and A. C. C. Say. Real-time , constant-space, constant-ran- domness veriﬁers. Theoretical Computer Science, 976:114155, 2023

work page 2023
[15]

Girish, R

U. Girish, R. Raz, and W. Zhan. Quantum logspace computa tions are veriﬁable. In 2024 Symposium on Simplicity in Algorithms (SOSA) , pages 144–150, 2024

work page 2024
[16]

Goldwasser, Y

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegati ng computation: Interactive proofs for muggles. J. ACM , 62(4), Sept. 2015

work page 2015
[17]

Holzer, M

M. Holzer, M. Kutrib, and A. Malcher. Complexity of mult i-head ﬁnite automata: Origins and directions. Theoretical Computer Science, 412(1–2):83–96, Jan. 2011

work page 2011
[18]

I. Macarie. Closure properties of stochastic language s. Technical Report 441, University of Rochester, 1993

work page 1993
[19]

M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, Cambridge, UK, 2002

work page 2002
[20]

Remscrim

Z. Remscrim. The power of a single qubit: Two-way quantu m ﬁnite automata and the word problem. In A. Czumaj, A. Dawar, and E. Merelli, edit ors, 47th In- ternational Colloquium on Automata, Languages, and Program ming (ICALP 2020) , vol- ume 168 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 139:1–139:18, Dagstuhl, Germany, 2020. Sc...

work page 2020
[21]

Remscrim

Z. Remscrim. Lower bounds on the running time of two-way quantum ﬁnite automata and sublogarithmic-space quantum Turing machines. In J. R. Lee , editor, 12th Innovations in The- oretical Computer Science Conference (ITCS 2021) , volume 185 of Leibniz International Pro- ceedings in Informatics (LIPIcs) , pages 39:1–39:20, Dagstuhl, Germany, 2021. Schloss D...

work page arXiv 2021
[22]

A. C. C. Say and A. Yakaryılmaz. Finite state veriﬁers wi th constant randomness. Logical Methods in Computer Science , 10(3), Aug. 2014

work page 2014
[23]

A. C. C. Say and A. Yakaryılmaz. Magic coins are useful fo r small-space quantum machines. Quantum Information and Computation , 17(11–12):1027–1043, 2017. 22 A. C. Cem Say, M. Utkan Gezer

work page 2017
[24]

Shallit and Y

J. Shallit and Y. Breitbart. Automaticity I: Propertie s of a measure of descriptional complexity. Journal of Computer and System Sciences , 53:10–25, 1996

work page 1996
[25]

A. Shamir. IP = PSPACE. J. ACM , 39(4):869–877, 1992

work page 1992
[26]

P. W. Shor. Polynomial-time algorithms for prime facto rization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484–1509, 1997

work page 1997
[27]

Turakainen

P. Turakainen. On languages representable in rational probabilistic automata. Annales Academiæ Scientiarum Fennicæ, (439), 1969

work page 1969
[28]

Turakainen

P. Turakainen. Rational stochastic automata in formal language theory. In Discrete Mathemat- ics, volume 7 of Banach Center Publications . PWN, 1982

work page 1982
[29]

J. Watrous. On the complexity of simulating space-boun ded quantum computations. Compu- tational Complexity , 12:48–84, 2003

work page 2003
[30]

Yakaryılmaz and A

A. Yakaryılmaz and A. C. C. Say. Succinctness of two-way probabilistic and quantum ﬁnite automata. Discrete Mathematics & Theoretical Computer Science , Vol. 12 no. 4, Jan. 2010

work page 2010
[31]

Yakaryılmaz and A

A. Yakaryılmaz and A. C. C. Say. Languages recognized by nondeterministic quantum ﬁnite automata. Quantum Information and Computation , 10(9):747–770, sep 2010

work page 2010
[32]

faithful

W. Zhan. Randomness and Quantumness in Space-Bounded Computation . PhD thesis, Prince- ton University, 2023. 23 Unconditional proofs of quantumness between small-space m achines Appendix A generalization of Dwork and Stockmeyer’s theorem Theorem 13. Let M be a ptm which recognizes a nonregular language such that for any inp ut w of length n, M runs within...

work page 2023

[1] [1]

Ambainis and J

A. Ambainis and J. Watrous. Two-way ﬁnite automata with q uantum and classical states. Theoretical Computer Science, 287(1):299–311, 2002

work page 2002

[2] [2]

Ambainis and A

A. Ambainis and A. Yakaryılmaz. Automata and quantum com puting. In J. Pin, editor, Handbook of Automata Theory , pages 1457–1493. European Mathematical Society Publishi ng House, Zürich, Switzerland, 2021

work page 2021

[3] [3]

Arora and B

S. Arora and B. Barak. Computational Complexity: A Modern Approach . Cambridge University Press, USA, 2009

work page 2009

[4] [4]

Bernstein and U

E. Bernstein and U. Vazirani. Quantum complexity theory . SIAM Journal on Computing , 26: 1411–1473, 1997

work page 1997

[5] [5]

Brakerski, V

Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. Sim pler proofs of quantumness. In S. T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Commun ication and Cryptography (TQC 2020) , volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14, Dagstuhl, Germany, 2020. Schloss Dagstuh l – Leibniz-Zent...

work page 2020

[6] [6]

J. F. Clauser, M. E. Horne, A. Shimony, and R. A. Holt. Prop osed experiment to test local hidden-variable theories. Physical Review Letters , 23:880–884, 1969

work page 1969

[7] [7]

Condon and R

A. Condon and R. Ladner. Interactive proof systems with p olynomially bounded strategies. Journal of Computer and System Sciences , 50(3):506–518, 1995. 19In fact, the protocol described in [ 15] is one-way, that is, the prover simply sends the veriﬁer a si ngle proof string, with no further interaction. 21 Unconditional proofs of quantumness between smal...

work page 1995

[8] [8]

Dwork and L

C. Dwork and L. Stockmeyer. A time complexity gap for two- way probabilistic ﬁnite-state automata. SIAM Journal on Computing , 19(6):1011–1023, 1990

work page 1990

[9] [9]

Dwork and L

C. Dwork and L. Stockmeyer. Finite state veriﬁers I: The p ower of interaction. J. ACM , 39(4): 800–828, Oct. 1992

work page 1992

[10] [10]

Freivalds

R. Freivalds. Probabilistic two-way machines. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science , pages 33–45, 1981

work page 1981

[11] [11]

Freivalds and M

R. Freivalds and M. Karpinski. Lower space bounds for ra ndomized computation. In Automata, Languages and Programming. ICALP 1994 , Lecture Notes in Computer Science 820. Springer, 1994

work page 1994

[12] [12]

M. U. Gezer and A. C. C. Say. Constant-space, constant-r andomness veriﬁers with arbitrarily small error. Information and Computation , 288:104744, 2022

work page 2022

[13] [13]

M. U. Gezer and A. C. C. Say. P has polynomial-time ﬁnite-state veriﬁers, 2024. URL https://arxiv.org/abs/2306.09542

work page arXiv 2024

[14] [14]

M. U. Gezer, Ö. Dolu, N. Ersoy, and A. C. C. Say. Real-time , constant-space, constant-ran- domness veriﬁers. Theoretical Computer Science, 976:114155, 2023

work page 2023

[15] [15]

Girish, R

U. Girish, R. Raz, and W. Zhan. Quantum logspace computa tions are veriﬁable. In 2024 Symposium on Simplicity in Algorithms (SOSA) , pages 144–150, 2024

work page 2024

[16] [16]

Goldwasser, Y

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegati ng computation: Interactive proofs for muggles. J. ACM , 62(4), Sept. 2015

work page 2015

[17] [17]

Holzer, M

M. Holzer, M. Kutrib, and A. Malcher. Complexity of mult i-head ﬁnite automata: Origins and directions. Theoretical Computer Science, 412(1–2):83–96, Jan. 2011

work page 2011

[18] [18]

I. Macarie. Closure properties of stochastic language s. Technical Report 441, University of Rochester, 1993

work page 1993

[19] [19]

M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, Cambridge, UK, 2002

work page 2002

[20] [20]

Remscrim

Z. Remscrim. The power of a single qubit: Two-way quantu m ﬁnite automata and the word problem. In A. Czumaj, A. Dawar, and E. Merelli, edit ors, 47th In- ternational Colloquium on Automata, Languages, and Program ming (ICALP 2020) , vol- ume 168 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 139:1–139:18, Dagstuhl, Germany, 2020. Sc...

work page 2020

[21] [21]

Remscrim

Z. Remscrim. Lower bounds on the running time of two-way quantum ﬁnite automata and sublogarithmic-space quantum Turing machines. In J. R. Lee , editor, 12th Innovations in The- oretical Computer Science Conference (ITCS 2021) , volume 185 of Leibniz International Pro- ceedings in Informatics (LIPIcs) , pages 39:1–39:20, Dagstuhl, Germany, 2021. Schloss D...

work page arXiv 2021

[22] [22]

A. C. C. Say and A. Yakaryılmaz. Finite state veriﬁers wi th constant randomness. Logical Methods in Computer Science , 10(3), Aug. 2014

work page 2014

[23] [23]

A. C. C. Say and A. Yakaryılmaz. Magic coins are useful fo r small-space quantum machines. Quantum Information and Computation , 17(11–12):1027–1043, 2017. 22 A. C. Cem Say, M. Utkan Gezer

work page 2017

[24] [24]

Shallit and Y

J. Shallit and Y. Breitbart. Automaticity I: Propertie s of a measure of descriptional complexity. Journal of Computer and System Sciences , 53:10–25, 1996

work page 1996

[25] [25]

A. Shamir. IP = PSPACE. J. ACM , 39(4):869–877, 1992

work page 1992

[26] [26]

P. W. Shor. Polynomial-time algorithms for prime facto rization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484–1509, 1997

work page 1997

[27] [27]

Turakainen

P. Turakainen. On languages representable in rational probabilistic automata. Annales Academiæ Scientiarum Fennicæ, (439), 1969

work page 1969

[28] [28]

Turakainen

P. Turakainen. Rational stochastic automata in formal language theory. In Discrete Mathemat- ics, volume 7 of Banach Center Publications . PWN, 1982

work page 1982

[29] [29]

J. Watrous. On the complexity of simulating space-boun ded quantum computations. Compu- tational Complexity , 12:48–84, 2003

work page 2003

[30] [30]

Yakaryılmaz and A

A. Yakaryılmaz and A. C. C. Say. Succinctness of two-way probabilistic and quantum ﬁnite automata. Discrete Mathematics & Theoretical Computer Science , Vol. 12 no. 4, Jan. 2010

work page 2010

[31] [31]

Yakaryılmaz and A

A. Yakaryılmaz and A. C. C. Say. Languages recognized by nondeterministic quantum ﬁnite automata. Quantum Information and Computation , 10(9):747–770, sep 2010

work page 2010

[32] [32]

faithful

W. Zhan. Randomness and Quantumness in Space-Bounded Computation . PhD thesis, Prince- ton University, 2023. 23 Unconditional proofs of quantumness between small-space m achines Appendix A generalization of Dwork and Stockmeyer’s theorem Theorem 13. Let M be a ptm which recognizes a nonregular language such that for any inp ut w of length n, M runs within...

work page 2023