Document Open Access Logo

Acceptance Ambiguity for Quantum Automata

Authors Paul C. Bell , Mika Hirvensalo

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.70.pdf
  • Filesize: 487 kB
  • 14 pages

Document Identifiers

Author Details

Paul C. Bell
  • Department of Computer Science, Byrom Street, Liverpool John Moores University, Liverpool, L3-3AF, UK
Mika Hirvensalo
  • Department of Mathematics and Statistics, University of Turku, FI-20014, Turku, Finland

Funding

  • Hirvensalo, Mika: Supported by Väisälä Foundation

Cite As Get BibTex

Paul C. Bell and Mika Hirvensalo. Acceptance Ambiguity for Quantum Automata. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.70

Abstract

We consider notions of freeness and ambiguity for the acceptance probability of Moore-Crutchfield Measure Once Quantum Finite Automata (MO-QFA). We study the distribution of acceptance probabilities of such MO-QFA, which is partly motivated by similar freeness problems for matrix semigroups and other computational models. We show that determining if the acceptance probabilities of all possible input words are unique is undecidable for 32 state MO-QFA, even when all unitary matrices and the projection matrix are rational and the initial configuration is defined over real algebraic numbers. We utilize properties of the skew field of quaternions, free rotation groups, representations of tuples of rationals as a linear sum of radicals and a reduction of the mixed modification Post’s correspondence problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum finite automata
  • matrix freeness
  • undecidability
  • Post’s correspondence problem
  • quaternions

Metrics

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

References

  1. P. C. Bell, S. Chen, and L. M. Jackson. Scalar ambiguity and freeness in matrix semigroups over bounded languages. In Language and Automata Theory and Applications, volume LNCS 9618, pages 493-505, 2016. Google Scholar
  2. P. C. Bell, V. Halava, and M. Hirvensalo. Decision Problems for Probabilistic Finite Automata on Bounded Languages. Fundamenta Informaticae, 123(1):1-14, 2012. Google Scholar
  3. P. C. Bell and I. Potapov. Periodic and infinite traces in matrix semigroups. Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS 4910:148-161, 2008. Google Scholar
  4. P. C. Bell and I. Potapov. Reachability problems in quaternion matrix and rotation semigroups. Information and Computation, 206(11):1353-1361, 2008. Google Scholar
  5. P. C. Bell and I. Potapov. On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. International Journal of Foundations of Computer Science, 21(6):963-978, 2010. Google Scholar
  6. A. Bertoni, G. Mauri, and M. Torelli. Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata. In Automata, Languages and Programming, volume 52 of LNCS, pages 87-94, 1977. Google Scholar
  7. A. S. Besicovitch. On the linear independence of fractional powers of integers. J. London Math. Soc., 15:3-6, 1940. Google Scholar
  8. V. Blondel and V. Canterini. Undecidable problems for probabilistic automata of fixed dimension. Theory of Computing Systems, 36:231-245, 2003. Google Scholar
  9. V. Blondel, E. Jeandel, P. Koiran, and N. Portier. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34:6:1464-1473, 2005. Google Scholar
  10. A. Brodsky and N. Pippenger. Characterizations of 1-way quantum finite automata. SIAM Journal on Computing, 31:1456-1478, 2002. Google Scholar
  11. J. Cassaigne, T. Harju, and J. Karhumäki. On the undecidability of freeness of matrix semigroups. International Journal of Algebra and Computation, 9(3-4):295-305, 1999. Google Scholar
  12. J. Cassaigne and F. Nicolas. On the decidability of semigroup freeness. RAIRO - Theoretical Informatics and Applications, 46(3):355-399, 2012. Google Scholar
  13. É. Charlier and J. Honkala. The freeness problem over matrix semigroups and bounded languages. Information and Computation, 237:243-256, 2014. Google Scholar
  14. C. Choffrut and J. Karhumäki. Some decision problems on integer matrices. Informatics and Applications, 39:125-131, 2005. Google Scholar
  15. T. Colcombet, J. Ouaknine, P. Semukhin, and J. Worrell. On reachability problems for low dimensional matrix semigroups. In ArXiV Manuscript (to appear ICALP'19), volume arXiv:1902.09597, pages 1-15, 2019. Google Scholar
  16. V. Halava, T. Harju, and M. Hirvensalo. Undecidability bounds for integer matrices using Claus instances. International Journal of Foundations of Computer Science (IJFCS), 18,5:931-948, 2007. Google Scholar
  17. M. Hirvensalo. Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages. SOFSEM 2007: Theory and Practice of Computer Science, Lecture Notes in Computer Science, 4362:309-319, 2007. Google Scholar
  18. J. Honkala. Decision problems concerning thinness and slenderness of formal languages. In Acta Informatica, volume 35, pages 625-636, 1998. Google Scholar
  19. R. A. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge University Press, 1991. Google Scholar
  20. D. A. Klarner, J.-C. Birget, and W. Satterfield. On the undecidability of the freeness of integer matrix semigroups. International Journal of Algebra and Computation, 1 (2):223-226, 1991. Google Scholar
  21. S.-K. Ko and I. Potapov. Vector ambiguity and freeness problems in SL(2, ℤ). Fandumenta Informaticae, 162(2-3):161-182, 2018. Google Scholar
  22. W. Kuich and A. Salomaa. Semirings, Automata, Languages, volume 5. Springer, 1986. Google Scholar
  23. E. Lengyel. Mathematics for 3D Game Programming & Computer Graphics. Charles River Media, 2004. Google Scholar
  24. C. Moore and J. P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2):275-306, 2000. Google Scholar
  25. M. S. Paterson. Unsolvability in 3× 3 matrices. Studies in Applied Mathematics, 49(1):105-107, 1970. Google Scholar
  26. A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971. Google Scholar
  27. S. Swierczkowski. A class of free rotation groups. Indag. Math., 5(2):221-226, 1994. 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 About DROPS Imprint Privacy Contact