Decidable and undecidable problems about quantum automata

Simple item page
dc.creatorBlondel, Vincent D.
dc.creatorJeandel, Emmanuel
dc.creatorKoiran, Pascal
dc.creatorPortier, Natacha
dc.date2003-04-11
dc.date.accessioned2026-07-07T06:06:34Z
dc.date.available2026-07-07T06:06:34Z
dc.descriptionWe study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
dc.description10 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/0304082
dc.identifierhttp://arxiv.org/abs/quant-ph/0304082
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91018
dc.subjectQuantum Physics
dc.titleDecidable and undecidable problems about quantum automata
dc.typetext

Files

Collections

arXiv