Квантовый конечный автомат - Quantum finite automaton - Wikipedia

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

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

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

Неформальное описание

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

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

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

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

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

Другое обобщение, которое должно стать очевидным, - это использование стохастическая матрица для матриц перехода и a вектор вероятности для государства; это дает вероятностный конечный автомат. Записи в векторе состояния должны быть действительными числами, положительными и суммой равными единице, чтобы вектор состояния интерпретировался как вероятность. Матрицы переходов должны сохранять это свойство: поэтому они должны быть стохастическими. Каждый вектор состояния следует представить как задающий точку в симплекс; таким образом, это топологический автомат, где симплекс является многообразием, а стохастические матрицы являются линейными автоморфизмами симплекса на себя. Поскольку каждый переход (по существу) не зависит от предыдущего (если мы не обращаем внимания на различие между принятыми и отклоненными языками), 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 \mathbb {C} P^{N}}$ является элементом ${\displaystyle N}$-размерный сложное проективное пространство, несущий внутренний продукт ${\displaystyle \Vert \cdot \Vert }$ это Метрика Фубини – Этюд.

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

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

Таким образом, тройная ${\displaystyle (\mathbb {C} P^{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 \sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})}$ дан кем-то

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

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

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

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

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

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

Пример

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

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

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

Квантовое состояние - это вектор, в обозначение бюстгальтера

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

с сложные числа ${\displaystyle a_{1},a_{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}}}$

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

${\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}}\subset Q}$ и ${\displaystyle Q_{\text{rej}}\subset 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 |\psi ^{\prime }\rangle }$, используя операторы проекции ${\displaystyle P}$, когда его волновая функция коллапсирует в одно из трех подпространств ${\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}}$

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

Если волновая функция сжалась до подпространства «принять» или «отклонить», дальнейшая обработка останавливается. В противном случае обработка продолжается со следующей буквой, считанной из ввода и примененной к тому, что должно быть собственным состоянием ${\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 |\psi \rangle =|q_{0}\rangle }$. Унитарные преобразования обозначаются отображением ${\displaystyle \delta }$,

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

так что

${\displaystyle U_{\alpha }|q_{1}\rangle =\sum _{q_{2}\in Q}\delta (q_{1},\alpha ,q_{2})|q_{2}\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-размерный) Симметричное пространство Римана занять место ${\displaystyle \mathbb {C} P^{N}}$. Вместо унитарных матриц используется изометрии риманова многообразия или, в более общем смысле, некоторого набора открытые функции подходит для данного топологического пространства. Исходное состояние можно принять за точку в пространстве. Множество допустимых состояний можно принять как произвольное подмножество топологического пространства. Затем говорят, что формальный язык принимается этим топологический автомат если точка после итерации гомеоморфизмами пересекает принимаемое множество. Но, конечно, это не более чем стандартное определение М-автомат. Поведение топологических автоматов изучается в области топологическая динамика.

Квантовый автомат отличается от топологического в том, что вместо двоичного результата (входит ли повторяемая точка в окончательный набор или нет?), Есть вероятность. Квантовая вероятность - это (квадрат) начального состояния, спроецированного на некоторое конечное состояние. п; то есть ${\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}}$ обобщается на некоторые метрическое пространство, а вероятностная мера заменяется простой функцией метрики на этом пространстве.

Смотрите также

• Квантовая цепь Маркова

Примечания

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