Document Open Access Logo

Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines

Author Zachary Remscrim

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.39.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Zachary Remscrim
  • Department of Computer Science, The University of Chicago, IL, USA

Acknowledgements

The author would like to express his sincere gratitude to Professor Michael Sipser for many years of mentorship and support, without which this work would not have been possible, and to thank Professor Richard Lipton, as well as the anonymous reviewers, for several helpful comments on an earlier draft of this paper.

Cite AsGet BibTex

Zachary Remscrim. Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.39

Abstract

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language L_{pal} = {w ∈ {a,b}^*:w is a palindrome} with bounded error in expected time 2^{O(n)}. We prove that their result cannot be improved upon: a 2QCFA (of any size) cannot recognize L_{pal} with bounded error in expected time 2^{o(n)}. This is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space o(log n) and expected time 2^{n^{1-Ω(1)}} cannot recognize L_{pal} with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or o(log n)-space QTM that recognizes any language L in terms of a natural "hardness measure" of L. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computation
  • Lower bounds
  • Finite automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Leonard Adleman. Two theorems on random polynomial time. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages 75-83. IEEE, 1978. Google Scholar
  2. Andris Ambainis and John Watrous. Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1):299-311, 2002. Google Scholar
  3. Andris Ambainis and Abuzer Yakaryılmaz. Automata and quantum computing. arXiv preprint, 2015. URL: http://arxiv.org/abs/1507.01988.
  4. Ao V Anisimov. Group languages. Cybernetics and Systems Analysis, 7(4):594-601, 1971. Google Scholar
  5. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505-510, 2019. Google Scholar
  6. J-C Birget, A Yu Ol’shanskii, Eliyahu Rips, and Mark V Sapir. Isoperimetric functions of groups and computational complexity of the word problem. Annals of Mathematics, pages 467-518, 2002. Google Scholar
  7. Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1-3), 1983. Google Scholar
  8. Anne Condon, Lisa Hellerstein, Samuel Pottle, and Avi Wigderson. On the power of finite automata with both nondeterministic and probabilistic states. SIAM Journal on Computing, 27(3):739-762, 1998. Google Scholar
  9. Martin J Dunwoody. The accessibility of finitely presented groups. Inventiones mathematicae, 81(3):449-457, 1985. Google Scholar
  10. Cynthia Dwork and Larry Stockmeyer. A time complexity gap for two-way probabilistic finite-state automata. SIAM Journal on Computing, 19(6):1011-1023, 1990. Google Scholar
  11. Cynthia Dwork and Larry Stockmeyer. Finite state verifiers I: The power of interaction. Journal of the ACM (JACM), 39(4):800-828, 1992. Google Scholar
  12. Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation, 2020. URL: http://arxiv.org/abs/2006.03530.
  13. Rūsiņš Freivalds. Probabilistic two-way machines. In International Symposium on Mathematical Foundations of Computer Science, pages 33-45. Springer, 1981. Google Scholar
  14. Albert G Greenberg and Alan Weiss. A lower bound for probabilistic algorithms for finite state machines. Journal of Computer and System Sciences, 33(1):88-105, 1986. Google Scholar
  15. Michael Gromov. Groups of polynomial growth and expanding maps (with an appendix by Jacques Tits). Publications Mathématiques de l'IHÉS, 53:53-78, 1981. Google Scholar
  16. Lov K Grover. A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium of Theory of Computing, pages 212-219, 1996. Google Scholar
  17. Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. Google Scholar
  18. Fred C Hennie. One-tape, off-line Turing machine computations. Information and Control, 8(6):553-578, 1965. Google Scholar
  19. Thomas Herbst. On a subclass of context-free groups. RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications, 25(3):255-272, 1991. Google Scholar
  20. Derek F Holt, Sarah Rees, Claas E Röver, and Richard M Thomas. Groups with context-free co-word problem. Journal of the London Mathematical Society, 71(3):643-657, 2005. Google Scholar
  21. Clara Löh. Geometric group theory. Springer, 2017. Google Scholar
  22. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing, 8(1):1-51, 2012. Google Scholar
  23. David E Muller and Paul E Schupp. Groups, the theory of ends, and context-free languages. Journal of Computer and System Sciences, 26(3):295-310, 1983. Google Scholar
  24. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  25. Michael O Rabin and Dana Scott. Finite automata and their decision problems. IBM journal of research and development, 3(2):114-125, 1959. Google Scholar
  26. Zachary Remscrim. Lower bounds on the running time of two-way quantum finite automata and sublogarithmic-space quantum turing machines, 2020. URL: http://arxiv.org/abs/2003.09877.
  27. Zachary Remscrim. The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 139:1-139:18, 2020. Google Scholar
  28. AC Say and Abuzer Yakaryilmaz. Magic coins are useful for small-space quantum machines. Quantum Information & Computation, 17(11-12):1027-1043, 2017. Google Scholar
  29. Jeffrey Shallit. Automaticity IV: sequences, sets, and diversity. Journal de théorie des nombres de Bordeaux, 8(2):347-367, 1996. Google Scholar
  30. Jeffrey Shallit and Yuri Breitbart. Automaticity I: Properties of a measure of descriptional complexity. Journal of Computer and System Sciences, 53(1):10-25, 1996. Google Scholar
  31. Peter W Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994. Google Scholar
  32. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 881-890, 2013. Google Scholar
  33. Andreas Thom. Convergent sequences in discrete groups. Canadian Mathematical Bulletin, 56(2):424-433, 2013. Google Scholar
  34. Jacques Tits. Free subgroups in linear groups. Journal of Algebra, 20(2):250-270, 1972. Google Scholar
  35. John Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1-2):48-84, 2003. Google Scholar
  36. John Watrous. Encyclopedia of complexity and system science, chapter quantum computational complexity, 2009. URL: http://arxiv.org/abs/0804.3401.
  37. John Watrous. The theory of quantum information. Cambridge University Press, 2018. Google Scholar
  38. Joseph A Wolf et al. Growth of finitely generated solvable groups and curvature of riemannian manifolds. Journal of differential Geometry, 2(4):421-446, 1968. Google Scholar
  39. Abuzer Yakaryilmaz and AC Cem Say. Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science, 12(4):19-40, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact