References
- Z. Brakerski, V. Koppula, U. Vazirani and T. Vidick (2020). “Simpler proofs of quantumness”, in S. T. Flammia (ed.), 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 8:1–8:14, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
- P.W. Shor (1997). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM Journal on Computing, 26: 5, 1484–1509.
- U. Mahadev (2022). “Classical verification of quantum computations”. SIAM Journal on Computing, 51: 4, 1172–1229.
- O. Regev (2009). “On lattices, learning with errors, random linear codes, and cryptography”. Journal of the ACM, 56: 6.
- W. Zhan (2023). “Randomness and quantumness in space-bounded computation”. Ph.D thesis, Princeton University.
- U. Girish, R. Raz, and W. Zhan (2024). “Quantum logspace computations are verifiable”, in 2024 Symposium on Simplicity in Algorithms (SOSA), pp. 144–150.
- C. Dwork, and L. Stockmeyer (1992). “Finite state verifiers I: The power of interaction”. Journal of the ACM, 39: 4, 800–828.
- R. Freivalds and M. Karpinski (1994). “Lower space bounds for randomized computation”, in Automata, Languages and Programming. ICALP 1994, Lecture Notes in Computer Science 820, Springer.
- A. Ambainis and J. Watrous (2002). “Two-way finite automata with quantum and classical states”. Theoretical Computer Science, 287: 1, 299–311.
- A. C. Cem Say and A. Yakaryılmaz (2017). “Magic coins are useful for small-space quantum machines”. Quantum Information and Computation, 17: 11–12, 1027–1043.
- Z. Remscrim (2020). “The power of a single qubit: Two-way quantum finite automata and the word problem”, in A. Czumaj, A. Dawar, and E. Merelli (eds), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), vol. 168 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 139:1–139:18, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://eccc.weizmann.ac.il/report/2019/107/ . - A. Ambainis and A. Yakaryılmaz (2021). “Automata and quantum computing”, in J.-É. Pin (ed.), Handbook of Automata Theory, pp. 1457–1493. Zürich, Switzerland: European Mathematical Society Publishing House.
- A.C. Cem Say and A. Yakaryılmaz. (2014). “Finite state verifiers with constant randomness”. Logical Methods in Computer Science, 10: 3.
- M. Utkan Gezer and A. C. Cem Say (2022). “Constant-space, constant-randomness verifiers with arbitrarily small error”. Information and Computation, 288, 104744.
- M. Utkan Gezer, Ö. Dolu, N. Ersoy, and A. C. Cem Say (2023). “Real-time, constant-space, constantrandomness verifiers”. Theoretical Computer Science, 976, 114155.
- M. Utkan Gezer and A. C. Cem Say (2024). “P has polynomial-time finite-state verifiers.”
https://arxiv.org/abs/2306.09542 . - A. Yakaryılmaz and A. C. Cem Say (2010). “Languages recognized by nondeterministic quantum finite automata”. Quantum Information and Computation, 10: 9, 747–770.
- A. Yakaryılmaz and A. C. Cem Say (2010). “Succinctness of two-way probabilistic and quantum finite automata”. Discrete Mathematics & Theoretical Computer Science, 12: 4.
- E. Bernstein and U. Vazirani (1997). “Quantum complexity theory”. SIAM Journal on Computing, 26: 1411–1473.
- R. Freivalds (1981). “Probabilistic two-way machines”, in Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 33–45.
- C. Dwork and L. Stockmeyer (1990). “A time complexity gap for two-way probabilistic finite-state automata”. SIAM Journal on Computing, 19: 6, 1011–1023.
- M. A. Nielsen and I. L. Chuang (2002). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.
- J. Watrous (2003). “On the complexity of simulating space-bounded quantum computations”. Computational Complexity, 12, 48–84.
- Z. Remscrim (2021). “Lower bounds on the running time of two-way quantum finite automata and sublogarithmicspace quantum Turing machines”, in J. R. Lee (ed.), 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 39:1–39:20, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://arxiv.org/abs/2003.09877 . - P. Turakainen (1969). “On languages representable in rational probabilistic automata”. Annales Academiæ Scientiarum Fennicæ, (439).
- Ioan Macarie (1993). “Closure properties of stochastic languages”. Technical Report 441, University of Rochester.
- Paavo Turakainen (1982). “Rational stochastic automata in formal language theory”, in Discrete Mathematics, volume 7 of Banach Center Publications. PWN.
- A. Shamir (1992). “IP = PSPACE”. Journal of the ACM, 39: 4, 869–877.
- M. Holzer, M. Kutrib, and A. Malcher (2011). “Complexity of multi-head finite automata: Origins and directions”. Theoretical Computer Science, 412: 1–2, 83–96.
- S. Arora and B. Barak. (2009). Computational Complexity: A Modern Approach. New York: Cambridge University Press.
- J. F. Clauser, M. E. Horne, A. Shimony, and R. A. Holt (1969). “Proposed experiment to test local hiddenvariable theories”. Physical Review Letters, 23, 880–884.
- A. Condon and R. Ladner (1995). “Interactive proof systems with polynomially bounded strategies”. Journal of Computer and System Sciences, 50: 3, 506–518.
- S. Goldwasser, Y. T. Kalai, and G. N. Rothblum (2015). “Delegating computation: Interactive proofs for muggles”. Journal of the ACM, 62: 4.
- J. Shallit and Y. Breitbart. (1996). “Automaticity I: Properties of a measure of descriptional complexity”. Journal of Computer and System Sciences, 53, 10–25.