69
правок
Изменения
Нет описания правки
=== Одномерный квантовый конечный автомат===
Авторы '''одномерного ''' (англ. ''Measure-one'', ''1-way'') ККА {{--- }} Cris Moore и James P. Crutchfield (2000). Главное свойство {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
}}
'''Многомерный ''' (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство {{--- }} допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время.
Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
<math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math>{{- --}} допускающее пр-во , <math> \mathcal{H}_r </math> {{--- }} отвергающее пр-во , <math> \mathcal{H}_{non} </math> {{- --}} промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
:<math>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots </math> , где <math>\operatorname{span}</math> {{---}} [[wikipedia:Linear span | линейная оболочка]]
