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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Состояние принятия автомата задается проекционной матрицей , так что при заданном -мерном квантовом состоянии вероятность нахождения в состоянии принятия равна${\displaystyle N\times N}$ ${\displaystyle P}$${\displaystyle N}$${\displaystyle |\psi \rangle }$${\displaystyle |\psi \rangle }$

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

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

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

Здесь вектор понимается как представляющий начальное состояние автомата, то есть состояние, в котором автомат находился до того, как начал принимать входную строку. Пустая строка понимается как просто единичная матрица, так что${\displaystyle |\psi \rangle }$${\displaystyle \varничего_не_существующего }$

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

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

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

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

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

Таблица переходов состояний Состояние   ввода 1 0 С 1 С 1 С 2 С 2 С 2 С 1

Диаграмма состояний

Квантовое состояние – это вектор в скобочной записи

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

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

${\displaystyle {\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}$

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

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

и

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

Принимая в качестве состояния принятия, матрица проекции имеет вид${\displaystyle S_{1}}$

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

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

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

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

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

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

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

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

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

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

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

и так далее. Разбор входной строки происходит следующим образом. Предположим, что автомат находится в состоянии . После прочтения входной буквы автомат будет находиться в состоянии${\displaystyle |\psi \rangle }$${\displaystyle \alpha }$

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

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

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

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

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

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

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

так что

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

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

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

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

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

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

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

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

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

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

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

• Квантовая цепь Маркова
• Машина Блюма–Шуба–Смейла
• Настоящий компьютер