A small 1-way quantum finite automaton

Simple item page
dc.creatorKikusts, Arnolds
dc.date1998-10-22
dc.date.accessioned2026-07-07T06:15:45Z
dc.date.available2026-07-07T06:15:45Z
dc.descriptionWe study 1-way quantum finite automata (QFAs) and compare them with their classical counterparts. We show that 1-way QFAs can be very space efficient. We construct a 1-way QFAs that are quadratically smaller than any equivalent deterministic finite automata and give the correct answer with a large probability by recognizing the languages in a two letter alphabet "the number of the letters a and the number of the letters b are divisible by n".
dc.description7 pages, LATEX, uses article.sty
dc.identifierhttps://arxiv.org/abs/quant-ph/9810065
dc.identifierhttp://arxiv.org/abs/quant-ph/9810065
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93854
dc.subjectQuantum Physics
dc.titleA small 1-way quantum finite automaton
dc.typetext

Files

Collections

arXiv