Квантовые конечные автоматы — различия между версиями
Alex Z (обсуждение | вклад) (→Описание) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 74 промежуточные версии 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>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> вершинами и его <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> записываются [ | + | Описанное выше по сути и является ККА, но в <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> и в столбцах матриц <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 | + | * Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы<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 | + | Авторы '''одномерного''' (англ. ''Measure-one'') ККА {{---}} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]]. |
− | + | Автомат такого типа с <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> : | ||
− | :< | + | :<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>. |
Вероятность <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> равна : | ||
− | :< | + | :<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 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>\mathcal{H}_Q</tex> : | ||
+ | |||
+ | <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> соответственно : | ||
− | + | :<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 матрицы-проектора : <tex>P_a</tex>, <tex>P_r</tex> и <tex> P_{non} </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= | ||
+ | '''Двухсторонний квантовый конечный автомат''' (англ. ''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> — множество опровергающих состояний. | ||
+ | }} | ||
− | : | + | Отличия от одностороннего : |
+ | * Головка может двигаться в обоих направлениях. | ||
+ | * Может гарантированно разрешать регулярный язык. | ||
+ | * Может за линейное время разрешать нерегулярный язык. | ||
==См. также== | ==См. также== | ||
Строка 78: | Строка 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)] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Автоматы и регулярные языки]] | [[Категория: Автоматы и регулярные языки]] |
Текущая версия на 19:07, 4 сентября 2022
Неформально говоря квантовый конечный автомат — это квантовый аналог конечного автомата, который использует квантовые гейты. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.
Определение
Определение: |
Квантовый конечный автомат (ККА) (англ. Quantum finite automata, QFA) — это кортеж :
| , где
Кроме того, ККА является частным случаем Геометрического конечного автомата и Топологического конечного автомата[1].
Принцип работы
- На вход подается строчка .
- На выходе мы получаем число , являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
Типы ККА
- Первый тип — односторонние ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА — допускать большинство регулярных языков. Также односторонние ККА делятся на Одномерные ККА и Многомерные ККА.
- Второй тип — двухсторонние ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство — допускать нерегулярные языкы.
Описание
Для первоначального описание ККА воспользуемся следующим примером. Пусть у нас есть графовое представление ДКА и пусть в нем вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором матриц смежности таких, что каждая матрица размера и что каждому символу сопоставляется единственная матрица из этого набора. Каждая матрица состоит из и , причём означает переход из состояния в по символу , а — его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности , в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу обыкновенным умножением матриц.
Пусть у нас есть ДКА с
вершинами и его . Тогда по описанному определению можно составить матрицы смежности размерности . Также введем -размерный вектор , описывающий состояние ДКА, a — начальное состояние автомата. Тогда для перехода из состояния в по строчке нужно воспользоваться правилом умножения матриц из линейной алгебры :Описанное выше по сути и является ККА, но в [2] такие, что , a матрицы — унитарные матрицы, причем такие матрицы могут не только состоять из и , но и состоять из комплексных чисел. Для ККА характерна геометрическая интерпретация в пространстве . С этой стороны вектор является точкой, a — операторы эволюции в представлении Шредингера [3].
записываются амплитуды вероятностейКроме того, можно упомянуть несколько особенностей ККА:
- НКА. Из-за свойства НКА в векторе алгоритм Томпсона, то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА. и в столбцах матриц может находиться несколько . Если в этом случае рассмотреть
- Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы[4] для и вектор вероятностей состояний для . Одно из свойств — сумма всех элементов равна , и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.
- Марковская цепь. При вводе строчек марковской цепи[5]. при больших одномерный ККА может быть эквивалентен
Односторонние квантовые кончные автоматы
Одномерный квантовый конечный автомат
Авторы одномерного (англ. Measure-one) ККА — Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА — допускать регулярный язык. Автомат такого типа с состояниями представляется в виде кубита c состояниями.
- .
Такой кубит приносит в пространство метрику Фубини-Штуди[6] . Матрицы смежности остаются унитарными, а переход в новое сосояние по символу :
- .
Переход в допускающее состояние производится матрицей-проектором[7] .
Вероятность
, где равна :Многомерный квантовый конечный автомат
Определение: |
Многомерный квантовый конечный автомат (англ. Measure-many QFA) — это кортеж :
| , где
Многомерный ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство — допускать регулярные языкы.
Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится гильбертово пространство. Пусть у нас есть гильбертово пространство :
, где — допускающее пр-во , — отвергающее пр-во , — промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов соответственно :
- [8] , где — линейная оболочка
Так же в многомерном ККА присутствуют 3 матрицы-проектора :
, и для каждого гильбертово пр-ва :Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в
. В таком случае вероятность автомата находиться в допускающем состоянии равна:- , где — входная строчка
Двухсторонние квантовые конечные автоматы
Определение: |
Двухсторонний квантовый конечный автомат (англ. 2-way QFA) — это кортеж :
| , где
Отличия от одностороннего :
- Головка может двигаться в обоих направлениях.
- Может гарантированно разрешать регулярный язык.
- Может за линейное время разрешать нерегулярный язык.
См. также
Примечания
Источники информации
- Andris Ambainis, QUANTUM FINITE AUTOMATA
- Wikipedia — Quantum finite automata
- SlideShare.net, Seminar on quantum automata (complete)