Квантовый конечный автомат — различия между версиями
(Новая страница: «Квантовые вычисления сочетает в себе квантовую механику с информатикой. Определяя кван...») |
(→Описание) |
||
| Строка 15: | Строка 15: | ||
== Описание== | == Описание== | ||
| − | Для начало воспользуемся графовым представлением [[Детерминированные конечные автоматы|Детерминированного конечного автомата (ДКА)]]. Пусть в нем <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>1</tex> означает переход из состояние <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> - его отсутствие. В этом случаи, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенный ''умножением матриц''. |
Версия 23:54, 6 января 2015
Квантовые вычисления сочетает в себе квантовую механику с информатикой. Определяя квантово-механические аналоги обычных моделей вычислений (например : машины Тьюринга или конечный автомат), получаем модели, как правило, более мощные, чем обычные (или классических) модели, потому что квантовая механика позволяет реализовать более широкий спектр операций. Кроме того, квантовые алгоритмы могут быть экспоненциально быстрее, чем любой классического алгоритма.
Содержание
Определение
| Определение: |
| Квантовый конечный автомат (ККА) (англ. Quantum finite automata, QFA) — квантовый аналог конечного автомата. |
Объединение квантовой механики с конечным автоматом и является Квантовым конечным автоматом. Кроме того, ККА является частным случаем Геометрического конечного автомата и Топологического конечного автомата.
Принцип работы
- На вход подается строчка .
- На выходе мы получаем число , являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
Описание
Для начало воспользуемся графовым представлением Детерминированного конечного автомата (ДКА). Пусть в нем вершин и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться Матрицей смежности для каждого символа , в котором означает переход из состояние в по символу , а - его отсутствие. В этом случаи, текущее состояние автомата записывается как вектор, размерности , в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу обыкновенный умножением матриц.
Одномерный квантовый конечный автомат
Авторы одномерного (англ. Measure-one, 1-way) ККА были Cris Moore и James P. Crutchfield в 2000.
Многомерный квантовый конечный автомат
Многомерный (или Двухмерный) (англ. Measure-many, 2-way) ККА был введен Attila Kondacs и John Watrous в 1997.
Источники информации
- Andris Ambainis, QUANTUM FINITE AUTOMATA
- Wikipedia — Quantum finite automata
