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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Определение

Определение:
Квантовый конечный автомат (ККА) (англ. 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-(Q_a + Q_r), Q_{non} \subset Q [/math] — множество промежуточных состояний


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

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

  • На вход подается строчка [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 | \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] — операторы эволюции в представлении Шредингера [2].

В дополнении для ККА можно упомянуть пару особенностей :

  • НКА. Из-за свойство НКА в векторе [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] — входящая строчка

См. также

Примечания

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