Изменения

<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Главной особенностью является допущение некоторого языка за Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные конечные автоматы.

'''Квантовый конечный автомат (ККА)''' (англ. ''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 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> {{---}} входящая строчка* Головка может двигаться в обоих направлениях.* Может гарантированно разрешать регулярный язык.* Может за линейное время разрешать нерегулярный язык.