DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2019.70

Acceptance Ambiguity for Quantum Automata

Authors: Paul C. Bell and Mika Hirvensalo

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bell_et_al:LIPIcs.MFCS.2019.70,
  author =	{Bell, Paul C. and Hirvensalo, Mika},
  title =	{{Acceptance Ambiguity for Quantum Automata}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.70},
  URN =		{urn:nbn:de:0030-drops-110149},
  doi =		{10.4230/LIPIcs.MFCS.2019.70},
  annote =	{Keywords: Quantum finite automata, matrix freeness, undecidability, Post’s correspondence problem, quaternions}
}

Search Results

Documents authored by Hirvensalo, Mika

Acceptance Ambiguity for Quantum Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message