License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.70
URN: urn:nbn:de:0030-drops-110149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11014/
Go to the corresponding LIPIcs Volume Portal

Bell, Paul C. ; Hirvensalo, Mika

Acceptance Ambiguity for Quantum Automata

pdf-format:
LIPIcs-MFCS-2019-70.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bell_et_al:LIPIcs:2019:11014,
  author =	{Paul C. Bell and Mika Hirvensalo},
  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 =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11014},
  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}
}

Keywords: Quantum finite automata, matrix freeness, undecidability, Post's correspondence problem, quaternions
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI