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

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

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

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

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

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

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

Приведенное выше описание DFA в терминах линейных операторов и векторов почти требует обобщения, заменяя вектор состояния q некоторым общим вектором, а матрицы - некоторыми общими операторами. Это, по сути , что делает QFA: он заменяет д по амплитуде вероятности , и с помощью унитарных матриц . Становятся очевидными и другие подобные обобщения: вектор 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 было популяризировано в работах Кондакса и Уотроуса в 1997 году, а затем Муром и Кратчфельдом, они были описаны еще в 1971 году Ионом Байану .

Автоматы с однократным измерением

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

Как с помощью обычного конечного автомата , квантовый автомат считается, что возможные внутренние состояния, представленные в этом случае с помощью -state кубита . Точнее, кубит -состояние - это элемент -мерного комплексного проективного пространства , несущий внутренний продукт, который является метрикой Фубини – Штуди . ${\ 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 \ раз 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 \ раз 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 \ Верт ^ {2}}$

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

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

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

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

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

пример

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

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

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

Квантовое состояние - это вектор в скобках.

${\ displaystyle | \ psi \ rangle = a_ {1} | S_ {1} \ rangle + a_ {2} | S_ {2} \ rangle = {\ begin {bmatrix} a_ {1} \\ a_ {2} \ конец {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}}}$

Как должно быть легко очевидно, если начальное состояние является чистым состоянием или , то результат работы машины будет в точности идентичен классическому детерминированному конечному автомату. В частности, этот автомат с вероятностью единица для этих начальных состояний принимает язык, который идентичен обычному языку для классического 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 году. Общая структура похожа на структуру автомата измерения один раз, за ​​исключением того, что вместо одной проекции в конце есть проекция или квантовое измерение , выполняемое после каждого письмо читается. Далее следует формальное определение.

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

${\ displaystyle {\ mathcal {H}} _ {Q} = {\ mathcal {H}} _ {\ text {accept}} \ oplus {\ mathcal {H}} _ {\ text {reject}} \ oplus { \ mathcal {H}} _ {\ text {без остановки}}}$

В литературе эти ортогональные подпространства обычно формулируются в терминах набора ортогональных базисных векторов для гильбертова пространства . Этот набор базисных векторов делится на подмножества и , так что ${\ 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 {отклонить}}}$${\ displaystyle {\ mathcal {H}} _ {\ text {без остановки}}}$

${\ 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 р _ {\ альфа} (х)}$${\ displaystyle U _ {\ alpha}}$

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

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

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

Приведенные выше конструкции показывают, как понятие квантового конечного автомата может быть обобщено на произвольные топологические пространства . Например, можно взять какое-нибудь ( N -мерное) симметрическое пространство Римана вместо . Вместо унитарных матриц используются изометрии риманова многообразия или, в более общем смысле, некоторый набор открытых функций, соответствующих данному топологическому пространству. Исходное состояние можно принять за точку в пространстве. Множество допустимых состояний можно принять как произвольное подмножество топологического пространства. Затем говорят, что формальный язык принимается этим топологическим автоматом, если точка после итерации гомеоморфизмами пересекает принимаемое множество. Но, конечно, это не более чем стандартное определение М-автомата . Поведение топологических автоматов изучается в области топологической динамики . ${\ 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}}$

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

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

Ноты