В квантовых вычислениях , квантовые конечные автоматы ( КФД ) или конечные автоматы квантовых представляют собой квантовый аналог вероятностных автоматов или процесс принятия Маркова . Они представляют собой математическую абстракцию реальных квантовых компьютеров . Может быть определено несколько типов автоматов, в том числе меры, когда и меру много автоматов. Квантовые конечные автоматы также можно понимать как квантование подсдвигов конечного типа или как квантование цепей Маркова . QFA, в свою очередь, являются частными случаями геометрических конечных автоматов илитопологические конечные автоматы .
Автоматы работают, получая строку конечной длины букв из конечного алфавита , и присвоив каждой такой строке вероятность индикация вероятности нахождения автомата в состоянии приема ; то есть, указывая, принял ли автомат строку или отклонил.
В языках , принятый КФД не являются регулярными языками из детерминированных конечных автоматов , и не им стохастические языки из вероятностных конечных автоматов . Изучение этих квантовых языков остается активной областью исследований.
Неформальное описание
Существует простой и интуитивно понятный способ понимания квантовых конечных автоматов. Каждый начинается с теоретико-графической интерпретации детерминированных конечных автоматов (DFA). DFA можно представить в виде ориентированного графа с состояниями в виде узлов в графе и стрелками, представляющими переходы между состояниями. Каждая стрелка помечена возможным символом ввода, так что, учитывая конкретное состояние и символ ввода, стрелка указывает на следующее состояние. Один из способов представления такого графа - это набор матриц смежности с одной матрицей для каждого входного символа. В этом случае список возможных состояний DFA записывается как вектор-столбец. Для данного входного символа матрица смежности указывает, как любое данное состояние (строка в векторе состояний) перейдет в следующее состояние; переход состояния задается умножением матриц .
Требуется отдельная матрица смежности для каждого возможного входного символа, поскольку каждый входной символ может привести к другому переходу. Записи в матрице смежности должны быть нулем и единицей. Для любого заданного столбца в матрице только одна запись может быть ненулевой: это запись, которая указывает следующий (уникальный) переход состояния. Точно так же состояние системы - это вектор-столбец, в котором только одна запись не равна нулю: эта запись соответствует текущему состоянию системы. Позволятьобозначают набор входных символов. Для заданного входного символа, написать как матрица смежности, которая описывает эволюцию DFA к его следующему состоянию. Наборзатем полностью описывает функцию перехода состояний DFA. Пусть Q представляет множество возможных состояний DFA. Если в Q есть N состояний , то каждая матрицаявляется N на N - мерный. Исходное состояниесоответствует вектору-столбцу с единицей в строке q 0 . Общее состояние q тогда представляет собой вектор-столбец с единицей в q- й строке. При злоупотреблении нотации , пусть д 0 и д и обозначим эти два вектора. Затем, после прочтения входных символов с входной ленты состояние DFA будет задано как Переходы состояний задаются обычным умножением матриц (то есть умножением q 0 наи др. ); порядок применения «обратный» только потому, что мы следуем стандартным обозначениям линейной алгебры.
Приведенное выше описание DFA в терминах линейных операторов и векторов почти требует обобщения путем замены вектора состояния q некоторым общим вектором, а матрицынекоторыми общими операторами. Это, по сути , что делает QFA: он заменяет д по амплитуде вероятности , ис помощью унитарных матриц . Становятся очевидными и другие подобные обобщения: вектор q может быть некоторым распределением на многообразии ; множество матриц перехода становятся автоморфизмами многообразия; это определяет топологический конечный автомат. Точно так же матрицы можно рассматривать как автоморфизмы однородного пространства ; это определяет геометрический конечный автомат.
Прежде чем перейти к формальному описанию QFA, следует упомянуть и понять два важных обобщения. Первый - это недетерминированный конечный автомат (NFA). В этом случае вектор q заменяется вектором, который может иметь более одной записи, отличной от нуля. Такой вектор затем представляет собой элемент силового набора из Q ; его просто индикаторная функция на Q . Аналогично, матрицы переходов состоянийопределены таким образом, что в данном столбце может быть несколько ненулевых записей. Эквивалентно, то умножения-сложения операции , выполняемые во покомпонентного матричного умножения следует заменить на булевых и-или операций, то есть так , что один работает с кольцом из характеристики 2 .
Известная теорема утверждает, что для каждого DFA существует эквивалентный NFA, и наоборот . Это означает, что набор языков, которые могут распознаваться DFA и NFA, одинаков; это обычные языки . В обобщении QFA набор распознаваемых языков будет другим. Описание этого множества - одна из важнейших исследовательских задач теории QFA.
Другое обобщение, которое должно быть сразу очевидным, - это использование стохастической матрицы для матриц перехода и вектора вероятности для состояния; это дает вероятностный конечный автомат . Записи в векторе состояния должны быть действительными числами, положительными и суммой равными единице, чтобы вектор состояния интерпретировался как вероятность. Матрицы переходов должны сохранять это свойство: поэтому они должны быть стохастическими. Каждый вектор состояния следует представить как задающий точку в симплексе ; таким образом, это топологический автомат, где симплекс является многообразием, а стохастические матрицы являются линейными автоморфизмами симплекса на себя. Поскольку каждый переход (по существу) не зависит от предыдущего (если не принимать во внимание различие между принятыми и отклоненными языками), PFA по сути становится своего рода цепью Маркова .
Напротив, в QFA многообразие является комплексным проективным пространством , а матрицы перехода - унитарные матрицы. Каждая точка всоответствует квантово-механической амплитуде вероятности или чистому состоянию ; унитарные матрицы можно рассматривать как управляющие эволюцией системы во времени (а именно, в картине Шредингера ). Обобщение от чистых состояний к смешанным должно быть простым: смешанное состояние - это просто теоретико- мерное распределение вероятностей на.
Стоит задуматься о распределениях, которые возникают на многообразии во время ввода языка. Чтобы автомат мог «эффективно» распознавать язык, это распределение должно быть «как можно более равномерным». Эта потребность в единообразии является основным принципом, лежащим в основе методов максимальной энтропии : они просто гарантируют четкую и компактную работу автомата. Помещенный другими словами, в машинном обучении методы , используемые для обучения скрытых марковских моделей обобщаются КФД , а также: в алгоритм Витерби и вперед-назад алгоритм обобщают с готовностью к КФД.
Хотя исследование QFA было популяризировано в работах Кондакса и Уотроуса в 1997 году [1], а затем Муром и Кратчфельдом [2], они были описаны еще в 1971 году Ионом Байану . [3] [4]
Автоматы с однократным измерением
Автоматы с однократным измерением были представлены Крисом Муром и Джеймсом П. Кратчфилдом . [2] Формально их можно определить следующим образом.
Как и в случае с обычным конечным автоматом , квантовый автомат считается имеющим возможные внутренние состояния, представленные в данном случае -состояние кубита . Точнее,-состояние кубита является элементом -мерное сложное проективное пространство , несущее внутренний продукт это метрика Фубини – Штуди .
Переходы состояний , матрицы переходов или графы де Брейна представлены набором унитарные матрицы , с одной унитарной матрицей для каждой буквы . То есть при вводе буквы, унитарная матрица описывает переход автомата из текущего состояния в его следующее состояние :
Таким образом, тройная образуют квантовый полуавтомат .
Принимает состояние автомата задается матрица проекции , так что, учитывая -мерное квантовое состояние , вероятность находиться в состоянии принятия - это
Вероятность того, что конечный автомат примет заданную конечную входную строку дан кем-то
Здесь вектор Подразумевается, что оно представляет начальное состояние автомата, то есть состояние, в котором автомат находился до того, как начал принимать ввод строки. Пустая строка понимается как единичная матрица, так что
это просто вероятность того, что начальное состояние будет принятым.
Поскольку левое действие на меняет порядок букв в строке на обратный , нередко QFA определяются с использованием правильного действия над эрмитовыми состояниями транспонирования просто для того, чтобы сохранить порядок букв одинаковым.
Регулярный язык принимается с вероятностью квантовым конечным автоматом, если для всех предложений на языке (и заданном фиксированном начальном состоянии ), надо .
Пример
Рассмотрим классический детерминированный конечный автомат, заданный таблицей переходов состояний
| Диаграмма состояния |
Квантовое состояние - это вектор в скобках.
с комплексными числами нормализовано так, чтобы
Матрицы унитарных переходов:
а также
Принимая чтобы быть состоянием принятия, матрица проекции
Как должно быть легко очевидно, если начальное состояние - чистое состояние или же , то результат запуска машины будет в точности идентичен классическому детерминированному конечному автомату. В частности, существует язык, принимаемый этим автоматом с вероятностью единица для этих начальных состояний, и он идентичен обычному языку для классического DFA и задается регулярным выражением :
Неклассическое поведение возникает, если оба а также не равны нулю. Более тонкое поведение происходит, когда матрицы а также не все так просто; см., например, кривую де Рама как пример квантового конечного автомата, действующего на множество всех возможных конечных двоичных строк.
Измерение многих автоматов
Автоматы с измерением многих были введены Кондаксом и Уотроусом в 1997 году. [1] Общая структура напоминает структуру автомата с измерением один раз, за исключением того, что вместо одной проекции в конце есть проекция, или квантовое измерение , выполняется после прочтения каждой буквы. Далее следует формальное определение.
Гильбертово пространство раскладывается на три ортогональных подпространства
В литературе эти ортогональные подпространства обычно формулируются в терминах множества ортогональных базисных векторов гильбертова пространства . Этот набор базисных векторов разделен на подмножества а также , так что
- линейная оболочка базисных векторов принятого множества. Пространство отбраковки определяется аналогично, а оставшееся пространство обозначается как непостоянное подпространство. Есть три матрицы проекции,, а также , каждое из которых проецируется на соответствующее подпространство:
и так далее. Анализ входной строки происходит следующим образом. Считаем автомат находящимся в состоянии. После прочтения входного письма, автомат будет в состоянии
На этом этапе выполняется измерение состояния , используя операторы проекции , при этом его волновая функция коллапсирует в одно из трех подпространств или же или же . Вероятность коллапса определяется выражением
для подпространства "accept", и аналогично для двух других пространств.
Если волновая функция сжалась до подпространства «принять» или «отклонить», дальнейшая обработка прекращается. В противном случае обработка продолжается со следующей буквой, считанной из ввода и примененной к тому, что должно быть собственным состоянием. Обработка продолжается до тех пор, пока не будет прочитана вся строка или пока машина не остановится. Часто дополнительные символы и $ присоединены к алфавиту, чтобы действовать как левый и правый маркеры конца строки.
В литературе автомат с числом мер часто обозначается набором . Здесь,, , а также определены выше. Начальное состояние обозначается. Унитарные преобразования обозначаются отображением,
чтобы
Отношение к квантовым вычислениям
По состоянию на 2019 год большинство квантовых компьютеров являются реализациями квантовых конечных автоматов с однократной мерой, а программные системы для их программирования предоставляют возможность подготовки состояний, измерение и выбор унитарных преобразований , такие как управляемый вентиль НЕ , преобразование Адамара и другие квантовые логические вентили , напрямую программисту.
Основное различие между реальными квантовыми компьютерами и теоретической структурой, представленной выше, заключается в том, что подготовка начального состояния никогда не может привести к точечному чистому состоянию , и унитарные операторы не могут быть точно применены. Таким образом, исходное состояние следует рассматривать как смешанное состояние.
для некоторого распределения вероятностей характеризуя способность оборудования подготовить начальное состояние, близкое к желаемому начальному чистому состоянию . Это состояние нестабильно, но со временем страдает от некоторой квантовой декогеренции . Точные измерения также невозможны, и вместо этого для описания процесса измерения используются положительные операторные меры . Наконец, каждое унитарное преобразование - это не один четко определенный квантовый логический вентиль, а скорее смесь
для некоторого распределения вероятностей описание того, насколько хорошо оборудование может произвести желаемую трансформацию .
В результате этих эффектов фактическая временная эволюция состояния не может рассматриваться как чистая точка с бесконечной точностью, управляемая последовательностью произвольно резких преобразований, а скорее как эргодический процесс или, точнее, процесс перемешивания, который только объединяет преобразования в состояние, но также размывает состояние с течением времени.
Нет квантового аналога выталкивающего автомата или стековой машины . Это связано с теоремой о запрете клонирования : нет способа сделать копию текущего состояния машины, поместить ее в стек для последующего использования, а затем вернуться к нему.
Геометрические обобщения
Приведенные выше конструкции показывают, как понятие квантового конечного автомата может быть обобщено на произвольные топологические пространства . Например, можно взять некоторое ( N -мерное) симметрическое пространство Римана вместо. Вместо унитарных матриц используются изометрии риманова многообразия или, в более общем смысле, некоторый набор открытых функций, соответствующих данному топологическому пространству. Исходное состояние можно принять за точку в пространстве. Множество допустимых состояний можно принять как произвольное подмножество топологического пространства. Затем говорят, что формальный язык принимается этим топологическим автоматом, если точка после итерации гомеоморфизмами пересекает принимаемое множество. Но, конечно, это не более чем стандартное определение М-автомата . Поведение топологических автоматов изучается в области топологической динамики .
Квантовый автомат отличается от топологического в том, что вместо двоичного результата (находится ли повторяемая точка в конечном наборе или нет?) Есть вероятность. Квантовая вероятность - это (квадрат) начального состояния, спроецированного на некоторое конечное состояние P ; это. Но эта амплитуда вероятности - это просто очень простая функция расстояния между точками. и точка в , под метрикой расстояния, задаваемой метрикой Фубини – Штуди . Напомним, квантовую вероятность принятия языка можно интерпретировать как метрику с вероятностью принятия, равной единице, если метрическое расстояние между начальным и конечным состояниями равно нулю, а в противном случае вероятность принятия меньше единицы, если метрическое расстояние не равно нулю. Таким образом, следует, что квантовый конечный автомат является лишь частным случаем геометрического или метрического автомата , гдеобобщается на некоторое метрическое пространство , а вероятностная мера заменяется простой функцией метрики на этом пространстве.
Смотрите также
- Квантовая цепь Маркова
Заметки
- ^ a b Kondacs, A .; Уотроус, Дж. (1997), "О мощности квантовых конечных автоматов", Труды 38-го ежегодного симпозиума по основам информатики , стр. 66–75 CS1 maint: обескураженный параметр ( ссылка )
- ^ a b К. Мур, Дж. Кратчфилд, «Квантовые автоматы и квантовые грамматики», « Теоретическая информатика» , 237 (2000), стр. 275-306.
- ^ И. Байнау, " Органические суперкатегории и качественная динамика систем " (1971), Бюллетень математической биофизики, 33 стр. 339-354.
- ^ I. Baianu, "Категории, функторы и теория квантовых автоматов" (1971). 4-й Международный конгресс LMPS, август-сентябрь 1971 г.