Quantum Information & Computation
Volume 25, Issue 1
RESEARCH ARTICLE Open access

Unconditional Proofs of Quantumness Between Small-Space Machines

A. C. Cem Say, M. Utkan Gezer

Author affiliations
  • A. C. Cem Say1
  • M. Utkan Gezer1
  1. Department of Computer Engineering, Boğaziçi University, Bebek, İstanbul, Türkiye

pp. 36-56 · 10.2478/qic-2025-0002

Read PDF View on Reference Global
On this page

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 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.
Open accessCC BY-NC-ND 4.0

Keywords

  • proofs of quantumness
  • interactive proof systems
  • probabilistic Turing machines
  • quantum finite automata

Suggested citation

A. C. Cem Say, M. Utkan Gezer (2025). Unconditional Proofs of Quantumness Between Small-Space Machines. Quantum Information & Computation, 25(1), 36-56. https://doi.org/10.2478/qic-2025-0002

Download BibTeX

References (34)

  1. 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.Google Scholar
  2. 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.DOI: 10.1137/S0097539795293172Google Scholar
  3. U. Mahadev (2022). “Classical verification of quantum computations”. SIAM Journal on Computing, 51: 4, 1172–1229.DOI: 10.1137/20M1371828Google Scholar
  4. O. Regev (2009). “On lattices, learning with errors, random linear codes, and cryptography”. Journal of the ACM, 56: 6.DOI: 10.1145/1568318.1568324Google Scholar
  5. W. Zhan (2023). “Randomness and quantumness in space-bounded computation”. Ph.D thesis, Princeton University.Google Scholar
  6. U. Girish, R. Raz, and W. Zhan (2024). “Quantum logspace computations are verifiable”, in 2024 Symposium on Simplicity in Algorithms (SOSA), pp. 144–150.DOI: 10.1137/1.9781611977936.14Google Scholar
  7. C. Dwork, and L. Stockmeyer (1992). “Finite state verifiers I: The power of interaction”. Journal of the ACM, 39: 4, 800–828.DOI: 10.1145/146585.146599Google Scholar
  8. 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.DOI: 10.1007/3-540-58201-0_100Google Scholar
  9. A. Ambainis and J. Watrous (2002). “Two-way finite automata with quantum and classical states”. Theoretical Computer Science, 287: 1, 299–311.DOI: 10.1016/S0304-3975(02)00138-XGoogle Scholar
  10. 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.DOI: 10.26421/QIC17.11-12-6Google Scholar
  11. 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/.Google Scholar
  12. 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.DOI: 10.4171/automata-2/17Google Scholar
  13. A.C. Cem Say and A. Yakaryılmaz. (2014). “Finite state verifiers with constant randomness”. Logical Methods in Computer Science, 10: 3.DOI: 10.2168/LMCS-10(3:6)2014Google Scholar
  14. M. Utkan Gezer and A. C. Cem Say (2022). “Constant-space, constant-randomness verifiers with arbitrarily small error”. Information and Computation, 288, 104744.DOI: 10.1016/j.ic.2021.104744Google Scholar
  15. M. Utkan Gezer, Ö. Dolu, N. Ersoy, and A. C. Cem Say (2023). “Real-time, constant-space, constantrandomness verifiers”. Theoretical Computer Science, 976, 114155.DOI: 10.1016/j.tcs.2023.114155Google Scholar
  16. M. Utkan Gezer and A. C. Cem Say (2024). “P has polynomial-time finite-state verifiers.” https://arxiv.org/abs/2306.09542.Google Scholar
  17. A. Yakaryılmaz and A. C. Cem Say (2010). “Languages recognized by nondeterministic quantum finite automata”. Quantum Information and Computation, 10: 9, 747–770.DOI: 10.26421/QIC10.9-10-3Google Scholar
  18. 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.DOI: 10.46298/dmtcs.509Google Scholar
  19. E. Bernstein and U. Vazirani (1997). “Quantum complexity theory”. SIAM Journal on Computing, 26: 1411–1473.DOI: 10.1137/S0097539796300921Google Scholar
  20. R. Freivalds (1981). “Probabilistic two-way machines”, in Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 33–45.DOI: 10.1007/3-540-10856-4_72Google Scholar
  21. 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.DOI: 10.1137/0219069Google Scholar
  22. M. A. Nielsen and I. L. Chuang (2002). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.DOI: 10.1119/1.1463744Google Scholar
  23. J. Watrous (2003). “On the complexity of simulating space-bounded quantum computations”. Computational Complexity, 12, 48–84.DOI: 10.1007/s00037-003-0177-8Google Scholar
  24. 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.Google Scholar
  25. P. Turakainen (1969). “On languages representable in rational probabilistic automata”. Annales Academiæ Scientiarum Fennicæ, (439).DOI: 10.5186/aasfm.1969.439Google Scholar
  26. Ioan Macarie (1993). “Closure properties of stochastic languages”. Technical Report 441, University of Rochester.Google Scholar
  27. Paavo Turakainen (1982). “Rational stochastic automata in formal language theory”, in Discrete Mathematics, volume 7 of Banach Center Publications. PWN.DOI: 10.4064/-7-1-31-44Google Scholar
  28. A. Shamir (1992). “IP = PSPACE”. Journal of the ACM, 39: 4, 869–877.DOI: 10.1145/146585.146609Google Scholar
  29. 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.DOI: 10.1016/j.tcs.2010.08.024Google Scholar
  30. S. Arora and B. Barak. (2009). Computational Complexity: A Modern Approach. New York: Cambridge University Press.DOI: 10.1017/CBO9780511804090Google Scholar
  31. 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.DOI: 10.1103/PhysRevLett.23.880Google Scholar
  32. A. Condon and R. Ladner (1995). “Interactive proof systems with polynomially bounded strategies”. Journal of Computer and System Sciences, 50: 3, 506–518.DOI: 10.1006/jcss.1995.1040Google Scholar
  33. S. Goldwasser, Y. T. Kalai, and G. N. Rothblum (2015). “Delegating computation: Interactive proofs for muggles”. Journal of the ACM, 62: 4.DOI: 10.1145/2699436Google Scholar
  34. J. Shallit and Y. Breitbart. (1996). “Automaticity I: Properties of a measure of descriptional complexity”. Journal of Computer and System Sciences, 53, 10–25.DOI: 10.1006/jcss.1996.0046Google Scholar