Изменения

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

'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <mathtex>(Q,\Sigma, V, q_0, Q_a, Q_r)</mathtex>, где* <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>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> , и для того , чтобы во всех переходах сохранялось это свойство , и нужны стохастические матрицы.

Авторы '''одномерного ''' (англ. ''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> и .  Такой кубит приносит в это пространство метрику Фубини-Штуди<ref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <mathtex>\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>

'''Многомерный квантовый конечный автомат''' (англ. ''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> — алфавит, из букв которого могут состоять входные слова,* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </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>.

Многомерный (или Двухмерный) (англ. ''Measure-many'', 'Многомерный'2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное Его главное свойство {{-- -}} допускать нерегулярный язык регулярные языкы. Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> : <tex>L \mathcal{H}_Q= \mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</tex> , где <tex> \mathcal{H}_a </tex> {{---}} допускающее пр-во , <tex> \mathcal{H}_r </tex> {{a^mb^m---}} отвергающее пр-во , <tex> \mathcal{H}_{non}</tex> за линейное время{{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :

Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы :<tex>P\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots </tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство , где <mathtex>\mathcaloperatorname{Hspan}_Q</mathtex> {{---}} линейная оболочка<ref> [https://en.wikipedia.org/wiki/Linear_span Wikipedia {{---}} Lineal span]</ref>

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

:<mathtex>P_a:\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q_Q \rangle \in Q_a \}, to \mathcal{H}_r _a , P_r = \dots , \mathcal{H}_P_{non} = \dots </mathtex> , где <math>\operatorname{span}</math> {{---}} [[wikipedia:Linear span | линейная оболочка]]

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

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

Переход в новое состояние кубита остается таким же==Двухсторонние квантовые конечные автоматы=={{Определение|definition='''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где* <tex>Q</tex> — множество состояний автомата,* <tex>\Sigma</tex> — алфавит, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в букв которого могут состоять входные слова,* <mathtex>\mathcaldelta : Q\times \Sigma \times Q \to \mathbb{HC}_a\times \{-1, 0,1\mathcal{H}_r </tex> — всюду определённая функция перехода автомата,* <tex>q_0</tex> ­— начальное состояние автомата, * <tex>Q_a \mathcal{H}_{non}subset Q</tex> — множество допускающих состояний,* <tex>Q_r \subset Q</mathtex>— множество опровергающих состояний. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно : }}

Отличия от одностороннего :<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{---}} входящая строчка* Головка может двигаться в обоих направлениях.* Может гарантированно разрешать регулярный язык.* Может за линейное время разрешать нерегулярный язык.