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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Многомерный квантовый конечный автомат)
(Многомерный квантовый конечный автомат)
(не показано 47 промежуточных версий 2 участников)
Строка 1: Строка 1:
Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Главной особенностью является допущение некоторого языка за экспоненциально меньший размер, чем обычные конечные автоматы.
+
<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.
  
 
== Определение ==
 
== Определение ==
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <math>(Q,\Sigma, V, q_0, Q_a, Q_r)</math>, где
+
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, V, q_0, Q_a, Q_r)</tex>, где
* <tex>Q</tex> — множество состояний автомата
+
* <tex>Q</tex> — множество состояний автомата,
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
+
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>V</tex> — функция перехода автомата
+
* <tex>V</tex> — функция перехода автомата,
* <tex>q_0</tex> ­— начальное состояние автомата
+
* <tex>q_0</tex> ­— начальное состояние автомата,
* <tex>Q_a \subset Q</tex> — множество допускающих состояний
+
* <tex>Q_a \subset Q</tex> — множество допускающих состояний,
* <tex>Q_r \subset Q</tex> — множество опровергающих состояний
+
* <tex>Q_r \subset Q</tex> — множество опровергающих состояний,
* <tex>Q_{non}  = Q \setminus (Q_a  \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний
+
* <tex>Q_{non}  = Q \setminus (Q_a  \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний.
 
}}
 
}}
  
Строка 21: Строка 21:
 
* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
 
* На выходе мы получаем число <tex> Pr(s)</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 \mid \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>[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>q</tex> записываются [[wikipedia:Probability amplitude|''амплитуды вероятностей'']], a матрицы <math>\{U_\alpha\}</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>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <math>\{U_\alpha\}</math> {{---}} операторы эволюции в представлении Шредингера <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> записываются амплитуды вероятностей<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  <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>. Если в этом случае рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА.
 
   
 
   
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы<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> для <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> состояниями представляется в виде [[Кубит | кубита]] <math>|\psi\rangle</math> c <tex>N</tex> состояниями.  
+
Автомат такого типа с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <tex>|\psi\rangle</tex> c <tex>N</tex> состояниями.  
:<math>|\psi\rangle \in CP^N</math>.  
+
:<tex>|\psi\rangle \in CP^N</tex>.  
  
Такой кубит  приносит в пространство метрику Фубини-Штуди<ref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <math>\Vert\cdot\Vert</math>.  
+
Такой кубит  приносит в пространство метрику Фубини-Штуди<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 = U_\alpha |\psi\rangle</math>.
+
:<tex>|\psi'\rangle = U_\alpha |\psi\rangle</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>.  
+
Переход в допускающее состояние производится матрицей-проектором<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>
  
 
===Многомерный квантовый конечный автомат===
 
===Многомерный квантовый конечный автомат===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Многомерный (или Двухмерный)  квантовый конечный автомат''' (англ. ''Measure-many'', ''2-way'' ''QFA'') {{---}} это кортеж : <math>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
+
'''Многомерный квантовый конечный автомат''' (англ. ''Measure-many QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
+
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_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} </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>\mathcal{H}_a</tex>,
* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>
+
* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>.
  
 
}}
 
}}
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство {{---}} допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время.
+
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {{---}} допускать регулярные языкы.
 +
 
 +
Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> :
  
Принципы многомерного ККА очень схож с Одномерным, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</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>\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> соответственно :
+
:<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>  
  
:<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> {{---}} линейная оболочка<ref>[https://en.wikipedia.org/wiki/Linear_span {{---}} Lineal span]</ref>  
+
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <tex>P_a</tex>, <tex>P_r</tex> и <tex> P_{non} </tex> для каждого гильбертово пр-ва :
  
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :
+
:<tex>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</tex>
  
:<math>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</math>
+
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в  <tex>\mathcal{H}_a, \mathcal{H}_r  , \mathcal{H}_{non}</tex>. В таком случае вероятность автомата находиться в допускающем состоянии равна:
  
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в  <math>\mathcal{H}_a, \mathcal{H}_r  , \mathcal{H}_{non}</math>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно :
+
:<tex>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</tex>, где <tex>s</tex> {{---}} входная строчка
 +
 
 +
==Двухсторонние квантовые конечные автоматы==
 +
{{Определение
 +
|definition=
 +
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где
 +
* <tex>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>Q_r \subset Q</tex> — множество опровергающих состояний.
 +
}}
  
:<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{---}} входящая строчка
+
Отличия от одностороннего :
 +
* Головка может двигаться в обоих направлениях.
 +
* Может гарантированно разрешать регулярный язык.
 +
* Может за линейное время разрешать нерегулярный язык.
  
 
==См. также==
 
==См. также==
Строка 91: Строка 112:
 
* 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)]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 16:05, 12 января 2015

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

Определение

Определение:
Квантовый конечный автомат (ККА) (англ. 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] — множество опровергающих состояний.


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

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

См. также

Примечания

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