Изменения
→Описание
* Пусть у нас есть ДКА с <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> записываются [[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 операторы эволюции в представлении Шредингера].
В дополнении для ККА можно упомянуть пару особенностей :
* НКА. Из-за свойство НКА в векторе <tex>q</tex> и в столбцах матриц <math>\{U_\alpha\}</math> может находиться несколько <tex>1</tex>. Если в этом случаи рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одно научно-исследовательских задач в теории ККА.
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы для <math>\{U_\alpha\}</math> и вектор вероятностей состояний для <tex>q</tex>.Одно из свойств <tex>q</tex> - сумма всех элементов равна <tex>1</tex> и для того чтобы во всех переходах сохранялось это свойство и нужны стохастические матрицы.
=== Одномерный квантовый конечный автомат===
В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде кубита <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
Матрицы смежными остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> : <math>|\psi'\rangle</math> = <math>U_\alpha |\psi\rangle</math>.
Переход в допускающее состояние производиться [https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) матрицей-проектором ] <tex> P [N \times N]</tex>.
Вероятность <tex>Pr(s)</tex>, где <tex>s = (a_0,a_1,\cdots,a_k) </tex> равна :
:<math>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </math>
===Многомерный квантовый конечный автомат===
