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

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

Определение

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

Квантовый конечный автомат (ККА) (англ. 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] записываются амплитуды вероятностей, a матрицы [math]\{U_\alpha\}[/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, 1-way) ККА — 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, 2-way 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]L = \{a^mb^m\}[/math] за линейное время.

Принципы многомерного ККА очень схож с Одномерным, за исключением применение матрицы [math]P[/math] после каждого итерации символа строки. Для формального определения понадобиться гильбертово пространство. Пусть у нас есть гильбертово пространство [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]

Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в [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] — входящая строчка

См. также

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

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

• Andris Ambainis, QUANTUM FINITE AUTOMATA
• Wikipedia — Quantum finite automata