Квантовый конечный автомат

В вычислениях квантовых квантовые конечные автоматы ( QFA ) или квантовые конечные автоматы являются квантовым аналогом вероятностных автоматов или марковского процесса принятия решений . Они обеспечивают математическую абстракцию реальных квантовых компьютеров . Могут быть определены несколько типов автоматов, включая автоматы с однократным измерением и автоматы с множественным измерением . Квантовые конечные автоматы можно также понимать как квантование подсдвигов конечного типа или как квантование цепей Маркова . ККА, в свою очередь, являются частными случаями геометрических конечных автоматов или топологических конечных автоматов .

Автоматы работают, получая строку конечной длины. $\sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})$ букв $\sigma _{i}$ из конечного алфавита $\Sigma$ и присваиваем каждой такой строке вероятность $\operatorname {Pr} (\sigma )$ указание вероятности нахождения автомата в состоянии принятия ; то есть указывает, принял или отклонил автомат строку.

Языки , принимаемые QFA, не являются ни регулярными языками детерминированных конечных автоматов , ни стохастическими языками вероятностных конечных автоматов . Изучение этих квантовых языков остается активной областью исследований.

Неофициальное описание

Существует простой и интуитивно понятный способ понимания квантовых конечных автоматов. Каждый начинает с теоретико-графовой интерпретации детерминированных конечных автоматов (DFA). DFA можно представить в виде ориентированного графа с состояниями в качестве узлов графа и стрелками, обозначающими переходы между состояниями. Каждая стрелка помечена возможным входным символом, так что, учитывая определенное состояние и входной символ, стрелка указывает на следующее состояние. Один из способов представления такого графа — с помощью набора матриц смежности , по одной матрице для каждого входного символа. В этом случае список возможных состояний DFA записывается как вектор-столбец . Для данного входного символа матрица смежности указывает, как любое данное состояние (строка в векторе состояния) перейдет в следующее состояние; переход между состояниями задается умножением матриц .

Для каждого возможного входного символа необходима отдельная матрица смежности, поскольку каждый входной символ может привести к различному переходу. Записи в матрице смежности должны быть равны нулю и единице. Для любого данного столбца в матрице только одна запись может быть ненулевой: это запись, которая указывает следующий (уникальный) переход состояния. Аналогично, состояние системы представляет собой вектор-столбец, в котором только одна запись не равна нулю: эта запись соответствует текущему состоянию системы. Позволять $\Sigma$ обозначают набор входных символов. Для данного входного символа $\alpha \in \Sigma$ , писать $U_{\alpha }$ как матрица смежности, которая описывает эволюцию DFA к следующему состоянию. Набор $\{U_{\alpha }|\alpha \in \Sigma \}$ затем полностью описывает функцию перехода состояний DFA. Пусть Q представляет собой множество возможных состояний ДКА. имеется N Если в Q состояний , то каждая матрица $U_{\alpha }$ является N на N -мерным. Исходное состояние $q_{0}\in Q$ соответствует вектор-столбцу с единицей в q ₀ -й строке. Тогда общее состояние q представляет собой вектор-столбец с единицей в q'-й строке. Злоупотребляя обозначениями , пусть q ₀ и q также обозначают эти два вектора. Затем, после прочтения входных символов $\alpha \beta \gamma \cdots$ с входной ленты состояние DFA будет определяться выражением $q=\cdots U_{\gamma }U_{\beta }U_{\alpha }q_{0}.$ Переходы состояний задаются обычным матричным умножением (т. е. умножением q ₀ на $U_{\alpha }$ , и т. д. ); порядок применения «обратный» только потому, что мы следуем стандартным обозначениям линейной алгебры .

Приведенное выше описание ДКА в терминах линейных операторов и векторов почти требует обобщения путем замены вектора состояния q некоторым общим вектором и матриц $\{U_{\alpha }\}$ некоторыми общими операторами. По сути, это то, что делает QFA: он заменяет q единичным вектором , а $\{U_{\alpha }\}$ по унитарным матрицам . Становятся очевидными и другие подобные обобщения: вектор q может быть некоторым распределением на многообразии ; множество матриц перехода становятся автоморфизмами многообразия; это определяет топологический конечный автомат. Аналогично матрицы можно рассматривать как автоморфизмы однородного пространства ; это определяет геометрический конечный автомат.

Прежде чем перейти к формальному описанию QFA, следует упомянуть и понять два примечательных обобщения. Первый — это недетерминированный конечный автомат (НКА). В этом случае вектор q заменяется вектором, который может иметь более одной записи, отличной от нуля. Тогда такой вектор представляет собой элемент степеней набора Q ; это просто функция Q индикаторная . Аналогично, матрицы перехода состояний $\{U_{\alpha }\}$ определяются таким образом, что в данном столбце может быть несколько ненулевых записей. Эквивалентно, операции умножения-сложения, выполняемые при покомпонентном умножении матриц, должны быть заменены булевыми операциями и/или, то есть так, чтобы мы работали с кольцом характеристики 2 .

Известная теорема утверждает, что для каждого ДКА существует эквивалентный НКА, и наоборот . Это означает, что набор языков , которые могут распознаваться DFA и NFA, один и тот же; это обычные языки . При обобщении QFA набор признанных языков будет другим. Описание этого множества — одна из выдающихся исследовательских задач теории QFA.

Другое обобщение, которое должно сразу бросаться в глаза, — это использование стохастической матрицы для матриц перехода и вектора вероятности для состояния; это дает вероятностный конечный автомат . Элементы вектора состояния должны быть действительными числами, положительными и иметь сумму, равную единице, чтобы вектор состояния можно было интерпретировать как вероятность. Матрицы перехода должны сохранять это свойство: именно поэтому они должны быть стохастическими. Каждый вектор состояния следует представлять себе как определяющий точку симплекса ; таким образом, это топологический автомат, в котором симплекс является многообразием, а стохастические матрицы являются линейными автоморфизмами симплекса на самого себя. Поскольку каждый переход (по сути) независим от предыдущего (если не принимать во внимание различие между принятыми и отвергнутыми языками), PFA по сути становится своего рода цепью Маркова .

Напротив, в QFA многообразие представляет собой комплексное проективное пространство. $\mathbb {C} P^{N}$ , а матрицы перехода являются унитарными матрицами. Каждая точка в $\mathbb {C} P^{N}$ соответствует (чистому) квантовомеханическому состоянию ; унитарные матрицы можно рассматривать как управляющие эволюцией системы во времени (а именно, в картине Шрёдингера ). Обобщение чистых состояний на смешанные состояния должно быть простым: смешанное состояние — это просто теоретико-мерное распределение вероятностей на $\mathbb {C} P^{N}$ .

Достойный внимания момент — это распределения, которые возникают в многообразии во время ввода языка. Чтобы автомат мог «эффективно» распознавать язык, это распределение должно быть «насколько это возможно равномерным». Эта потребность в единообразии является основополагающим принципом методов максимальной энтропии : они просто гарантируют четкую и компактную работу автомата. Другими словами, методы машинного обучения , используемые для обучения скрытых моделей Маркова, также обобщаются на QFA: алгоритм Витерби и алгоритм вперед-назад легко обобщаются на QFA.

Хотя исследование QFA было популяризировано в работе Кондакса и Уотроуса в 1997 г. ^{[ 1 ]} а позже Мур и Кратчфельд, ^{[ 2 ]} они были описаны еще в 1971 году Ионом Баяну . ^{[ 3 ]}^{[ 4 ]}

Автоматы, измеряемые один раз

Автоматы с однократной мерой были представлены Крисом Муром и Джеймсом П. Кратчфилдом . ^{[ 2 ]} Формально их можно определить следующим образом.

Как и в случае с обычным конечным автоматом , считается, что квантовый автомат имеет $N$ возможные внутренние состояния, представленные в данном случае $N$ -государственный кудит $|\psi \rangle$ . Точнее, $N$ -государственный кудит $|\psi \rangle \in P(\mathbb {C} ^{N})$ является элементом $(N-1)$ -мерное сложное проективное пространство , несущее внутренний продукт $\Vert \cdot \Vert$ это метрика Фубини–Студи .

Переходы состояний , матрицы переходов или графы де Брейна представлены набором $N\times N$ унитарные матрицы $U_{\alpha }$ , с одной унитарной матрицей для каждой буквы $\alpha \in \Sigma$ . То есть, учитывая входную букву $\alpha$ , унитарная матрица описывает переход автомата из текущего состояния $|\psi \rangle$ в свое следующее состояние $|\psi ^{\prime }\rangle$ :

|\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle

Таким образом, тройка $(P(\mathbb {C} ^{N}),\Sigma ,\{U_{\alpha }\;\vert \;\alpha \in \Sigma \})$ образуют квантовый полуавтомат .

Приемное состояние автомата задается $N\times N$ матрица проекции $P$ , так что, учитывая $N$ -мерное квантовое состояние $|\psi \rangle$ , вероятность $|\psi \rangle$ находиться в состоянии принятия

\langle \psi |P|\psi \rangle =\Vert P|\psi \rangle \Vert ^{2}

Вероятность того, что конечный автомат примет заданную конечную входную строку $\sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})$ дается

\operatorname {Pr} (\sigma )=\Vert PU_{\sigma _{k}}\cdots U_{\sigma _{1}}U_{\sigma _{0}}|\psi \rangle \Vert ^{2}

Здесь вектор $|\psi \rangle$ Под ним понимается начальное состояние автомата, то есть состояние, в котором он находился до того, как он начал принимать строковые входные данные. Пустая строка $\varnothing$ понимается как единичная матрица, так что

\operatorname {Pr} (\varnothing )=\Vert P|\psi \rangle \Vert ^{2}

это просто вероятность того, что начальное состояние будет принятым.

Поскольку левое действие $U_{\alpha }$ на $|\psi \rangle$ меняет порядок букв в строке $\sigma$ , QFA нередко определяются с использованием правильного действия над состояниями эрмитового транспонирования просто для того, чтобы сохранить порядок букв одинаковым.

Язык над алфавитом $\Sigma$ принимается с вероятностью $p$ квантовым конечным автоматом (и заданным фиксированным начальным состоянием $|\psi \rangle$ ), если для всех предложений $\sigma$ в языке есть $p\leq \operatorname {Pr} (\sigma )$ .

Пример

Рассмотрим классический детерминированный конечный автомат, заданный таблицей переходов состояний

**Таблица перехода состояний**
Вход Состояние	1	0
С ₁	С ₁	S_S2
S_S2	S_S2	С ₁

Государственная диаграмма

Квантовое состояние представляет собой вектор в обозначениях бра-кета.

|\psi \rangle =a_{1}|S_{1}\rangle +a_{2}|S_{2}\rangle ={\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}

с комплексными числами $a_{1},a_{2}$ нормализовано так, что

{\begin{bmatrix}a_{1}^{*}\;\;a_{2}^{*}\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}=a_{1}^{*}a_{1}+a_{2}^{*}a_{2}=1

Унитарные матрицы перехода:

U_{0}={\begin{bmatrix}0&1\\1&0\end{bmatrix}}

и

U_{1}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}

принимая $S_{1}$ чтобы быть состоянием принятия, матрица проекции равна

P={\begin{bmatrix}1&0\\0&0\end{bmatrix}}

Как должно быть очевидно, если исходное состояние является чистым состоянием $|S_{1}\rangle$ или $|S_{2}\rangle$ , то результат работы машины будет точно идентичен классическому детерминированному конечному автомату. В частности, для этих начальных состояний существует язык, принимаемый этим автоматом с вероятностью единица, и он идентичен регулярному языку для классического ДКА и задается регулярным выражением :

(1^{*}(01^{*}0)^{*})^{*}\,\!

Неклассическое поведение имеет место, если оба $a_{1}$ и $a_{2}$ ненулевые. Более тонкое поведение происходит, когда матрицы $U_{0}$ и $U_{1}$ не так просты; см., например, кривую де Рама как пример квантового конечного автомата, действующего на множестве всех возможных конечных двоичных строк.

Автоматы измерения многих

Автоматы типа «мера-многие» были представлены Кондаксом и Уотрусом в 1997 году. ^{[ 1 ]} Общая структура напоминает автомат с однократным измерением, за исключением того, что вместо одной проекции в конце имеется проекция, или квантовое измерение , выполняемое после прочтения каждой буквы. Далее следует формальное определение.

Гильбертово пространство ${\mathcal {H}}_{Q}$ разлагается на три ортогональных подпространства

{\mathcal {H}}_{Q}={\mathcal {H}}_{\text{accept}}\oplus {\mathcal {H}}_{\text{reject}}\oplus {\mathcal {H}}_{\text{non-halting}}

В литературе эти ортогональные подпространства обычно формулируются в терминах множества $Q$ ортогональных базисных векторов гильбертова пространства ${\mathcal {H}}_{Q}$ . Этот набор базисных векторов разделен на подмножества. $Q_{\text{acc}}\subseteq Q$ и $Q_{\text{rej}}\subseteq Q$ , такой, что

{\mathcal {H}}_{\text{accept}}=\operatorname {span} \{|q\rangle :|q\rangle \in Q_{\text{acc}}\}

— линейная оболочка базисных векторов в принятом наборе. Пространство отклонения определяется аналогично, а оставшееся пространство обозначается как непрерывное подпространство. Имеются три матрицы проекций, $P_{\text{acc}}$ , $P_{\text{rej}}$ и $P_{\text{non}}$ , каждый из которых проецируется в соответствующее подпространство:

P_{\text{acc}}:{\mathcal {H}}_{Q}\to {\mathcal {H}}_{\text{accept}}

и так далее. Анализ входной строки происходит следующим образом. Считаем, что автомат находится в состоянии $|\psi \rangle$ . После прочтения входного письма $\alpha$ , автомат будет в состоянии

|\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle

На этом этапе измерение, три возможных результата которого имеют собственные пространства ${\mathcal {H}}_{\text{accept}}$ , ${\mathcal {H}}_{\text{reject}}$ , ${\mathcal {H}}_{\text{non-halting}}$ выполняется в состоянии $|\psi ^{\prime }\rangle$ , и в этот момент его волновая функция коллапсирует в одно из трех подпространств ${\mathcal {H}}_{\text{accept}}$ или ${\mathcal {H}}_{\text{reject}}$ или ${\mathcal {H}}_{\text{non-halting}}$ . Вероятность коллапса в подпространство «принятия» определяется выражением

\operatorname {Pr} _{\text{acc}}(\sigma )=\Vert P_{\text{acc}}|\psi ^{\prime }\rangle \Vert ^{2},

и аналогично для двух других пространств.

Если волновая функция схлопнулась либо в подпространства «принять», либо «отклонить», дальнейшая обработка останавливается. В противном случае обработка продолжается, следующая буква считывается со входа и применяется к тому, что должно быть собственным состоянием $P_{\text{non}}$ . Обработка продолжается до тех пор, пока не будет прочитана вся строка или машина не остановится. Часто дополнительные символы $\kappa$ и $ примыкают к алфавиту и служат левым и правым конечными маркерами строки.

В литературе многомерный автомат часто обозначается кортежем $(Q;\Sigma ;\delta ;q_{0};Q_{\text{acc}};Q_{\text{rej}})$ . Здесь, $Q$ , $\Sigma$ , $Q_{\text{acc}}$ и $Q_{\text{rej}}$ такие, как определено выше. Начальное состояние обозначается $|q_{0}\rangle$ . Унитарные преобразования обозначаются отображением $\delta$ ,

\delta :Q\times \Sigma \times Q\to \mathbb {C}

так что

U_{\alpha }|q_{i}\rangle =\sum _{q_{j}\in Q}\delta (q_{i},\alpha ,q_{j})|q_{j}\rangle

Связь с квантовыми вычислениями

По состоянию на 2019 год большинство квантовых компьютеров представляют собой реализации квантовых конечных автоматов с однократным измерением, а программные системы для их программирования демонстрируют подготовку состояний $|\psi \rangle$ , измерение $P$ и выбор унитарных преобразований $U_{\alpha }$ , такие как управляемый вентиль НЕ , преобразование Адамара и другие квантовые логические вентили , непосредственно программисту.

Основное различие между реальными квантовыми компьютерами и теоретической базой, представленной выше, заключается в том, что подготовка начального состояния никогда не может привести к точечному чистому состоянию , а также невозможно точно применить унитарные операторы. Таким образом, начальное состояние необходимо принять как смешанное состояние.

\rho =\int p(x)|\psi _{x}\rangle dx

для некоторого распределения вероятностей $p(x)$ характеризующая способность оборудования готовить исходное состояние, близкое к желаемому исходному чистому состоянию. $|\psi \rangle$ . Это состояние нестабильно, но страдает от некоторой квантовой декогеренции со временем . Точные измерения также невозможны, и вместо этого используются положительные операторные меры для описания процесса измерения . Наконец, каждое унитарное преобразование — это не один четко определенный квантовый логический элемент, а скорее смесь

U_{\alpha ,(\rho )}=\int p_{\alpha }(x)U_{\alpha ,x}dx

для некоторого распределения вероятностей $p_{\alpha }(x)$ описание того, насколько хорошо оборудование может осуществить желаемое преобразование $U_{\alpha }$ .

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

Не существует квантового аналога автомата с выталкивающим устройством или стековой машины . Это связано с теоремой о запрете клонирования : нет возможности сделать копию текущего состояния машины, поместить ее в стек для последующего использования, а затем вернуться к нему.

Геометрические обобщения

Приведенные выше конструкции показывают, как понятие квантового конечного автомата может быть обобщено на произвольные топологические пространства . Например вместо , $\mathbb {C} P^{N}$ . Вместо унитарных матриц используются изометрии риманова многообразия или, в более общем смысле, некоторый набор открытых функций, соответствующий данному топологическому пространству. За начальное состояние можно принять точку в пространстве. Множество состояний принятия можно считать некоторым произвольным подмножеством топологического пространства. Тогда говорят, что формальный язык принимается этим топологическим автоматом , если точка после итерации по гомеоморфизмам пересекает приемное множество. Но, конечно, это не что иное, как стандартное определение М-автомата . Поведение топологических автоматов изучается в области топологической динамики .

Квантовый автомат отличается от топологического автомата тем, что вместо двоичного результата (входит ли повторяемая точка в окончательный набор или нет?) у него есть вероятность. Квантовая вероятность — это (квадрат) начального состояния, спроецированный на некоторое конечное состояние P ; то есть $\mathbf {Pr} =\vert \langle P\vert \psi \rangle \vert ^{2}$ . Но эта амплитуда вероятности — всего лишь очень простая функция расстояния между точками $\vert P\rangle$ и точка $\vert \psi \rangle$ в $\mathbb {C} P^{N}$ расстояния, , при метрике заданной метрикой Фубини–Студи . Напомним, что квантовую вероятность принятия языка можно интерпретировать как метрику, причем вероятность принятия равна единице, если метрическое расстояние между начальным и конечным состояниями равно нулю, а в противном случае вероятность принятия меньше единицы. если метрическое расстояние не равно нулю. Таким образом, следует, что квантовый конечный автомат является лишь частным случаем геометрического автомата или метрического автомата , где $\mathbb {C} P^{N}$ обобщается на некоторое метрическое пространство , а вероятностная мера заменяется простой функцией метрики этого пространства.

См. также

Примечания

^ Перейти обратно: ^а ^б Кондакс, А.; Уотрус, Дж. (1997), «О мощности квантовых автоматов с конечным состоянием», Труды 38-го ежегодного симпозиума по основам информатики , стр. 66–75.
^ Перейти обратно: ^а ^б К. Мур, Дж. Крачфилд, «Квантовые автоматы и квантовые грамматики», Theoretical Computer Science , 237 (2000), стр. 275–306.
^ И. Баяну, « Организмические суперкатегории и качественная динамика систем » (1971), Бюллетень математической биофизики, 33 стр. 339-354.
^ И. Баяну, «Категории, функторы и теория квантовых автоматов» (1971). 4-й международный Конгресс ЛМПС, август-сентябрь 1971 г.

[Kondacs-1] Перейти обратно: ^а ^б Кондакс, А.; Уотрус, Дж. (1997), «О мощности квантовых автоматов с конечным состоянием», Труды 38-го ежегодного симпозиума по основам информатики , стр. 66–75.

[Moore-2] Перейти обратно: ^а ^б К. Мур, Дж. Крачфилд, «Квантовые автоматы и квантовые грамматики», Theoretical Computer Science , 237 (2000), стр. 275–306.

[3] И. Баяну, « Организмические суперкатегории и качественная динамика систем » (1971), Бюллетень математической биофизики, 33 стр. 339-354.

[4] И. Баяну, «Категории, функторы и теория квантовых автоматов» (1971). 4-й международный Конгресс ЛМПС, август-сентябрь 1971 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]