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

Квантовые вычисления сочетает в себе квантовую механику с информатикой. Определяя квантово-механические аналоги обычных моделей вычислений (например : машины Тьюринга или конечный автомат), получаем модели, как правило, более мощные, чем обычные (или классических) модели, потому что квантовая механика позволяет реализовать более широкий спектр операций. Кроме того, квантовые алгоритмы могут быть экспоненциально быстрее, чем любой классического алгоритма.

Определение

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

Квантовый конечный автомат (ККА) (англ. Quantum finite automata, QFA) — квантовый аналог конечного автомата.

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

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

• На вход подается строчка [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]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 | \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] и для того чтобы во всех переходах сохранялось это свойство и нужны стохастические матрицы.

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

Авторы одномерного (англ. Measure-one, 1-way) ККА - Cris Moore и James P. Crutchfield (2000). Главное свойство — допускать регулярный язык. В таком виде конечный автомат с [math]N[/math] состояниями представляется в виде кубита [math]|\psi\rangle[/math] c N-состояниями. Такой кубит [math]\in CP^N[/math] и приносит в это пространство метрику [math]\Vert\cdot\Vert[/math]. Матрицы смежности остаются унитарными, а переход в новое сосояние по символу [math]\alpha[/math] :

[math]|\psi'\rangle[/math] = [math]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]

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

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

Многомерный квантовый конечный автомат — это кортеж : [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]

Многомерный (или Двухмерный) (англ. Measure-many, 2-way) ККА был введен 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