69
правок
Изменения
→Многомерный квантовый конечный автомат
===Многомерный квантовый конечный автомат===
Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. {{Определение|definition='''Многомерный квантовый конечный автомат''' {{---}} это кортеж : <math>(Q;\Sigma, \delta, q_0, Q_a, Q_r)</math>, где* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </tex> —всюду определённая функция перехода автомата* <tex>q_0</tex> — начальное состояние автомата* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</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>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{---}} входящая строчка
==Источники информации==
* Andris Ambainis, [http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QUANTUM FINITE AUTOMATA]
* [[wikipedia:Quantum finite automata | Wikipedia {{---}} Quantum finite automata]]
