0000000000203159
AUTHOR
Vasilijs Kravcevs
showing 5 related works from this author
Kvantu algoritmu sarežģītības novērtējumi
2008
Anot¯acija Kvantu algoritmu veiktsp¯ejas p¯ar¯akums par klasiskajiem algoritmiem ir gal- venais iemesls paˇsreiz¯ejai lielai ieinteres¯et¯ibai par kvantu skaitl¸oˇsanu. Vieni no slaven¯akiem kvantu algoritmiem ir Grovera mekl¯eˇsanas algoritms un ˇSora skaitl¸u faktoriz¯acijas algoritms. Piem¯eram, Grovera algoritms atrisina el- ementa mekl¯eˇsanas probl¯emu N elementu sarakst¯a ar laiku Ø(pN), kaut klasiskam algoritmam ir nepiecieˇsams (N) laiks, lai atrisin¯atu ˇso probl¯emu. T¯atad m¯es esam l¸oti ieienteres¯eti atrast ˇs¯adas probl¯emas, kur¯am kvantu al- goritms var b¯ut par¯aks par klasisko analogu. Kvantu skaitl¸oˇsanas centr¯alais jaut¯ajums ir, cik sp¯ec¯ıgi ir kvantu algoritmi? C…
On a class of languages recognizable by probabilistic reversible decide-and-halt automata
2009
AbstractWe analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations.
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
2011
We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
2011
We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
Quantum algorithm complexity
2008
Elektroniskā versija nesatur pielikumus