Теория конечных квантовых автоматов (обзор)
В работе рассмотрено многообразие существующих моделей квантовых автоматов. Выделены модели, которые принято называть конечными квантовыми автоматами, также модели, которые таковыми не являются (так как они используют средства, не применяемые для классических конечно-автоматных моделей). Приведены о...
Saved in:
| Published in: | Труды Института прикладной математики и механики |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут прикладної математики і механіки НАН України
2012
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124130 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Теория конечных квантовых автоматов (обзор) / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 196-209. — Бібліогр.: 44 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860170814564859904 |
|---|---|
| author | Скобелев, В.Г. |
| author_facet | Скобелев, В.Г. |
| citation_txt | Теория конечных квантовых автоматов (обзор) / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 196-209. — Бібліогр.: 44 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики |
| description | В работе рассмотрено многообразие существующих моделей квантовых автоматов. Выделены модели, которые принято называть конечными квантовыми автоматами, также модели, которые таковыми не являются (так как они используют средства, не применяемые для классических конечно-автоматных моделей). Приведены основные результаты, связанные с анализом эквивалентности конечных квантовых автоматов.
У роботi розглянуто рiзноманiття iснуючих моделей квантових автоматiв. Видiлено моделi, якi прийнято називати скiнченними квантовими автоматами, а також моделi, що не є такими (оскiльки засоби, якi у них використано, не застосовуються для класичних скiнченно-автоматних моделей). Наведено основнi результати, пов’язанi з аналiзом еквiвалентностi скiнченних квантових автоматiв.
In the given paper it is considered variety of models for quantum automata. There are extracted models, which are called finite quantum automata, as well as the ones which are not models for finite quantum automata (since they explore these or the other tools which are not used for classical finite-automata models). Basic results connected with analysis of equivalency of finite quantum automata are listed.
|
| first_indexed | 2025-12-07T17:58:51Z |
| format | Article |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2012. Том 25
УДК 530.145+519.713
c©2012. В. Г. Скобелев
ТЕОРИЯ КОНЕЧНЫХ КВАНТОВЫХ АВТОМАТОВ (ОБЗОР)
В работе рассмотрено многообразие существующих моделей квантовых автоматов. Выделены мо-
дели, которые принято называть конечными квантовыми автоматами, также модели, которые тако-
выми не являются (так как они используют средства, не применяемые для классических конечно-
автоматных моделей). Приведены основные результаты, связанные с анализом эквивалентности
конечных квантовых автоматов.
Ключевые слова: модели квантовых автоматов, эквивалентность конечных квантовых авто-
матов.
1. Введение. На протяжении последних 30-и лет происходит интенсивное фор-
мирование теории квантовых алгоритмов. Эти исследования, во многом, базируют-
ся на достижениях классической теории алгоритмов, которая к 80-ым годам XX
столетия приняла вид стройной теории со сложившейся проблематикой. При этом
исследования в области квантовых алгоритмов, в свою очередь, стимулировали пере-
осмысление проблематики таких достаточно хорошо проработанных разделов клас-
сической теории алгоритмов, как теория автоматов. С другой стороны, квантовые
вычисления, вероятностные по своей сути, существенно используют математиче-
ский аппарат теории линейных операторов в конечномерном комплексном эрмито-
вом пространстве. Тем самым, устанавливается глубокая внутренняя связь между
квантовыми вычислениями и алгебраической теорией автоматов.
По-видимому, именно особенности анализа квантовых систем явились одной из
основных причин того, что, в отличие от классической теории автоматов, было по-
строено значительное число различных моделей квантовых автоматов, различаю-
щихся как по сложности, так и по их возможностям. Эти результаты содержатся в
различных, иногда труднодоступных, статьях. Поэтому в настоящей работе сделана
попытка охарактеризовать состояние, в котором на современном этапе находится
теория конечных квантовых автоматов.
С целью сделать изложение материала, по возможности, замкнутым в п.2 приве-
дены необходимые результаты теории детерминированных и вероятностных автома-
тов, а в п.3 – основные понятия теории квантовых вычислений. В п.4 рассмотрены
существующие модели квантовых автоматов. Выделены модели, которые принято
называть конечными квантовыми автоматами, также модели, которые таковыми
не являются (так как они используют средства, не применяемые для классических
конечно-автоматных моделей). В п.5 приведены основные результаты, связанные с
анализом эквивалентности конечных квантовых автоматов. Заключение содержит
ряд выводов.
2. Конечные автоматы. В середине XX века были заложены основы теории
конечных автоматов [1-5]. Эта теория была предназначена для исследования вы-
196
Квантовые автоматы
числений, осуществляемых в реальное время на конечной памяти. По своей сути
конечный автомат (в дальнейшем, для краткости, автомат) является формальной
моделью тех процессов, которые могут быть реализованы на компьютерах (из-за су-
ществующих ограничений на объем их памяти). При этом, автомат рассматривался
либо как преобразователь информации, либо как распознаватель языка.
В первом случае автомат имеет вид M = (Q, X, Y, δ, λ) (Q, X и Y – конечные мно-
жество состояний, входной и выходной алфавит, а δ : Q × X → Q и λ : Q × X → Y
– функции переходов и выходов). Были выделены две основные модели (Мили и
Мура), а также некоторые их разновидности, связанные с представлением функци-
онирования автомата во времени. Именно в рамках этих моделей и осуществлялось
исследование задач анализа и синтеза автоматов.
Замечание 1. Следует отметить, что в 60-70 годах XX века большое внимание было
уделено исследованию автоматов без потери информации [6, 7], т.е. автоматов, для которых
по выходному слову, а также по начальному и/или финальному состоянию однозначно
восстанавливается входное слово, поданное на автомат.
Во втором случае автомат называется настроенным автоматом и имеет вид M =
(Q, X, δ, qin, Qfin) (где Q и X – конечные множество состояний и входной алфавит,
δ : Q× X→ Q – функция переходов, qin ∈ Q – начальное состояние, Qfin ⊆ Q – множе-
ство финальных состояний). Язык, распознаваемый (говорят также, представлен-
ный) настроенным автоматом, определяется как множество слов, переводящих на-
чальное состояние во множество финальных состояний (говорят также, что настро-
енный автомат принимает входное слово, если оно переводит начальное состояние в
множество финальных состояний, и отвергает входное слово в противном случае).
Такие языки образуют множество регулярных языков, которое представляет собой
наименьший нетривиальный класс языков, имеющий многочисленные приложения.
Для каждого регулярного языка L ⊆ X∗ может быть эффективно построен при-
веденный настроенный автомат, распознающий этот язык, т.е. такой настроенный
автомат M = (Q, X, δ, qin, Qfin), что для любых состояний q, q′ ∈ Q (q 6= q′) множества
слов, переводящих состояние q во множество Qfin отличается от множества слов,
переводящих состояние q′ во множество Qfin.
Отметим, что настроенный автомат естественным образом интерпретируется в
терминах 1-направленной 1-головочной машины Тьюринга (МТ) с одной входной
лентой (т.е. информация только считывается). Напомним, что «1-направленноcть»
означает, что на каждом шаге работы МТ головка сдвигается на клетку вправо.
Всюду в дальнейшем предполагается, что входной алфавит X зафиксирован.
Обозначим через LDFA множество всех регулярных языков, распознаваемых на-
строенными автоматами.
Существенную роль в исследовании сложности распознавания регулярных язы-
ков сыграли следующие два момента.
Во-первых, это формирование модели источника, т.е. недетерминированного на-
строенного автомата M = (Q, X, δ, Qin, Qfin), где δ ⊆ Q × ({Λ} ∪ X) × Q – тернарное
отношение, определяющее допустимые переходы (Λ – пустое слово). Язык, распо-
знаваемый источником, определяется как множество слов, переводящих хотя бы од-
197
В.Г. Скобелев
но начальное состояние q ∈ Qin во множество Qfin финальных состояний. Множество
всех языков, представляемых источниками, совпадает с LDFA.
Замечание 2. Хотя для каждого источника может быть эффективно построен эк-
вивалентный ему (т.е. представляющий тот же язык) настроенный автомат, переход от
источника к настроенному автомату может вызвать существенный рост мощности множе-
ства состояний (известны примеры, когда источник имеет n состояний, а эквивалентный
ему приведенный настроенный автомат 2n состояний). По-видимому, это обстоятельство
и послужило основной причиной того, что именно алгебра источников [4], разработанная
Б.А. Трахтенбротом в 60-х годах XX века, в 90-х годах стала основой для формирования
одного из основных классов систем дискретных событий, предназначенных для автомати-
зации управления производственными процессами.
Во-вторых, это выделение настроенных групповых автоматов, т.е. таких автома-
тов M = (Q, X, δ, qin, Qfin), что для каждого x ∈ X отображение δx, определяемое ра-
венством δx(q) = δ(q, x) (q ∈ Q) – подстановка на множестве Q. Для множества LGFA
языков, представимых настроенными групповыми автоматами, истинно включение
LGFA ⊂ LDFA. Это обстоятельство послужило причиной исследования k-буквенных
(k ∈ N) групповых автоматов [8, 9], являющихся специальным случаем односторон-
них многоголовочных автоматов [10].
k-буквенный (k ∈ N) групповой автомат определяется как настроенный автомат
M = (Q, T, δ, qin, Qfin) (T = {Λ}k ∪
k−1⋃
i=1
{Λ}k−iXi ∪ Xk), где δ : T× Q→ Q – такая функция
переходов, что для каждого w ∈ T отображение δw, определяемое равенством δw(q) =
δ(q, w) (q ∈ Q) – подстановка на множестве Q.
Замечание 3. k-буквенный (k ∈ N) групповой автомат M = (Q, T, δ, qin, Qfin), как пра-
вило, следующим образом интерпретируется в терминах 1-направленной k-головочной МТ
M = (Q, X, δ, qin, Qfin) с одной входной лентой (здесь «1-направленноcть» означает, что на
каждом шаге работы МТ все головки синхронно сдвигаются на клетку вправо).
Пусть на входной ленте записано слово $Λ . . . Λ︸ ︷︷ ︸
k−1 раз
x1 . . . xl#, где $ и #, соответственно,
левый и правый концевые маркеры, а x1 . . . xl ∈ X∗ (l ∈ Z+). В начальный момент МТ M на-
ходится в состоянии q0 = qin, а ее головки обозревают первые k клеток. Функционирование
МТ M состоит из следующих l + 2 шагов:
1) на 1-м шаге головки МТ синхронно сдвигаются на клетку вправо;
2) на j-м шаге (j = 2, . . . , l + 1) (перед его выполнением МТ находится в состоянии
qj−2, а ее головки обозревают клетки, в которых записано слово wj−1 ∈ T) МТ переходит
в состояние qj−1 = δ(qj−2, wj−1), после чего ее головки синхронно сдвигаются на клетку
вправо;
3) на (l + 2)-ем шаге (перед его выполнением МТ находится в состоянии ql+1, а самая
правая из ее головок обозревает клетку, в которой записан правый концевой маркер) МТ
останавливается.
Язык, распознаваемый автоматом M = (Q, T, δ, qin, Qfin), определяется как множество
всех слов x1 . . . xl ∈ X∗ (l ∈ Z+), переводящих МТ M = (Q, X, δ, qin, Qfin) из начального состо-
яния qin в множество финальных состояний Qfin.
Обозначим через LGFAk
(k ∈ N) множество всех языков, распознаваемых k-
буквенными групповыми автоматами (таким образом, LGFA1 = LGFA), и положим
198
Квантовые автоматы
LGFA∗ =
∞⋃
k=1
LGFAk
. Известно, что LGFAk
⊂ LGFAk+1
(k ∈ N) и LGFA∗ ⊂ LDFA.
Нетривиальным обобщением рассмотренных выше автоматов является вероят-
ностный автомат [11-13]. Он характеризуется тем, что для каждого состояния и
каждого входного символа с заданными вероятностями осуществляется переход в
каждое состояние, а также с заданными вероятностями осуществляется выдача каж-
дого из выходных символов. Отметим, что существует глубокая внутренняя связь
между вероятностными автоматами и конечными цепями Маркова [14].
Вероятностный настроенный автомат имеет вид M = (Q, X, {Mx}x∈X, u0, Qfin), где
Q = {q1, . . . , qn} – множество состояний, X – конечный входной алфавит, Mx (x ∈ X)
– стохастические n×n-матрицы переходов, u0 = (α(0)
1 , . . . , α
(0)
n )T (α(0)
i ∈ R+ (i ∈ Nn),
n∑
i=1
α
(0)
i = 1) – начальное распределение состояний, а Qfin ⊆ Q – множество фи-
нальных состояний. Эволюция автомата M на входном слове x1 . . . xl (l ∈ Z+) опре-
деляется равенством ul = (α(l)
1 , . . . , α
(l)
n )T = Mxl
. . . Mx1u0. Говорят, что автомат M
принимает входное слово x1 . . . xl с вероятностью PM(x1 . . . xl) =
∑
α
(l)
i , где сумма бе-
рется по всем таким i, что qi ∈ Qfin. Так как для любого входного слова может быть
вычислена вероятность того, что оно переводит автомат во множество финальных
состояний, то говорят, что:
1) вероятностный настроенный автомат распознает язык L с вероятностью p
(0.5 ≤ p ≤ 1), если он принимает каждое слово w1 ∈ L с вероятностью, не мень-
шей, чем p, а каждое слово w2 6∈ L – с вероятностью, не превосходящей 1− p;
2) вероятностный настроенный автомат распознает язык L с ограниченной ошиб-
кой (p1; p2) (0 ≤ p1 < p2 ≤ 1), если он принимает каждое слово w1 ∈ L с вероятностью,
не меньшей, чем p2, а каждое слово w2 6∈ L – с вероятностью, не превосходящей p1 (в
дальнейшем, для краткости, в фразе «распознавание языка с ограниченной ошиб-
кой» будем опускать слово «ограниченной»).
Отметим, что вероятностный настроенный автомат естественным образом ин-
терпретируется в терминах вероятностной 1-направленной 1-головочной МТ с одной
входной лентой.
Известно, что множество языков, распознаваемых вероятностными настроенны-
ми автоматами, имеет мощность континуум. При этом, при распознавании регуляр-
ных языков переход от детерминированного настроенного автомата к вероятност-
ному настроенному автомату может дать субэкспоненциальный выигрыш в числе
состояний.
Замечание 4. В [15] показано, что существует последовательность таких попарно раз-
личных языков Ln ∈ LDFA (n ∈ N), что язык Ln распознается с заданной вероятностью p
вероятностным настроенным автоматом с n состояниями, а детерминированный настроен-
ный автомат, распознающий этот язык, имеет Ω(2
log n
log log n ) (n →∞) состояний.
Более сильные результаты получены в [16] для обратимых вероятностных настроенных
автоматов, т.е. у которых каждая матрица переходов – обратимая дважды стохастическая.
Показано, что в 2-буквенном входном алфавите существует последовательность таких по-
парно различных языков Ln ∈ LDFA (n ∈ N), что язык Ln распознается с вероятностью 68
135
199
В.Г. Скобелев
обратимым вероятностным настроенным автоматом с zi состояниями, а детерминирован-
ный настроенный автомат, распознающий этот язык, имеет (7
1
14 )zi состояний. Кроме того,
в [16] показано, что если истинна гипотеза Артина (для любого целого числа a, не являю-
щегося точным квадратом и отличного от −1, существует бесконечно много таких простых
чисел m, что a – первообразный корень по модулю m, причем для количества Na(x) таких
простых чисел, не превосходящих x, справедлива асимптотика Na(x) ∼ ca
x
ln x (x →∞), где
ca – константа, зависящая только от a), то эта оценка может быть усилена. А именно, в
этом случае в 2-буквенном входном алфавите существует последовательность таких попар-
но различных языков Ln ∈ LDFA (n ∈ N), что язык Ln распознается с вероятностью 19
36
обратимым вероятностным настроенным автоматом с zi состояниями, а детерминирован-
ный настроенный автомат, распознающий этот язык, имеет (2
1
4 )zi состояний.
3. Квантовые вычисления. Начиная с 80-х годов XX века стало формиро-
ваться принципиально новое направление теории алгоритмов – теория квантовых
алгоритмов [17, 18]. С позиции теории систем любой квантовый алгоритм являет-
ся композицией двух взаимодействующих систем: классической конечной дискрет-
ной системы и квантовой системы. Классическая дискретная система реализует ту
часть процесса вычисления, которая представлена моделями и методами классиче-
ской теории алгоритмов. Квантовая система существенно базируется на использо-
вании квантово-механических процессов, что дает возможность обеспечить экспо-
ненциальный рост размерности пространства вычислений при линейном росте раз-
мерности системы (т.е. используемого количества кубитов), а также возможность
одновременного изменения величин, характеризующих эту систему. Именно эти два
фактора и лежат в основе построения для широкого класса задач, актуальных как
с теоретической, так и прикладной точки зрения, квантовых алгоритмов, для ко-
торых временная и емкостная сложность существенно ниже, чем для классических
алгоритмов.
Замечание 5. Для определения квантовой системы нам понадобятся следующие по-
нятия теории линейных операторов в комплексном эрмитовом пространстве Cn (n ∈ N)
векторов-столбцов |ϕ〉 = (α1, . . . , αn)T , в котором зафиксирован ортонормированный базис
Bn = {|i〉|i ∈ Nn}, где |i〉 = (0, . . . , 0︸ ︷︷ ︸
i−1 раз
, 1, 0, . . . , 0︸ ︷︷ ︸
n−i раз
)T . Скалярное произведение векторов |ϕi〉 ∈ Cn
(i = 1, 2) определено равенством 〈ϕ1|ϕ2〉 = 〈ϕ1| · |ϕ2〉, где 〈ϕ1| = |ϕ1〉†, а † – операция эрми-
тового сопряжения, т.е. транспонирования и замены чисел их комплексно сопряженными.
Норма вектора |ϕ〉 определена равенством ‖|ϕ〉‖ =
√
〈ϕ|ϕ〉.
Предполагается, что линейные операторы представлены в матричном виде. Линейный
оператор A : Cn → Cn называется:
1) нормальным, если AA† = A†A;
2) эрмитовым (или самосопряженным), если A† = A;
3) унитарным, если A†A = I, где I – единичная матрица (в дальнейшем унитарные
операторы будем обозначать буквой U , возможно, с индексами);
4) проектором на подпространство W ⊆ Cn, если для любого вектора |ϕ〉 ∈ Cn истинно
равенство A|ϕ〉 = |ϕ1〉, где |ϕ〉 = |ϕ1〉 ⊕ |ϕ2〉 (⊕ – прямая сумма), а |ϕ1〉 ∈W и |ϕ2〉 ∈W⊥ (в
дальнейшем проекторы будем обозначать буквой P , возможно, с индексами).
Отметим, что:
1) для любого нормального оператора A существуют такие попарноразличные числа
200
Квантовые автоматы
ν1, . . . , νm и такие попарно ортогональные ненулевые проекторы P1, . . . , Pm, удовлетворяю-
щие условию
m∑
i=1
Pi = I, что A =
m∑
i=1
νiPi (такое представление называется спектральным
разложением оператора A);
2) нормальный оператор является эрмитовым тогда и только тогда, когда все его соб-
ственные значения действительны;
3) унитарные операторы сохраняют скалярное произведение, а, следовательно, и норму
векторов;
4) для любого проектора P истинно равенство P 2 = P .
Квантовая система S в пространстве Cn (n ∈ N) – это физическая система, состо-
яние которой представлено таким вектором |ξ〉 = (α1, . . . , αn)T ∈ Cn, что ‖|ξ〉‖ = 1.
Число αi (i ∈ Nn) называется (комплексной) амплитудой, соответствующей базис-
ному вектору |i〉.
Исходя из положений квантовой механики, допустимыми преобразованиями со-
стояния квантовой системы S являются унитарные преобразования и измерения.
Проективное измерение состояния квантовой системы определяется спектраль-
ным разложением A =
m∑
i=1
νiPi эрмитового оператора A. В результате такого изме-
рения квантовая система S переходит из состояния |ξ〉 в состояние Pi|ξ〉
‖Pi|ξ〉‖ (i ∈ Nm) с
вероятностью pi = ‖Pi|ξ〉‖2. Отметим, что состояния Pi|ξ〉
‖Pi|ξ〉‖ (i ∈ Nm) попарно орто-
гональны.
Важный специальный случай проективного измерения – измерение в базисе Bn.
Оно определяется эрмитовым оператором A =
n∑
i=1
|i〉〈i|. В результате такого изме-
рения квантовая система S переходит из состояния |ξ〉 = (α1, . . . , αn)T в состояние
αi
|αi| |i〉 (i ∈ Nn) с вероятностью |αi|2.
Замечание 6. В соответствии с положениями квантовой механики, для состояний |ξ〉 и
eiθ|ξ〉 (θ ∈ R) квантовой системы S, совпадающих с точностью до фазового множителя eiθ,
имеет место одна и та же статистика измерений. Поэтому такие состояния рассматриваются
как (физически) эквивалентные, т.е. неразличимые при измерении. По этой причине при
измерении в базисе Bn считают, что квантовая система S переходит из состояния |ξ〉 =
(α1, . . . , αn)T в состояние |i〉 (i ∈ Nn) с вероятностью |αi|2.
Любое квантовое вычисление состоит в применении ряда последовательностей
унитарных преобразований состояния квантовой системы, за каждой из которых
следует измерение. Состояние, полученное при последнем измерении, представля-
ет результат квантового вычисления. Так как финальное состояние (как и каждое
измеренное промежуточное состояние) квантовой системы в процессе ее эволюции
получается с соответствующей вероятностью, то квантовые алгоритмы имеют веро-
ятностную природу.
4. Модели квантовых автоматов. Начиная с 1997г. построен и исследован
ряд, различных по сложности и возможностям, моделей квантовых автоматов. Все
эти модели рассматриваются как распознаватели языка и определены (при тех или
иных ограничениях) в терминах квантовой k-головочной (k ≥ 1) МТ с одной входной
201
В.Г. Скобелев
лентой, функционирующей в пространстве Cn.
Первая, и наиболее простая, модель квантового автомата – MO-1QFA постро-
ена в [19] (эти результаты были опубликованы в 1997г. в препринте «97-97-062
Santa Fe Institute Working Paper»). Эта модель определена в терминах квантовой
1-направленной 1-головочной МТ M = (Q, X, µ, |ψ0〉, Qfin), где Q – множество базисных
состояний Bn, Qfin ⊆ Q – множество финальных базисных состояний, X – входной
алфавит, |ψ0〉 ∈ Cn (‖|ψ0〉‖ = 1) – начальное состояние, а µ – отображение входного
алфавита X во множество n-мерных унитарных матриц (вместо µ(x) (x ∈ X) пишут
Ux). Пусть на входной ленте записано слово $x1 . . . xl#, где x1 . . . xl ∈ X∗ (l ∈ Z+). В
начальный момент МТ M находится в состоянии |ψ0〉, а ее головка обозревает клетку
с левым концевым маркером. Функционирование МТ M состоит из следующих l + 2
шагов:
1) на 1-м шаге головка МТ сдвигается на клетку вправо;
2) на j-м шаге (j = 2, . . . , l+1) (перед его выполнением МТ находится в состоянии
|ψj−2〉, а ее головка обозревает входной символ xj−1) МТ переходит в состояние
|ψj−1〉 = Uxj |ψj−2〉, после чего ее головка сдвигается на клетку вправо;
3) на (l + 2)-м шаге (перед его выполнением МТ находится в состоянии |ψl〉, а ее
головка обозревает правый концевой маркер) состояние |ψl〉 измеряется в базисе Bn
и МТ останавливается.
Слово w = x1 . . . xl ∈ Xl (l ∈ Z+) принимается МТ M тогда и только тогда, ко-
гда результат измерения принадлежит множеству Qfin. Положив Uw = Uxl
. . . Ux1 ,
получим, что вероятность того, что МТ M принимает входное слово w определяется
равенством PM(w) = ‖PaccUw|ψ0〉‖2, где Pacc – проектор на подпространство, порож-
даемое множеством Qfin. Таким образом, для MO-1QFA естественно определяется
распознавание языка с заданной вероятностью или с заданной ошибкой. Отметим,
что каждый обратимый настроенный вероятностный автомат имеет MO-1QFA ана-
лог. В [20] показано, что множество языков, распознаваемых MO-1QFA с заданной
ошибкой, совпадает с множеством LGFA (эти результаты были опубликованы в 1999
г. в Technical Report of University of British Columbia TR-99-03).
В [21] построена модель MM-1QFA, отличающаяся от MO-1QFA тем, что:
1) в множестве Q базисных состояний квантовой (МТ) M выделены непересекаю-
щиеся подмножества Qacc, Qrej и Qnh (Qacc ∪ Qrej ∪ Qnh = Q), соответственно, прини-
мающих, отвергающих и нетерминальных базисных состояний;
2) на каждом промежуточном шаге вычислений после применения соответству-
ющего унитарного оператора допускается измерение в базисе Bn;
3) если на промежуточном шаге после измерения получено состояние q ∈ Qnh,
то МТ переходит к обработке следующего символа, а если состояние q ∈ Qacc ∪ Qrej ,
то МТ останавливается (при этом, слово принимается, если q ∈ Qacc, и отвергается,
если q ∈ Qrej).
Замечание 7. Таким образом, в модели MO-1QFA реализован классический подход к
распознаванию языков, а в модели MM-1QFA – подход, известный как «распознавание с
остановкой» (Decide and Halt). Нетривиальность последнего подхода состоит в том, что он
дал возможность выделить класс задач распознавания, известных как «задачи с перспек-
202
Квантовые автоматы
тивой» (promise problems). Последние характеризуются следующим образом.
С задачей распознавания ассоциируется такой язык L ⊆ {0, 1}∗, что задача сводится к
тому, чтобы принять любой вход, которому соответствует слово w ∈ L, и отвергнуть любой
вход, которому соответствует слово w ∈ {0, 1}∗\L. Предполагается, что заданы непересекаю-
щиеся языки LY ES ∈ {0, 1}∗ и LNO ∈ {0, 1}∗. Язык LY ES ∪ LNO называется «перспективой»
(promise) и предназначен для остановки алгоритма распознавания без дальнейшей обработ-
ки входа. Пусть на промежуточном шаге работы алгоритма распознавания обработанной
части входа соответствует слово v ∈ LY ES ∪LNO. Тогда алгоритм распознавания останавли-
вается (если v ∈ LY ES , то вход принимается, а если v ∈ LNO, то вход отвергается). Если же
v 6∈ LY ES ∪ LNO, то алгоритм распознавания обрабатывает некоторую новую часть входа,
формирует соответствующее слово и осуществляет его анализ указанным способом.
Модель MM-1QFA является более сильной, чем модель MO-1QFA (например,
язык a∗b∗ распознается с ошибкой моделью MM-1QFA, и не распознается с ошиб-
кой моделью MO-1QFA). Тем не менее, модель MM-1QFA распознает только язы-
ки, принадлежащие собственному подмножеству множества LDFA (например, язык
{a, b}∗b не может быть распознан моделью MM-1QFA ни с какой ошибкой).
В [8] установлены оценки вероятностей, с которыми модель MM-1QFA распозна-
ют некоторые подмножества регулярных языков. В частности, показано, что языки,
принадлежащие множеству LGFA, могут быть распознаны моделью MM-1QFA с ве-
роятностью, не меньшей, чем 7
9 .
В [20] в терминах «запрещенных» фрагментов графов переходов детерминиро-
ванных приведенных настроенных автоматов сделана попытка охарактеризовать
класс языков, не распознаваемых моделью MM-1QFA. Эти результаты существенно
усилены в [22] за счет выделения новых «запрещенных» фрагментов. В [22] также
показано, что множество языков, распознаваемых моделью MM-1QFA не замкнуто
относительно булевых операций. Однако, до сих пор отсутствует конструктивный
критерий принадлежности регулярного языка множеству языков, распознаваемых
моделью MM-1QFA.
Большое внимание было уделено сравнению мощностей множеств базисных со-
стояний (в дальнейшем, для краткости, будем говорить множеств состояний) мо-
делей MO-1QFA и MM-1QFA с мощностями множеств состояний настроенных де-
терминированных или вероятностных автоматов, распознающих тот же регулярный
язык.
В [8] показано, что регулярный язык Ln = {ai|i делится на n} (n ≥ 2) распозна-
ется квантовым автоматом с числом состояний O(log n) (n → ∞), а любой настро-
енный детерминированный или вероятностный автомат, распознающий этот язык,
имеет, по крайней мере, n состояний.
Замечание 8. Язык Ln = {ai|i делится на n} (n ≥ 2) принадлежит множеству так на-
зываемых периодических языков. В [23] показано, что любой регулярный n-периодический
(n ≥ 2) язык L в однобуквенном алфавите (т.е. ai ∈ L тогда и только тогда, когда ai+n ∈ L)
распознается квантовым автоматом с O(
√
n) (n →∞) состояниями.
Итак, квантовый автомат может дать экспоненциальный выигрыш в числе со-
стояний по сравнению с настроенным детерминированным или вероятностным ав-
203
В.Г. Скобелев
томатом, распознающим тот же язык.
Замечание 9. В [24] показано, что существует такая последовательность zn (n ∈ N)
задач с перспективой, что задача zn может быть решена квантовым автоматом с двумя
состояниями, а любой вероятностный настроенный автомат, решающий эту задачу, имеет
не менее n состояний, т.е. верхняя граница выигрыша в числе состояний, которую может
дать квантовый автомат по сравнению с вероятностным автоматом, не ограничена.
Однако может иметь место и обратная ситуация. В [25] показано, что любой
квантовый автомат, распознающий регулярный язык Ln = {wa |w ∈ {a, b}∗, |w| < n}
(n ∈ N), имеет не менее 2Ω(n) (n →∞) состояний. В то же время, существует настро-
енный детерминированный автомат с O(n2) (n → ∞) состояниями, распознающий
этот язык.
Значительное число работ было посвящено исследованию различных обобщений
моделей MO-1QFA и MM-1QFA.
Одним из первых обобщений модели MO-1QFA является модель L-QFA (Latvian
QFA). В этой модели вместо одного (т.е. «чистого» (pure)) состояния |ψ〉 ∈ Cn
(‖|ψ〉‖ = 1) используется «смешанное» (mixed) состояние E = {(pi, |ψi〉| i ∈ Nn}
(
n∑
i=1
pi = 1), где pi (i ∈ Nn) – вероятность состояния |ψi〉. Смешанное состояние E
представляется матрицей плотности ρ =
n∑
i=1
pi|ψi〉〈ψi|. Под действием унитарного
оператора U матрица плотности ρ преобразуется в матрицу плотности U †ρU . Свой-
ства модели L-QFA детально исследованы в [26], где, в частности, показано, что
множество языков, распознаваемых моделью L-QFA замкнуто относительно буле-
вых операций. Более того, показано, что это множество языков совпадает с мно-
жеством языков, распознаваемых обратимыми вероятностными настроенными ав-
томатами. Таким образом, к этому классу языков применимы характеристики в
терминах «запрещенных» фрагментов графов переходов детерминированных при-
веденных настроенных автоматов, полученные в [22].
Использование «смешанных» состояний дает возможность получить экспоненци-
альный выигрыш в числе состояний по сравнению с моделью, использующей толь-
ко «чистые» состояния. В [27] показано, что существует такая последовательность
языков Ln (n ∈ N), распознаваемых с вероятностью 0.75 квантовыми автоматами,
имеющими 2n «смешанных» состояний, что квантовый автомат c «чистыми» со-
стояниями, распознающий язык Ln с ошибкой, имеет не менее eO(n ln n) (n → ∞)
состояний.
В [28] построена модель N-QFA, в которой на каждом промежуточном шаге вы-
числений вместо применения одного унитарного оператора допускается применение
конечной последовательности, состоящей из унитарных операторов и проективных
измерений.
Замечание 10. Таким образом, в модели N-QFA, в частности, реализован принцип
использования вспомогательных кубитов (ancilla qubits). Отметим, что в режиме «распо-
знавание с остановкой» (т.е. аналогичном режиму функционирования модели MM-1QFA)
модель N-QFA представляет собой один из конечно-автоматных вариантов модели кванто-
204
Квантовые автоматы
вого компьютера, рассмотренного в [29].
Модель N-QFA распознает только языки, принадлежащие собственному подмно-
жеству множества LDFA (например, язык {a, b}∗b не может быть распознан моде-
лью N-QFA ни с какой ошибкой). Однако, до сих пор отсутствует конструктивный
критерий принадлежности регулярного языка множеству языков, распознаваемых
моделью N-QFA.
В [9] по аналогии с моделью k-буквенного (k ∈ N) группового автомата построена
квантовая модель kQFA.
Эта модель определена в терминах квантовой 1-сторонней k-головочной (k ∈ N)
МТ M = (Q, T, µ, |ψ0〉, Qfin) (где T = {Λ}k ∪
k−1⋃
i=1
{Λ}k−iXi ∪ Xk, а µ – отображение мно-
жества T во множество n-мерных унитарных матриц), головки которой синхронно
сдвигаются вправо. Обозначим через LQFAk
(k ∈ N) множество языков, распознава-
емых моделью kQFA с ограниченной ошибкой, и положим LQFA∗ =
∞⋃
k=1
LQFAk
. В [9]
показано, что LQFAk
⊂ LQFAk+1
(k ∈ N) и LQFA∗ ⊂ LDFA, а также что множество
LQFA∗ замкнуто относительно булевых операций, но не замкнуто относительно опе-
раций конкатенации и итерации. Однако, до сих пор отсутствует конструктивный
критерий принадлежности регулярного языка множеству языков, распознаваемых
моделью kQFA.
Все рассмотренные выше модели квантовых автоматов распознают только соб-
ственное подмножество множества LDFA. Их принято называть квантовыми конеч-
ными автоматами.
Был предпринят ряд попыток расширить множество языков, распознаваемых
квантовыми автоматами, за счет расширения множества действий, допустимых для
модели квантового автомата в процессе распознавания языка. Все полученные таким
образом модели используют средства, не применяемые для классических конечно-
автоматных моделей. Поэтому такие модели не относят к классу квантовых конеч-
ных автоматов. Перечислим некоторые из них.
В [30] построена модель CL-QFA, являющаяся обобщением модели N-QFA. В
этой модели для управления остановкой на промежуточных шагах дополнительно
используется некоторый регулярный язык в алфавите собственных значений эрми-
товых операторов, определяющих применяемые проективные измерения. Доказано,
что CL-QFA распознает с ошибкой множество LDFA всех регулярных языков. Одна-
ко, до сих пор отсутствует конструктивный критерий принадлежности регулярного
языка множеству языков, распознаваемых моделью CL-QFA.
В [21] исследована модель 2-QFA квантового автомата, в которой автомат на
каждом шаге вычислений определяет, в какую сторону, влево или вправо, сдви-
нуться его головке (т.е. модель 2-QFA, представлена квантовой 2-направленной 1-
головочной МТ), а в [31] – модель 1.5-QFA квантового автомата, в которой автомат
на каждом шаге вычислений определяет, сдвинуться ли его головке на клетку впра-
во или остаться на месте.
В [21] и [32] показано, что множество языков, распознаваемых, соответственно, 2-
205
В.Г. Скобелев
направленной и 1.5-направленной моделью QFA включает в себя множество LDFA в
качестве собственного подмножества. Однако, до сих пор отсутствуют конструктив-
ные критерии принадлежности регулярного языка множествам языков, распозна-
ваемых этими моделями. Большая сложность исследования этих моделей вытекает
хотя бы из того, что, как показано в [32], задача анализа пустоты распознаваемого
языка для этих моделей алгоритмически неразрешима.
Следует отметить, что 2-направленная модель QFA может обеспечить субэкспо-
ненциальное ускорение по сравнению с 2-направленным вероятностным автоматом.
Например, в [21] показано, что контекстно-свободный язык L = {anbn|n ∈ N} распо-
знается с ошибкой 2-направленной моделью QFA за полиномиальное время (извест-
но, что (см., напр., [33, 34]) вероятностный 2-направленный настроенный автомат
может распознать этот язык только за экспоненциальное время).
В [35] построена модель C-QFA, являющаяся обобщением модели 1.5-QFA. В
этой модели предполагается, что лента 1.5-направленной 1-головочной МТ является
рабочей, т.е. МТ может не только считывать информацию, но и осуществлять запись
в обозреваемую клетку. Эта модель не получила широкого распространения, и до
сих пор не ясны ее преимущества по сравнению с моделью 1.5-QFA.
В [36-39] исследованы модели 1-направленных, 1.5-направленных и 2-
направленных квантовых автоматов со счетчиком.
Замечание 11. Под настроенным автоматом со «счетчиком» понимается автомат, со-
держащий ячейку, в которую может быть записано любое число. Первоначально содержи-
мое счетчика равно нулю. Действие автомата на каждом шаге вычислений зависит от того,
равно ли содержимое счетчика нулю или нет. При этом, на каждом шаге вычислений содер-
жимое счетчика, в зависимости только от текущего состояния автомата, может быть либо
увеличено на единицу, либо уменьшено на единицу, либо оставлено без изменения.
Отметим, что интерес к квантовым автоматам со счетчиком обусловлен, во мно-
гом, тем обстоятельством, что они имеют преимущества как по силе, так и по скоро-
сти распознавания языков по сравнению с аналогичными вероятностными настро-
енными автоматами со счетчиком.
5. Эквивалентность квантовых конечных автоматов. Задача анализа эк-
вивалентности двух моделей вычислений, имеющих один и тот же входной алфа-
вит, является одной из основных модельных задач теории вычислений. Значение
этой задачи состоит, в частности, в том, что при ее алгоритмической разрешимости
появляется возможность выделить и охарактеризовать те особенности структуры
модели, которые являются существенными для конкретного вычисления.
В терминах распознавания языков l-эквивалентность (l ∈ N) детерминирован-
ных моделей означает, что они распознают одно и то же множество слов длины, не
превосходящей l, а l-эквивалентность вероятностных моделей – что совпадают веро-
ятности принятия этими моделями любого входного слова длины, не превосходящей
l. Аналогичным образом, эквивалентность детерминированных моделей означает,
что они распознают один и тот же язык, а эквивалентность вероятностных моделей
– что совпадают вероятности принятия любого входного слова этими моделями. На-
помним, что квантовые автоматы являются вероятностными моделями вычислений.
206
Квантовые автоматы
Исследование задачи анализа эквивалентности квантовых конечных автоматов
осуществлялось в соответствии с рассмотренным в предыдущем разделе усложне-
нием модели автомата. Перечислим основные результаты, полученные в этом на-
правлении.
Задача анализа эквивалентности двух MO-1QFA моделей впервые была сфор-
мулирована в [19], а ее решение было получено в [40, 41]. В [42] был предложен
полиномиальный алгоритм проверки эквивалентности двух MM-1QFA моделей.
В [43] решена задача анализа эквивалентности моделей k1QFA и k2QFA в од-
нобуквенном входном алфавите. Доказано, что эти модели эквивалентны тогда и
только тогда, когда они (n4 + k − 1)-эквивалентны, где n = n1 + n2, ni (i = 1, 2) –
число базисных состояний модели kiQFA, а k = max{k1, k2}. Отметим, что отсюда, в
частности, вытекает, что в однобуквенном входном алфавите сложность анализа эк-
вивалентности состояний модели kQFA растет линейно с ростом k. В [44] исследова-
на задача анализа эквивалентности моделей k1QFA и k2QFA в m-буквенном входном
алфавите. Доказано, что эти модели эквивалентны тогда и только тогда, когда они
(n2mk−1−mk−1+k)-эквиваленты. Также построен полиномиальный по времени алго-
ритм, анализирующий эквивалентность таких моделей за время O(m2k−1n8+kmkn6)
(n →∞). Отметим, что отсюда, в частности, вытекает, что в m-буквенном входном
алфавите сложность анализа эквивалентности состояний модели kQFA растет экс-
поненциально с ростом k.
6. Заключение. В работе сделана попытка охарактеризовать состояние, в кото-
ром на современном этапе находится теория конечных квантовых автоматов. Четко
вырисовываются следующие возможные направления исследований. Во-первых, это
поиск критериев принадлежности языков множествам языков, распознаваемым мо-
делями конечных квантовых автоматов, возможно, при тех или иных ограничениях.
Во-вторых, это разработка алгоритмов построения минимального конечного кван-
тового автомата и характеристика структуры этого автомата.
1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматлит, 1962. – 476 с.
2. Hennie F.C. Finite state models for logical machines. – NY.: Wiley&Sons Inc., 1962. – 466 p.
3. Гилл А. Введение в теорию конечных автоматов. – М.: Наука, 1966. – 272 с.
4. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). – М.: Наука,
1970. – 400 с.
5. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Введение в теорию конечных автоматов. –
М.: Наука, 1985. – 320 с.
6. Huffman D.A. Cannonical forms for information-loseless finite state logical machines // IRE Trans-
actions Circuit Theoty. Special Supplment. – 1959. – Vol. CT-6. – P. 41-59.
7. Even S. On information-loseless automata of finite order // IEEE Transactions on Electronic
Computers. – 1965. – № 4. – P. 561-569.
8. Ambainis A., Freivalds R. 1-way quantum automata: strength, weakness and generalizations //
Proceedings of the 39th Annual Symposium on Fondations of Computer Science. – 1998. – P. 332-
341.
9. Belovs A., Rosmanis A., Smotrovs J.Multi-letter reversible and quantum finite automata // Lecture
Notes in Computer Science. – 2007. – Vol. 4588. – P. 60-71.
10. Hromkovič J. One-way multihead deterministic finite automata // Acta Informatica. – 1983. –
Vol. 19. – P. 377-384.
11. Rabin M.O. Probabilistic automata // Information and Control. – 1963. – № 3. – P. 230-245.
207
В.Г. Скобелев
12. Paz A. Introduction to probabilistic automata. – NY.: Academic Press, 1971. – 228 p.
13. Бухараев Р.Г. Основы теории вероятностных автоматов. – М.: Наука, 1985. – 287 с.
14. Кемени Д.Д., Снелл Д.Л. Конечные цепи Маркова. – М.: Наука, 1970. – 271 с.
15. Ambainis A. The complexity of probabilistic versus deterministic finite automata // Lecture Notes
in Computer Science. – 1996. – Vol. 1178. – P. 233-237.
16. Freivalds R.Non-constructive methods for finite probabilistic automata // Lecture Notes in Computer
Science. – 2007. – Vol. 4588. – P. 169-180.
17. Ожигов Ю.И. Квантовые вычисления. – М.: МГУ, факультет ВМиК, 2003. – 104 с.
18. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М.: Мир, 2006. –
824 с.
19. Moore C., Crutchfield J. Quantum automata and quantum grammars // Theoretical Computer
Science. – 2000. – Vol. 237. – P. 257-306.
20. Brodsky A., Pipenger N. Characterizations of 1-way quantum finite automata // Journal of Computing.
– 2002. – № 5. – P. 1456-1478.
21. Kondacs A., Watrous J. On the power of quantum finite state automata // Proceedings of the 38th
IEEE Symposium on Foundations of Computer Science. – 1997. – P. 66-75.
22. Ambainis A., Kikusts A., Valdats M. On some class of languages recognizable by 1-way quantum
automata // Lecture Notes in Computer Science. – 2001. – Vol. 2010. – P. 75-86.
23. Mereghetti C., Palano B. On the size of one-way quantum finite automata with periodic behaviors
// Theoretical Informatics and Applications. – 2002. – № 3. – P. 277-291.
24. Yakaryilmaz A. Exact quantum algorithm for promise problems in automata theory.
http://arhiv.org/abc/1101.3837
25. Ambainis A., Nayak A., Ta-Shma A., Vazirani U. Dense quantum coding and a lower bound
for 1-way quantum automata // Proceedings of the 31st Annual ACM Symposium on Theory of
Computation. – 1999. – P. 276-383.
26. Ambainis A., Beaudry M., Golovkins M., Kikusts A., Mercer M., Thrien D. Algebraic results on
quantum automata // Lecture Notes in Computer Science. – 2004. – Vol. 2996. – P. 93-104.
27. Freivalds R., Ozols M., Mančinska L. Improved constructions of mixed state quantum automata //
Theoretical Computer Science. – 2009. – Vol. 418. – 1923-1931.
28. Nayak A. Optimal lower bounds for quantum automata and random access codes // Proceedings
of the 40th Annual IEEE Symposium on Fondations of Computer Science. – 1999. – P. 369-377.
29. Aharonov D., Kitaev A., Nisan N. Quantum circuits with mixed states // Proceedings of the 30th
Annual ACM Symposium on Theory of Computation. – 1998. – P. 20-30.
30. Bertoni A., Mereghetti C., Palano B. Quatum computing: 1-way quantum automata // Lecture
Notes in Computer Science. – 2003. – Vol. 2710. – P. 1-20.
31. Amano V., Iwama K. Undesidability on quantum finite automata // Proceedings of the 31st Annual
ACM Symposium on Theory of Computation. – 1999. – P. 368-375.
32. Dubrovsky A. Space-efficient 1.5-way Turing machine // Lecture Notes in Computer Science. – 2001.
– Vol. 2138. – P. 380-383.
33. Freivalds R. Probabilistic two-way machines // Lecture Notes in Computer Science. – 1981. –
Vol. 118. – P. 33-45.
34. Dwork C., Stockmeyer L. On the power of 2-way probabilistic finite-state automata // Proceedings
of the 30th Annual IEEE Symposium on Fondations of Computer Science. – 1989. – P. 480-485.
35. Ciamarra M.P. Quantum reversibility and a new model of quantum automaton // Lecture Notes
in Computer Science. – 2001. – Vol. 2138. – P. 376-379.
36. Kravtsevs M. Quantum one counter automata // Lecture Notes in Computer Science. – 1999. –
Vol. 1725. – P. 431-440.
37. Yamasali T., Kobayashi H., Tokunaga Y., Imai H. One-way probabilistic reversible and quantum
automata // Lecture Notes in Computer Science. – 2000. – Vol. 1858. – P. 436-446.
38. Bonner R., Freivalds R., Kravtsevs M. Quantum versus probabilistic one-way finite automata with
counter // Lecture Notes in Computer Science. – 2001. – Vol. 2234. – P. 181-190.
39. Yamasali T., Kobayashi H., Imai H. Quantum versus deterministic counter automata // Lecture
Notes in Computer Science. – 2002. – Vol. 2387. – P. 584-594.
208
Квантовые автоматы
40. Qiu D.W. Characterization of sequential quantum machines // International Journal of Theoretical
Physics. – 2002. – № 4. – P. 811-822.
41. Li L.Z., Qiu D.W. Determination of equivalence between quantum sequential machines //
Theoretical Computer Science. – 2006. – Vol. 358. – P. 65-74.
42. Li L.Z., Qiu D.W. Determining the equivalence for one-way quantum automata // Theoretical
Computer Science. – 2008. – Vol. 403. – P. 42-51.
43. Qiu D.W., Yu S. Hierarhy and equivalence of multi-letter quantum finite automata // Theoretical
Computer Science. – 2009. – Vol. 410. – P. 3006-3017.
44. Qiu D.W., Li L., Zou X., Mateus P., Gruska J. Multi-letter quantum finite automata: decidability
of the equivalence and minimization of states // Acta Informatika. – 2011. – Vol. 48. – P. 271-290.
V.G. Skobelev
Theory of finite quantum automata (survey).
In the given paper it is considered variety of models for quantum automata. There are extracted models,
which are called finite quantum automata, as well as the ones which are not models for finite quantum
automata (since they explore these or the other tools which are not used for classical finite-automata
models). Basic results connected with analysis of equivalency of finite quantum automata are listed.
Keywords: models of quantum automata, equivalency of finite quantum automata.
В. Г. Скобелєв
Теорiя скiнченних квантових автоматiв (огляд).
У роботi розглянуто рiзноманiття iснуючих моделей квантових автоматiв. Видiлено моделi, якi
прийнято називати скiнченними квантовими автоматами, а також моделi, що не є такими (оскiльки
засоби, якi у них використано, не застосовуються для класичних скiнченно-автоматних моделей).
Наведено основнi результати, пов’язанi з аналiзом еквiвалентностi скiнченних квантових автоматiв.
Ключовi слова: моделi квантових автоматiв, еквiвалентнiсть скiнченних квантових авто-
матiв.
Ин-т прикл. математики и механики НАН Украины, Донецк
skbv@iamm.ac.donetsk.ua
Получено 31.05.12
209
|
| id | nasplib_isofts_kiev_ua-123456789-124130 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T17:58:51Z |
| publishDate | 2012 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Скобелев, В.Г. 2017-09-20T11:54:08Z 2017-09-20T11:54:08Z 2012 Теория конечных квантовых автоматов (обзор) / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 196-209. — Бібліогр.: 44 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/124130 530.145+519.713 В работе рассмотрено многообразие существующих моделей квантовых автоматов. Выделены модели, которые принято называть конечными квантовыми автоматами, также модели, которые таковыми не являются (так как они используют средства, не применяемые для классических конечно-автоматных моделей). Приведены основные результаты, связанные с анализом эквивалентности конечных квантовых автоматов. У роботi розглянуто рiзноманiття iснуючих моделей квантових автоматiв. Видiлено моделi, якi прийнято називати скiнченними квантовими автоматами, а також моделi, що не є такими (оскiльки засоби, якi у них використано, не застосовуються для класичних скiнченно-автоматних моделей). Наведено основнi результати, пов’язанi з аналiзом еквiвалентностi скiнченних квантових автоматiв. In the given paper it is considered variety of models for quantum automata. There are extracted models, which are called finite quantum automata, as well as the ones which are not models for finite quantum automata (since they explore these or the other tools which are not used for classical finite-automata models). Basic results connected with analysis of equivalency of finite quantum automata are listed. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Теория конечных квантовых автоматов (обзор) Теорiя скiнченних квантових автоматiв (огляд) Theory of finite quantum automata (survey) Article published earlier |
| spellingShingle | Теория конечных квантовых автоматов (обзор) Скобелев, В.Г. |
| title | Теория конечных квантовых автоматов (обзор) |
| title_alt | Теорiя скiнченних квантових автоматiв (огляд) Theory of finite quantum automata (survey) |
| title_full | Теория конечных квантовых автоматов (обзор) |
| title_fullStr | Теория конечных квантовых автоматов (обзор) |
| title_full_unstemmed | Теория конечных квантовых автоматов (обзор) |
| title_short | Теория конечных квантовых автоматов (обзор) |
| title_sort | теория конечных квантовых автоматов (обзор) |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124130 |
| work_keys_str_mv | AT skobelevvg teoriâkonečnyhkvantovyhavtomatovobzor AT skobelevvg teoriâskinčennihkvantovihavtomativoglâd AT skobelevvg theoryoffinitequantumautomatasurvey |