Изменения
→Описание
* Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <math>\Sigma=\{c_1, c_2, c_3, ..\}</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,.. \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <math>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</math>
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются '''амплитуды вероятностей''', a матрицы <math>\{U_\alpha\}</math> - '''унитарные матрицы'''.
Интересное свойство ККА - геометрическая интерпретация в пространстве <tex>CP^N</tex>.С этой стороны вектор <tex>q</tex> является точкой, a <math>\{U_\alpha\}</math> - операторы эволюции в представлении Шредингера.
В дополнении для ККА можно упомянуть пару особенностей :
* НКА. Из-за свойство НКА в векторе <tex>q</tex> и в столбцах матриц <math>\{U_\alpha\}</math> может находиться несколько <tex>1</tex>. Если в этом случаи рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одно научно-исследовательских задач в теории ККА.
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы для <math>\{U_\alpha\}</math> и вектор вероятностей состояний для <tex>q</tex>.Одно из свойств <tex>q</tex> - сумма всех элементов равна <tex>1</tex> и для того чтобы во всех переходах сохранялось это свойство и нужны стохастические матрицы.
=== Одномерный квантовый конечный автомат===
