Квантовые конечные автоматы

Неформально говоря квантовый конечный автомат — это квантовый аналог конечного автомата, который использует квантовые гейты. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.

Определение

Определение:

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

Кроме того, ККА является частным случаем Геометрического конечного автомата и Топологического конечного автомата.

Принцип работы

• На вход подается строчка [math] s = \langle a_0, a_1,\dots ,a_k \rangle, a_i \in \Sigma[/math].
• На выходе мы получаем число [math] Pr(s)[/math], являющееся вероятностью данного конечного автомата быть в допускающем состоянии.

Типы ККА

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

Описание

Для первоначального описание ККА воспользуемся следующим примером. Пусть у нас есть графовое представление ДКА и пусть в нем [math]N[/math] вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором матриц смежности таких, что каждая матрица размера [math][N \times N][/math] и что каждому символу [math]c \in \Sigma[/math] сопоставляется единственная матрица из этого набора. Каждая матрица состоит из [math]0[/math] и [math]1[/math], причём [math]1[/math] означает переход из состояния [math]i[/math] в [math]j[/math] по символу [math]c[/math], а [math]0[/math] — его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности [math]N[/math], в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу [math] c \in \Sigma[/math] обыкновенным умножением матриц.

Пусть у нас есть ДКА с [math]N[/math] вершинами и его [math]\Sigma=\{c_1, c_2, c_3, \dots\}[/math]. Тогда по описанному определению можно составить матрицы смежности [math]\{U_\alpha \mid \alpha \in \Sigma \}[/math] размерности [math][N \times N][/math]. Также введем [math]N[/math]-размерный вектор [math]q \in Q[/math], описывающий состояние ДКА, a [math]q_0[/math] — начальное состояние автомата. Тогда для перехода из состояния [math]q_0[/math] в [math]q[/math] по строчке [math] s = \langle \alpha_0, \alpha_1,\dots \rangle[/math] нужно воспользоваться правилом умножения матриц из линейной алгебры : [math]q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.[/math]

Описанное выше по сути и является ККА, но в [math]q[/math] записываются амплитуды вероятностей такие, что [math]|q|^2 = 1[/math] , a матрицы [math]\{U_\alpha\}[/math] — унитарные матрицы, причем такие матрицы могут не только состоять из [math]0[/math] и [math]1[/math], но и состоять из комплексных чисел. Для ККА характерна геометрическая интерпретация в пространстве [math]CP^N[/math]. С этой стороны вектор [math]q[/math] является точкой, a [math]\{U_\alpha\}[/math] — операторы эволюции в представлении Шредингера .

Кроме того, можно упомянуть несколько особенностей ККА:

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

• Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы для [math]\{U_\alpha\}[/math] и вектор вероятностей состояний для [math]q[/math]. Одно из свойств [math]q[/math] — сумма всех элементов равна [math]1[/math], и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.

• Марковская цепь. При вводе строчек [math]s^n[/math] при больших [math]n[/math] одномерный ККА может быть эквивалентен марковской цепи.

Односторонние квантовые кончные автоматы

Одномерный квантовый конечный автомат

Авторы одномерного (англ. Measure-one) ККА — Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА — допускать регулярный язык. Автомат такого типа с [math]N[/math] состояниями представляется в виде кубита [math]|\psi\rangle[/math] c [math]N[/math] состояниями.

[math]|\psi\rangle \in CP^N[/math].

Такой кубит приносит в пространство метрику Фубини-Штуди [math]\Vert\cdot\Vert[/math]. Матрицы смежности остаются унитарными, а переход в новое сосояние по символу [math]\alpha[/math] :

[math]|\psi'\rangle = U_\alpha |\psi\rangle[/math].

Переход в допускающее состояние производится матрицей-проектором [math] P [N \times N][/math].

Вероятность [math]Pr(s)[/math], где [math]s = (a_0,a_1,\cdots,a_k) [/math] равна :

[math]\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 [/math]

Многомерный квантовый конечный автомат

Определение:

Многомерный квантовый конечный автомат (англ. Measure-many QFA) — это кортеж : [math](Q,\Sigma, \delta, q_0, Q_a, Q_r)[/math], где [math]Q[/math] — базисные ортогональные вектора пр-ва [math]\mathcal{H}_Q[/math], [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова, [math]\delta : Q\times \Sigma \times Q \to \mathbb{C} [/math] — всюду определённая функция перехода автомата, [math]q_0[/math] ­— начальное состояние автомата, [math]Q_a \subset Q[/math] — базисные ортогональные вектора пр-ва [math]\mathcal{H}_a[/math], [math]Q_r \subset Q[/math] — базисные ортогональные вектора пр-ва [math]\mathcal{H}_r[/math].

Многомерный ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство — допускать регулярные языкы.

Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится гильбертово пространство. Пусть у нас есть гильбертово пространство [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] — промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов [math]Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q[/math] соответственно :

[math]\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots [/math] , где [math]\operatorname{span}[/math] — линейная оболочка

Так же в многомерном ККА присутствуют 3 матрицы-проектора : [math]P_a[/math], [math]P_r[/math] и [math] P_{non} [/math] для каждого гильбертово пр-ва :

[math]P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots[/math]

Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в [math]\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}[/math]. В таком случае вероятность автомата находиться в допускающем состоянии равна:

[math]\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2[/math], где [math]s[/math] — входная строчка

Двухсторонние квантовые конечные автоматы

Определение:

Двухсторонний квантовый конечный автомат (англ. 2-way QFA) — это кортеж : [math](Q,\Sigma, \delta, q_0, Q_a, Q_r)[/math], где [math]Q[/math] — множество состояний автомата, [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова, [math]\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\}[/math] — всюду определённая функция перехода автомата, [math]q_0[/math] ­— начальное состояние автомата, [math]Q_a \subset Q[/math] — множество допускающих состояний, [math]Q_r \subset Q[/math] — множество опровергающих состояний.

Отличия от одностороннего :

• Головка может двигаться в обоих направлениях.
• Может гарантированно разрешать регулярный язык.
• Может за линейное время разрешать нерегулярный язык.

См. также

• Детерминированные конечные автоматы
• Недетерминированные конечные автоматы
• Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Источники информации

• Andris Ambainis, QUANTUM FINITE AUTOMATA
• Wikipedia — Quantum finite automata
• SlideShare.net, Seminar on quantum automata (complete)