Теория конечных квантовых автоматов (обзор)

Abstract

В работе рассмотрено многообразие существующих моделей квантовых автоматов. Выделены модели, которые принято называть конечными квантовыми автоматами, также модели, которые таковыми не являются (так как они используют средства, не применяемые для классических конечно-автоматных моделей). Приведены основные результаты, связанные с анализом эквивалентности конечных квантовых автоматов.

У роботi розглянуто рiзноманiття iснуючих моделей квантових автоматiв. Видiлено моделi, якi прийнято називати скiнченними квантовими автоматами, а також моделi, що не є такими (оскiльки засоби, якi у них використано, не застосовуються для класичних скiнченно-автоматних моделей). Наведено основнi результати, пов’язанi з аналiзом еквiвалентностi скiнченних квантових автоматiв.

In the given paper it is considered variety of models for quantum automata. There are extracted models, which are called finite quantum automata, as well as the ones which are not models for finite quantum automata (since they explore these or the other tools which are not used for classical finite-automata models). Basic results connected with analysis of equivalency of finite quantum automata are listed.