Квантовые конечные автоматы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 95 промежуточных версий 5 участников)
Строка 1: Строка 1:
Квантовые вычисления сочетает в себе квантовую механику с информатикой. Определяя квантово-механические аналоги обычных моделей вычислений (например : машины Тьюринга или конечный автомат), получаем модели, как правило, более мощные, чем обычные (или классических) модели, потому что квантовая механика позволяет реализовать более широкий спектр операций. Кроме того, квантовые алгоритмы могут быть экспоненциально быстрее, чем любой классического алгоритма.
+
Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.
  
 
== Определение ==
 
== Определение ==
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') — квантовый аналог конечного автомата.
+
'''Квантовый конечный автомат (ККА)''' (англ. ''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>.  
  
 
===Принцип работы===  
 
===Принцип работы===  
Строка 13: Строка 21:
 
* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
 
* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
  
== Описание==
+
==Типы ККА==
 +
* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА {{---}} допускать большинство регулярных языков. Также односторонние ККА делятся на Одномерные ККА и Многомерные ККА.
 +
* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допускать нерегулярные языкы.
 +
 
 +
== Описание ==
  
Для начало воспользуемся графовым представлением [[Детерминированные конечные автоматы|ДКА]]. Пусть в нем <tex>N</tex> вершин и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться [[Матрица смежности графа|Матрицей смежности]] <tex>[N \times N]</tex> для каждого символа <tex> c \in \Sigma</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> вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <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> вершинами и его <math>\Sigma=\{c_1, c_2, c_3, \dots\}</math>.  Тогда по описанному определению можно составить матрицы смежности <math>\{U_\alpha | \alpha \in \Sigma \}</math> размерности <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> нужно воспользоваться правилом умножения матриц из линейной алгебры : <math>q = \cdots  U_{\alpha_1} U_{\alpha_0} q_0.</math>
+
Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <tex>\Sigma=\{c_1, c_2, c_3, \dots\}</tex>.  Тогда по описанному определению можно составить матрицы смежности <tex>\{U_\alpha \mid \alpha \in \Sigma \}</tex> размерности <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> нужно воспользоваться правилом умножения матриц из линейной алгебры : <tex>q = \cdots  U_{\alpha_1} U_{\alpha_0} q_0.</tex>
  
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются [[wikipedia:Probability amplitude|'''амплитуды вероятностей''']], a матрицы <math>\{U_\alpha\}</math> - [https://ru.wikipedia.org/wiki/Унитарная_матрица '''унитарные матрицы'''].  
+
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются амплитуды вероятностей<ref>[https://en.wikipedia.org/wiki/Probability_amplitude Wikipedia {{---}} Probability amplitude]</ref> такие, что <tex>|q|^2 = 1</tex> , a матрицы <tex>\{U_\alpha\}</tex> {{---}} [[Унитарный и ортогональный операторы| унитарные матрицы]], причем такие матрицы могут не только состоять из <tex>0</tex> и <tex>1</tex>, но и состоять из комплексных чисел.  
Для ККА характерено геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a  <math>\{U_\alpha\}</math> - [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 операторы эволюции в представлении Шредингера].
+
Для ККА характерна геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a  <tex>\{U_\alpha\}</tex> {{---}} операторы эволюции в представлении Шредингера <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> и в столбцах матриц <math>\{U_\alpha\}</math> может находиться несколько <tex>1</tex>. Если в этом случаи рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одно научно-исследовательских задач в теории ККА.
+
* НКА. Из-за свойства НКА в векторе <tex>q</tex> и в столбцах матриц <tex>\{U_\alpha\}</tex> может находиться несколько <tex>1</tex>. Если в этом случае рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА.
 
   
 
   
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать [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 стохастические матрицы] для <math>\{U_\alpha\}</math> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> - сумма всех элементов равна <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> для <tex>\{U_\alpha\}</tex> и вектор вероятностей состояний для <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'', ''1-way'') ККА - Cris Moore и James P. Crutchfield (2000). Главное свойство - допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
+
Авторы '''одномерного''' (англ. ''Measure-one'') ККА {{---}} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 кубита] <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.  
+
Автомат такого типа с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <tex>|\psi\rangle</tex> 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> <tex>\Vert\cdot\Vert</tex>.  
 
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
 
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
:<math>|\psi'\rangle</math> = <math>U_\alpha |\psi\rangle</math>.
+
:<tex>|\psi'\rangle = U_\alpha |\psi\rangle</tex>.
Переход в допускающее состояние производиться [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) матрицей-проектором] <tex> P [N \times N]</tex>.  
+
Переход в допускающее состояние производится матрицей-проектором<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> равна :  
 
Вероятность <tex>Pr(s)</tex>, где <tex>s = (a_0,a_1,\cdots,a_k) </tex> равна :  
  
:<math>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </math>
+
:<tex>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </tex>
  
 
===Многомерный квантовый конечный автомат===
 
===Многомерный квантовый конечный автомат===
Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
+
{{Определение
 +
|definition=
 +
'''Многомерный квантовый конечный автомат''' (англ. ''Measure-many QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где
 +
* <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>.
  
<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> - промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
+
}}
 +
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {{---}} допускать регулярные языкы.
  
:<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> - [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 линейная оболочка] 
+
Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> :
  
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :
+
<tex>\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> {{---}} отвергающее пр-во , <tex> \mathcal{H}_{non} </tex> {{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :  
  
:<math>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</math>
+
:<tex>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots </tex> , где <tex>\operatorname{span}</tex> {{---}} линейная оболочка<ref>[https://en.wikipedia.org/wiki/Linear_span Wikipedia {{---}} Lineal span]</ref>  
  
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в  <math>\mathcal{H}_a, \mathcal{H}_r  , \mathcal{H}_{non}</math>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно :  
+
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <tex>P_a</tex>, <tex>P_r</tex> и <tex> P_{non} </tex> для каждого гильбертово пр-ва :
  
:<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> - входящая строчка
+
:<tex>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</tex>
  
 +
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в  <tex>\mathcal{H}_a, \mathcal{H}_r  , \mathcal{H}_{non}</tex>. В таком случае вероятность автомата находиться в допускающем состоянии равна:
 +
 +
:<tex>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</tex>, где <tex>s</tex> {{---}} входная строчка
 +
 +
==Двухсторонние квантовые конечные автоматы==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Многомерный квантовый конечный автомат''' - это кортеж : <math>(Q;\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
+
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
+
* <tex>Q</tex> — множество состояний автомата,
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
+
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </tex> —всюду определённая функция перехода автомата
+
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\}</tex> — всюду определённая функция перехода автомата,
* <tex>q_0</tex> ­— начальное состояние автомата
+
* <tex>q_0</tex> ­— начальное состояние автомата,
* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>
+
* <tex>Q_a \subset Q</tex> — множество допускающих состояний,
* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>
+
* <tex>Q_r \subset Q</tex> — множество опровергающих состояний.
 +
}}
 +
 
 +
Отличия от одностороннего :
 +
* Головка может двигаться в обоих направлениях.
 +
* Может гарантированно разрешать регулярный язык.
 +
* Может за линейное время разрешать нерегулярный язык.
 +
 
 +
==См. также==
 +
*[[Детерминированные конечные автоматы]]
 +
*[[Недетерминированные конечные автоматы]]
 +
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
  
}}
+
== Примечания ==
 +
<references/>
  
 
==Источники информации==
 
==Источники информации==
 
* Andris Ambainis, [http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QUANTUM FINITE AUTOMATA]
 
* Andris Ambainis, [http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QUANTUM FINITE AUTOMATA]
 
* [[wikipedia:Quantum finite automata | Wikipedia {{---}} Quantum finite automata]]
 
* [[wikipedia:Quantum finite automata | Wikipedia {{---}} Quantum finite automata]]
 +
* SlideShare.net, [http://www.slideshare.net/ranjanphu/seminar-on-quantum-automata-complete Seminar on quantum automata (complete)]
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:07, 4 сентября 2022

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

Определение

Определение:
Квантовый конечный автомат (ККА) (англ. 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 \setminus (Q_a \bigcup 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 \mid \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] записываются амплитуды вероятностей[2] такие, что [math]|q|^2 = 1[/math] , a матрицы [math]\{U_\alpha\}[/math] унитарные матрицы, причем такие матрицы могут не только состоять из [math]0[/math] и [math]1[/math], но и состоять из комплексных чисел. Для ККА характерна геометрическая интерпретация в пространстве [math]CP^N[/math]. С этой стороны вектор [math]q[/math] является точкой, a [math]\{U_\alpha\}[/math] — операторы эволюции в представлении Шредингера [3].

Кроме того, можно упомянуть несколько особенностей ККА:

  • НКА. Из-за свойства НКА в векторе [math]q[/math] и в столбцах матриц [math]\{U_\alpha\}[/math] может находиться несколько [math]1[/math]. Если в этом случае рассмотреть алгоритм Томпсона, то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА.
  • Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы[4] для [math]\{U_\alpha\}[/math] и вектор вероятностей состояний для [math]q[/math]. Одно из свойств [math]q[/math] — сумма всех элементов равна [math]1[/math], и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.
  • Марковская цепь. При вводе строчек [math]s^n[/math] при больших [math]n[/math] одномерный ККА может быть эквивалентен марковской цепи[5].

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

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

Авторы одномерного (англ. Measure-one) ККА — Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА — допускать регулярный язык. Автомат такого типа с [math]N[/math] состояниями представляется в виде кубита [math]|\psi\rangle[/math] c [math]N[/math] состояниями.

[math]|\psi\rangle \in CP^N[/math].

Такой кубит приносит в пространство метрику Фубини-Штуди[6] [math]\Vert\cdot\Vert[/math]. Матрицы смежности остаются унитарными, а переход в новое сосояние по символу [math]\alpha[/math] :

[math]|\psi'\rangle = U_\alpha |\psi\rangle[/math].

Переход в допускающее состояние производится матрицей-проектором[7] [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]

Многомерный квантовый конечный автомат

Определение:
Многомерный квантовый конечный автомат (англ. Measure-many QFA) — это кортеж : [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].

Многомерный ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство — допускать регулярные языкы.

Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится гильбертово пространство. Пусть у нас есть гильбертово пространство [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] — линейная оболочка[8]

Так же в многомерном ККА присутствуют 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]

Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в [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] — входная строчка

Двухсторонние квантовые конечные автоматы

Определение:
Двухсторонний квантовый конечный автомат (англ. 2-way QFA) — это кортеж : [math](Q,\Sigma, \delta, q_0, Q_a, Q_r)[/math], где
  • [math]Q[/math] — множество состояний автомата,
  • [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова,
  • [math]\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\}[/math] — всюду определённая функция перехода автомата,
  • [math]q_0[/math] ­— начальное состояние автомата,
  • [math]Q_a \subset Q[/math] — множество допускающих состояний,
  • [math]Q_r \subset Q[/math] — множество опровергающих состояний.


Отличия от одностороннего :

  • Головка может двигаться в обоих направлениях.
  • Может гарантированно разрешать регулярный язык.
  • Может за линейное время разрешать нерегулярный язык.

См. также

Примечания

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