69
правок
Изменения
→Многомерный квантовый конечный автомат
{{Определение
|definition=
'''Многомерный (или Двухмерный) квантовый конечный автомат''' (англ. ''Measure-many'', ''2-way'' ''QFA'') {{---}} это кортеж : <math>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
}}
'''Многомерный''' (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство {{---}} допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время.
Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
