Изменения

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

'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, V, q_0, Q_a, Q_r)</tex>, где* <tex>Q</tex> — квантовый аналог конечного множество состояний автомата,* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,* <tex>V</tex> — функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата,* <tex>Q_a \subset Q</tex> — множество допускающих состояний,* <tex>Q_r \subset Q</tex> — множество опровергающих состояний,* <tex>Q_{non} = Q \setminus (Q_a \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний.

Объединение квантовой механики с конечным автоматом и является Квантовым конечным автоматом. Кроме того, ККА является частным случаем ''Геометрического конечного автомата'' и ''Топологического конечного автомата''<ref>[https://en.wikipedia.org/wiki/Quantum_finite_automata#Geometric_generalizations Wikipedia {{---}} Geometric generalizations]</ref>.

* На вход подается строчка <tex> s = \langle a_0, a_1,.. \dots ,a_k \rangle, a_i \in \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> {{- --}} [[https://ru.wikipedia.org/wiki/Унитарная_матрица '''Унитарный и ортогональный операторы| унитарные матрицы''']], причем такие матрицы могут не только состоять из <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> , и для того , чтобы во всех переходах сохранялось это свойство , и нужны стохастические матрицы.

Авторы '''одномерного ''' (англ. ''Measure-one'', ''1-way'') ККА {{--- }} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{-- -}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].В таком виде конечный автомат Автомат такого типа с <tex>N</tex> состояниями представляется в виде [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 [Кубит | кубита]] <mathtex>|\psi\rangle</mathtex> c <tex>N-</tex> состояниями. Такой кубит :<tex>|\psi\rangle \in CP^N</tex> и .  Такой кубит приносит в это пространство метрику Фубини-Штуди<mathref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <tex>\Vert\cdot\Vert</mathtex>.

:<mathtex>|\psi'\rangle</math> = <math>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>.

:<mathtex>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </mathtex>

{{Определение|definition='''Многомерный (или Двухмерный) квантовый конечный автомат''' (англ. ''Measure-manyQFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, ''2-way''Q_r) ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство </tex>, где* <tex>Q</tex> — базисные ортогональные вектора пр- допускать нерегулярный язык ва <tex>\mathcal{H}_Q</tex>,* <tex>\Sigma</tex>L = — алфавит, из букв которого могут состоять входные слова,* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{a^mb^mC} </tex> — всюду определённая функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата,* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы * <tex>PQ_r \subset Q</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство — базисные ортогональные вектора пр-ва <mathtex>\mathcal{H}_Q_r</mathtex> :.

<math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {H}_{non}</math> , где <math> \mathcal{H}_a </math>- допускающее пр-во , <math> \mathcal{H}_r </math> - отвергающее пр-во , <math> \mathcal{H}_{non} </math> - промежуточное пр-водопускать регулярные языкы. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :

:<math>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}Принципы многомерного ККА очень схожи с одномерными, \mathcal{H}_r = ... за исключением измерения вероятности после каждого прочтения символа входящей строки, \mathcal{H}_{non} = вместо единственного измерения вероятности целой строчки у одномерных ККА.Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]].. </math> , где Пусть у нас есть гильбертово пространство <mathtex>\operatornamemathcal{spanH}_Q</mathtex> - [https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D0.B0.D1.8F_.D0.BE.D0.B1.D0.BE.D0.BB.D0.BE.D1.87.D0.BA.D0.B0 линейная оболочка]

Так же в многомерном ККА присутствуют 3 матрицы-проектора : <mathtex>P_a\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</mathtex>, где <mathtex>P_r\mathcal{H}_a </mathtex> {{---}} допускающее пр-во , <tex> и \mathcal{H}_r <math/tex> P_{{---}} отвергающее пр-во , <tex> \mathcal{H}_{non} </mathtex> для {{---}} промежуточное пр-во. Для каждого гильбертово пр-ва существует набор базисных ортогональных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :

:<mathtex>P_a:\mathcal{H}_Q _a=\operatorname{span} \{|q\rangle : |q\to rangle \in Q_a \}, \mathcal{H}_a , P_r _r = ...\dots , P_\mathcal{H}_{non} = \dots </tex> , где <tex>\operatorname{span}</tex> {{---}} линейная оболочка<ref>[https://en.wikipedia..org/wiki/Linear_span Wikipedia {{---}} Lineal span]</mathref>

Переход в новое состояние кубита остается таким Так же, но после каждого перехода кубит коллпасирует в одно из многомерном ККА присутствуют 3 гильбертовых прматрицы-в проектора : <mathtex>P_a</tex>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_<tex>P_r</tex> и <tex> P_{non}</mathtex>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно для каждого гильбертово пр-ва :

:<mathtex>P_a:\mathcal{H}_Q \operatornameto \mathcal{PrH}_a (s) , P_r = \Vert P_a |dots, P_{non} = \psi\rangle \Vert^2</math>, где <tex>sdots</tex> - входящая строчка

'''Многомерный Двухсторонний квантовый конечный автомат''' (англ. ''2- way QFA'') {{---}} это кортеж : <mathtex>(Q;,\Sigma, \delta, q_0, Q_a, Q_r)</mathtex>, где* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>множество состояний автомата,* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\} </tex> —всюду — всюду определённая функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата,* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>множество допускающих состояний,* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{Hмножество опровергающих состояний.}}_r</tex> Отличия от одностороннего :* Головка может двигаться в обоих направлениях.* Может гарантированно разрешать регулярный язык.* Может за линейное время разрешать нерегулярный язык. ==См. также==*[[Детерминированные конечные автоматы]]*[[Недетерминированные конечные автоматы]]*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]