69
правок
Изменения
Нет описания правки
Для начало воспользуемся графовым представлением [[Детерминированные конечные автоматы|ДКА]]. Пусть в нем <tex>N</tex> вершин и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться [[Матрица смежности графа|Матрицей смежности]] <tex>[N \times N]</tex> для каждого символа <tex> c \in \Sigma</tex>, в котором <tex>1</tex> означает переход из состояние <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> - его отсутствие. В этом случаи, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенный ''умножением матриц''.
* Пусть у нас есть ДКА с <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/Унитарная_матрица '''унитарные матрицы'''].
<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> {{- --}} [https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D0.B0.D1.8F_.D0.BE.D0.B1.D0.BE.D0.BB.D0.BE.D1.87.D0.BA.D0.B0 линейная оболочка]
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в <math>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}</math>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно :
:<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{- --}} входящая строчка
{{Определение
|definition=
'''Многомерный квантовый конечный автомат''' {{- --}} это кортеж : <math>(Q;\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
