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

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

Определение

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

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

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

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

• На вход подается строчка [math] s = \langle a_0, a_1,.. ,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, ..\}[/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,.. \rangle[/math] нужно воспользоваться правилом умножения матриц из линейной алгебры : [math]q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.[/math]

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

Авторы одномерного (англ. Measure-one, 1-way) ККА - Cris Moore и James P. Crutchfield (2000).

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

Многомерный (или Двухмерный) (англ. Measure-many, 2-way) ККА был введен Attila Kondacs и John Watrous в 1997.

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

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