Изменения

Многомерный (или Двухмерный) (англ. ''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 = ... , \mathcal{H}_{non} = ... </math>  Так же в многомерном ККА присутствуют 3 матрицы-проектора, <math>P_a</math>, <math>P_r</math> and <math>P_{non}</math>для каждого гильбертово пр-ва: :<math>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = ..., 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> - входящая строчка