69
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, V, q_0, Q_a, Q_r)</mathtex>, где
* <tex>Q</tex> — множество состояний автомата
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
Для первоначального описание ККА воспользуемся следующим примером. Пусть есть графовым представлением [[Детерминированные конечные автоматы|ДКА]] и пусть в нем <tex>N</tex> вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <tex>[N \times N]</tex> и что каждому символу <tex>c \in \Sigma</tex> сопоставляется единственная матрица из этого набора. Каждая матрица состоит из <tex>0</tex> и <tex>1</tex>, причём <tex>1</tex> означает переход из состояния <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> {{---}} его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенным ''умножением матриц''.
Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <mathtex>\Sigma=\{c_1, c_2, c_3, \dots\}</mathtex>. Тогда по описанному определению можно составить матрицы смежности <mathtex>\{U_\alpha \mid \alpha \in \Sigma \}</mathtex> размерности <tex>[N \times N]</tex>. Также введем <tex>N</tex>-размерный вектор <tex>q \in Q</tex>, описывающий состояние ДКА, a <tex>q_0</tex> {{---}} начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <mathtex>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</mathtex>
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются амплитуды вероятностей<ref>[https://en.wikipedia.org/wiki/Probability_amplitude Wikipedia {{---}} Probability amplitude]</ref> такие, что <tex>|q|^2 = 1</tex> , a матрицы <mathtex>\{U_\alpha\}</mathtex> {{---}} [[Унитарный и ортогональный операторы| унитарные матрицы]], причем такие матрицы могут не только состоять из <tex>0</tex> и <tex>1</tex>, но и состоять из комплексных чисел. Для ККА характерна геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <mathtex>\{U_\alpha\}</mathtex> {{---}} операторы эволюции в представлении Шредингера <ref>[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A8%D1%80%D1%91%D0%B4%D0%B8%D0%BD%D0%B3%D0%B5%D1%80%D0%B0 Википедия {{---}} Представление Шрёдингера]</ref>.
Кроме того, можно упомянуть несколько особенностей ККА:
* НКА. Из-за свойства НКА в векторе <tex>q</tex> и в столбцах матриц <mathtex>\{U_\alpha\}</mathtex> может находиться несколько <tex>1</tex>. Если в этом случаи рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА.
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 Википедия {{---}} Стохастическая матрица]</ref> для <mathtex>\{U_\alpha\}</mathtex> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> {{---}} сумма всех элементов равна <tex>1</tex>, и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.
* Марковская цепь. При вводе строчек <tex>s^n</tex> при больших <tex>n</tex> одномерный ККА может быть эквивалентен [[Марковская цепь | марковской цепи]]<ref>[http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QFAs and quantum Markov chains]</ref>.
=== Одномерный квантовый конечный автомат===
Авторы '''одномерного''' (англ. ''Measure-one'') ККА {{---}} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
Автомат такого типа с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <mathtex>|\psi\rangle</mathtex> c <tex>N</tex> состояниями. :<mathtex>|\psi\rangle \in CP^N</mathtex>.
Такой кубит приносит в пространство метрику Фубини-Штуди<ref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <mathtex>\Vert\cdot\Vert</mathtex>.
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
:<mathtex>|\psi'\rangle = U_\alpha |\psi\rangle</mathtex>.
Переход в допускающее состояние производится матрицей-проектором<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Википедия {{---}} Проектор]</ref> <tex> P [N \times N]</tex>.
Вероятность <tex>Pr(s)</tex>, где <tex>s = (a_0,a_1,\cdots,a_k) </tex> равна :
:<mathtex>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </mathtex>
===Многомерный квантовый конечный автомат===
{{Определение
|definition=
'''Многомерный квантовый конечный автомат''' (англ. ''Measure-many QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</mathtex>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство, а и одномерный {{---}} допускать регулярный язык.
Принципы многомерного ККА очень схожи с одномерным, за исключением измерения вероятности после каждой итерации символа строки вместо измерения после полного ввода строчки как у одномерного ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <mathtex>\mathcal{H}_Q</mathtex> :
<mathtex>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</mathtex> , где <mathtex> \mathcal{H}_a </mathtex> {{---}} допускающее пр-во , <mathtex> \mathcal{H}_r </mathtex> {{---}} отвергающее пр-во , <mathtex> \mathcal{H}_{non} </mathtex> {{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
:<mathtex>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots </mathtex> , где <mathtex>\operatorname{span}</mathtex> {{---}} линейная оболочка<ref>[https://en.wikipedia.org/wiki/Linear_span Wikipedia {{---}} Lineal span]</ref>
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <mathtex>P_a</mathtex>, <mathtex>P_r</mathtex> и <mathtex> P_{non} </mathtex> для каждого гильбертово пр-ва :
:<mathtex>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</mathtex>
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в <mathtex>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}</mathtex>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно :
:<mathtex>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</mathtex>, где <tex>s</tex> {{---}} входная строчка
==Двухсторонние квантовые конечные автоматы==
{{Определение
|definition=
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</mathtex>, где
* <tex>Q</tex> — множество состояний автомата
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
