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

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

Определение

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

Квантовый конечный автомат (ККА) (англ. 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] обыкновенный умножением матриц.

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

Авторы одномерного (англ. 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