Изменения

'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, V, q_0, Q_a, Q_r)</mathtex>, где* <tex>Q</tex> — множество состояний автомата,* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,* <tex>V</tex> — функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата,* <tex>Q_a \subset Q</tex> — множество допускающих состояний,* <tex>Q_r \subset Q</tex> — множество опровергающих состояний,* <tex>Q_{non} = Q \setminus (Q_a \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний.

== ОписаниеТипы ККА==* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА {{---}} допускать большинство регулярных языков. Также односторонние ККА делятся на Одномерные ККА и Многомерные ККА.* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допускать нерегулярные языкы.

Для первоначального описание ККА воспользуемся следующим примером. Пусть у нас есть графовое представление [[Детерминированные конечные автоматы|ДКА с ]] и пусть в нем <tex>N</tex> вершинами вершин, и его <math>\Sigma=\{c_1, c_2, c_3, \dots\}</math>все вершины пронумерованы. Тогда по описанному определению для представления такого графа можно составить матрицы воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <mathtex>[N \{U_\alpha \mid \alpha \in \Sigma \}times N]</mathtex> размерности и что каждому символу <tex>[N c \in \times N]Sigma</tex>сопоставляется единственная матрица из этого набора. Так же введем Каждая матрица состоит из <tex>N0</tex> {{---}} размерный вектор и <tex>q \in Q1</tex>, описывающее состояние ДКА, a причём <tex>q_01</tex> {{---}} начальное состояние автомата. Тогда для перехода означает переход из состояния <tex>q_0i</tex> в <tex>qj</tex> по строчке символу <tex> s = \langle \alpha_0c</tex>, а <tex>0</tex> {{---}} его отсутствие. В этом случае, \alpha_1текущее состояние автомата записывается как вектор,\dots \rangleразмерности <tex>N</tex> нужно воспользоваться правилом умножения матриц , в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из линейной алгебры : нынешнего состояние в новое состояние по символу <mathtex>q = c \cdots U_{in \alpha_1} U_{\alpha_0} q_0.Sigma</mathtex>обыкновенным ''умножением матриц''.

Описанное выше по сути Пусть у нас есть ДКА с <tex>N</tex> вершинами и является ККА, но в его <tex>q\Sigma=\{c_1, c_2, c_3, \dots\}</tex> записываются [[wikipedia:Probability amplitude|''амплитуды вероятностей'']], a . Тогда по описанному определению можно составить матрицы смежности <mathtex>\{U_\alpha\mid \alpha \in \Sigma \}</mathtex> размерности <tex> {{---}} [[Унитарный и ортогональный операторы| ''унитарные матрицы'']N \times N]</tex>. Для ККА характерено геометрическая интерпретация в пространстве Также введем <tex>CP^N</tex>. С этой стороны -размерный вектор <tex>q\in Q</tex> является точкой, описывающий состояние ДКА, a <mathtex>\{U_\alpha\}q_0</mathtex> {{---}} операторы эволюции начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в представлении Шредингера <reftex>[https:q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</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> нужно воспользоваться правилом умножения матриц из линейной алгебры : <tex>q = \cdots U_{\alpha_1} U_{---\alpha_0}} Представление Шрёдингера]q_0.</reftex>.

В дополнении для Описанное выше по сути и является ККА можно упомянуть пару особенностей , но в <tex>q</tex> записываются амплитуды вероятностей<ref>[https: //en.wikipedia.org/wiki/Probability_amplitude Wikipedia {{---}} Probability amplitude]</ref> такие, что <tex>|q|^2 = 1</tex> , a матрицы <tex>\{U_\alpha\}</tex> {{---}} [[Унитарный и ортогональный операторы| унитарные матрицы]], причем такие матрицы могут не только состоять из <tex>0</tex> и <tex>1</tex>, но и состоять из комплексных чисел. Для ККА характерна геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <tex>\{U_\alpha\}</tex> {{---}} операторы эволюции в представлении Шредингера <ref>[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 Википедия {{---}} Представление Шрёдингера]</ref>.

Кроме того, можно упомянуть несколько особенностей ККА:  * НКА. Из-за свойство свойства НКА в векторе <tex>q</tex> и в столбцах матриц <mathtex>\{U_\alpha\}</mathtex> может находиться несколько <tex>1</tex>. Если в этом случаи случае рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одно одной из научно-исследовательских задач в теории ККА.

* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 Википедия {{---}} Стохастическая матрица]</ref> для <mathtex>\{U_\alpha\}</mathtex> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> {{---}} сумма всех элементов равна <tex>1</tex> , и для того , чтобы во всех переходах сохранялось это свойство , и нужны стохастические матрицы.

Авторы '''одномерного''' (англ. ''Measure-one'', ''1-way'') ККА {{---}} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].В таком виде конечный автомат Автомат такого типа с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <mathtex>|\psi\rangle</mathtex> c <tex>N</tex> состояниями. :<mathtex>|\psi\rangle \in CP^N</mathtex>.

Такой кубит приносит в пространство метрику Фубини-Штуди<ref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <mathtex>\Vert\cdot\Vert</mathtex>.

:<mathtex>|\psi'\rangle = U_\alpha |\psi\rangle</mathtex>.Переход в допускающее состояние производиться производится матрицей-проектором<ref>[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) Википедия {{---}} Проектор]</ref> <tex> P [N \times N]</tex>.

:<mathtex>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </mathtex>

'''Многомерный (или Двухмерный) квантовый конечный автомат''' (англ. ''Measure-many'', ''2-way'' ''QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</mathtex>, где* <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>.

'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Главное Его главное свойство {{---}} допускать нерегулярный язык регулярные языкы. Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>L = \mathcal{a^mb^m\H}_Q</tex> за линейное время. :

Принципы многомерного ККА очень схож с Одномерным<tex>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</tex> , где <tex> \mathcal{H}_a </tex> {{---}} допускающее пр-во , за исключением применение матрицы <tex>P\mathcal{H}_r </tex> после каждого итерации символа строки{{---}} отвергающее пр-во , <tex> \mathcal{H}_{non} </tex> {{---}} промежуточное пр-во. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство каждого пр-ва существует набор базисных ортогональных векторов <mathtex>Q , Q_a \subset Q, Q_r \mathcalsubset Q , Q_{Hnon}_Q\subset Q</mathtex> соответственно :

:<mathtex>\mathcal{H}_Q_a=\mathcaloperatorname{Hspan}_a \oplus {|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \oplus dots , \mathcal{H}_{non}= \dots </mathtex> , где <mathtex> \mathcaloperatorname{Hspan}_a </mathtex> {{---}} допускающее пр-во , линейная оболочка<mathref> \mathcal{H}_r <[https://en.wikipedia.org/math> {{---}} отвергающее пр-во , <math> \mathcal{H}_{non} <wiki/math> Linear_span Wikipedia {{---}} промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset QLineal span]</texref> соответственно :

Так же в многомерном ККА присутствуют 3 матрицы-проектора :<mathtex>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots P_a</mathtex> , где <mathtex>\operatorname{span}P_r</mathtex> {{---}} линейная оболочкаи <reftex>[https://en.wikipedia.org/wiki/Linear_span Wikipedia P_{{---}non} Lineal span]</reftex> для каждого гильбертово пр-ва :

Так же в многомерном ККА присутствуют 3 матрицы-проектора : <mathtex>P_a</math>:\mathcal{H}_Q \to \mathcal{H}_a , <math>P_r</math> и <math> = \dots, P_{non} = \dots</mathtex> для каждого гильбертово пр-ва :

:Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в <mathtex>P_a:\mathcal{H}_Q \to _a, \mathcal{H}_a _r , P_r = \dots, P_mathcal{H}_{non} = \dots</mathtex>. В таком случае вероятность автомата находиться в допускающем состоянии равна:

Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в :<mathtex>\mathcaloperatorname{HPr}_a(s) = \Vert P_a |\psi\rangle \Vert^2</tex>, \mathcalгде <tex>s</tex> {{---}} входная строчка ==Двухсторонние квантовые конечные автоматы=={{Определение|definition='''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{H---}_r } это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где* <tex>Q</tex> — множество состояний автомата,* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова, * <tex>\mathcaldelta : Q\times \Sigma \times Q \to \mathbb{HC}_\times \{non-1,0,1\}</mathtex>— всюду определённая функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата,* <tex>Q_a \subset Q</tex> — множество допускающих состояний,* <tex>Q_r \subset Q</tex> — множество опровергающих состояний. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно : }}

Отличия от одностороннего :<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{---}} входящая строчка* Головка может двигаться в обоих направлениях.* Может гарантированно разрешать регулярный язык.* Может за линейное время разрешать нерегулярный язык.