69
правок
Изменения
Нет описания правки
<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.
== Определение ==
==Типы ККА==
* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА {{---}} допущение допускать большинство регулярных языков. Также односторонний односторонние ККА делятся на Одномерные и Многомерные ККА.* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допущение нерегулярных языковдопускать нерегулярные языкы.
== Описание ==
Для первоначального описание ККА воспользуемся следующим примером. Пусть у нас есть графовым представлением графовое представление [[Детерминированные конечные автоматы|ДКА]] и пусть в нем <tex>N</tex> вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <tex>[N \times N]</tex> и что каждому символу <tex>c \in \Sigma</tex> сопоставляется единственная матрица из этого набора. Каждая матрица состоит из <tex>0</tex> и <tex>1</tex>, причём <tex>1</tex> означает переход из состояния <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> {{---}} его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенным ''умножением матриц''.
Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <tex>\Sigma=\{c_1, c_2, c_3, \dots\}</tex>. Тогда по описанному определению можно составить матрицы смежности <tex>\{U_\alpha \mid \alpha \in \Sigma \}</tex> размерности <tex>[N \times N]</tex>. Также введем <tex>N</tex>-размерный вектор <tex>q \in Q</tex>, описывающий состояние ДКА, a <tex>q_0</tex> {{---}} начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <tex>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</tex>
Кроме того, можно упомянуть несколько особенностей ККА:
* НКА. Из-за свойства НКА в векторе <tex>q</tex> и в столбцах матриц <tex>\{U_\alpha\}</tex> может находиться несколько <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> для <tex>\{U_\alpha\}</tex> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> {{---}} сумма всех элементов равна <tex>1</tex>, и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.
}}
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство, а и одномерный {{---}} допускать регулярный языкрегулярные языкы.
Принципы многомерного ККА очень схожи с одномерным, за исключением измерения вероятности после каждой итерации символа строки вместо измерения после полного ввода строчки как у одномерного ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> :
:<tex>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</tex>
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в <tex>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}</tex>. Для того чтобы определить В таком случае вероятность автомата находиться в допускающем состоянии нужно равна:
:<tex>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</tex>, где <tex>s</tex> {{---}} входная строчка
