69
правок
Изменения
Нет описания правки
* Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <math>\Sigma=\{c_1, c_2, c_3, \dots\}</math>. Тогда по описанному определению можно составить матрицы смежности <math>\{U_\alpha | \alpha \in \Sigma \}</math> размерности <tex>[N \times N]</tex>. Так же введем <tex>N</tex> {{---}} размерный вектор <tex>q \in Q</tex>, описывающее состояние ДКА, a <tex>q_0</tex> {{---}} начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <math>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</math>
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются [[wikipedia:Probability amplitude|'''амплитуды вероятностей''']], a матрицы <math>\{U_\alpha\}</math> {{- --}} [https://ru.wikipedia.org/wiki/Унитарная_матрица '''унитарные матрицы'''].
Для ККА характерено геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <math>\{U_\alpha\}</math> {{---}} [https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A8%D1%80%D1%91%D0%B4%D0%B8%D0%BD%D0%B3%D0%B5%D1%80%D0%B0 операторы эволюции в представлении Шредингера].
=== Одномерный квантовый конечный автомат===
Авторы одномерного (англ. ''Measure-one'', ''1-way'') ККА - Cris Moore и James P. Crutchfield (2000). Главное свойство {{- --}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 кубита] <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
