Квантовая теория сложности - Quantum complexity theory

Теория квантовой сложности - это подполе теории сложности вычислений, которая имеет дело с классами сложности, определенными с помощью квантовых компьютеров , вычислительной модели, основанной на квантовой механике . Он изучает сложность вычислительных задач по отношению к этим классам сложности, а также взаимосвязь между классами квантовой сложности и классическими (т. Е. Неквантовыми) классами сложности.

Два важных класса квантовой сложности - это BQP и QMA .

Фон

Класс сложности представляет собой совокупность вычислительных задач , которые могут быть решены с помощью расчетной модели при определенных ресурсных ограничениях. Например, класс сложности P определяется как набор задач, решаемых машиной Тьюринга за полиномиальное время . Точно так же классы квантовой сложности могут быть определены с использованием квантовых моделей вычислений, таких как модель квантовой схемы или эквивалентная квантовая машина Тьюринга . Одна из основных целей теории квантовой сложности - выяснить, как эти классы соотносятся с классическими классами сложности, такими как P , NP , BPP и PSPACE .

Одна из причин, по которой изучается теория квантовой сложности, - это последствия квантовых вычислений для современного тезиса Черча-Тьюринга . Короче говоря, современный тезис Черча-Тьюринга утверждает, что любую вычислительную модель можно смоделировать за полиномиальное время с помощью вероятностной машины Тьюринга . Однако вопросы вокруг тезиса Черча-Тьюринга возникают в контексте квантовых вычислений. Неясно, верен ли тезис Черча-Тьюринга для модели квантовых вычислений. Есть много свидетельств того, что этот тезис не верен. Возможно, вероятностная машина Тьюринга не сможет моделировать модели квантовых вычислений за полиномиальное время.

Как квантовая вычислительная сложность функций, так и классическая вычислительная сложность функций часто выражаются с помощью асимптотических обозначений . Некоторые распространенные формы асимптотического понятия функций , и . Выражает что что - то ограничена сверху , где константа такая , что и является функцией , выражает то , что ограничена снизу , где это константа, что и является функцией , и выражает оба и . Эти обозначения также имеют собственные названия. называется Big O нотации , называется Big Omega нотации, и называется Big Theta нотации.

Обзор классов сложности

Некоторые важные классы сложности - P, BPP, BQP, PP и P-Space. Чтобы определить их, мы сначала определяем проблему обещания. Проблема обещания - это проблема решения, в которой предполагается, что вход выбран из набора всех возможных входных строк. Проблема с обещанием - это пара . - это набор экземпляров yes, это набор экземпляров no, и пересечение этих наборов таково, что . Все предыдущие классы сложности содержат проблемы с обещаниями.

Класс сложности Критерии
п Обещать задачи, для которых детерминированная машина Тьюринга с полиномиальным временем принимает все строки в и отклоняет все строки в
BPP Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую строку с вероятностью не менее , и принимает каждую строку с вероятностью не более
BQP Обещайте такие задачи, что для функций существует генерируемое за полиномиальное время семейство квантовых схем , где - схема, которая принимает кубиты и выдает на выходе один кубит. Элемент из принят с вероятностью больше или равной . Элемент из принят с вероятностью меньше или равной .
ПП Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую входящую строку с вероятностью больше, чем , и принимает каждую строку с вероятностью не более
P-SPACE Обещать задачи, для которых детерминированная машина Тьюринга, работающая в полиномиальном пространстве, принимает каждую строку в и отклоняет все строки в

BQP

Алгоритм BQP (1 запуск)
Отвечать
произвел
Правильный
ответ
да Нет
да ≥ 2/3 ≤ 1/3
Нет ≤ 1/3 ≥ 2/3
Предполагаемая связь BQP с другими классами сложности.

Класс задач, которые могут быть эффективно решены квантовым компьютером с ограниченной ошибкой, называется BQP («ограниченная ошибка, квант, полиномиальное время»). Более формально BQP - это класс задач, которые могут быть решены с помощью квантовой машины Тьюринга с полиномиальным временем с вероятностью ошибки не более 1/3.

Как класс вероятностных задач, BQP является квантовым аналогом BPP («ограниченная ошибка, вероятностное, полиномиальное время»), класса задач, которые могут быть эффективно решены вероятностными машинами Тьюринга с ограниченной ошибкой. Известно, что BPP и BQP широко подозревали, но не доказали, что BQP BPP, что интуитивно означало бы, что квантовые компьютеры более мощные, чем классические компьютеры, с точки зрения временной сложности. BQP - это подмножество PP .

Точная связь BQP с P , NP и PSPACE неизвестна. Однако известно, что P BQP PSPACE; то есть класс проблем, которые могут быть эффективно решены с помощью квантовых компьютеров, включает все проблемы, которые могут быть эффективно решены с помощью детерминированных классических компьютеров, но не включает никаких проблем, которые не могут быть решены классическими компьютерами с полиномиальными пространственными ресурсами. Кроме того, предполагается, что BQP является строгим надмножеством P, что означает, что есть проблемы, которые эффективно решаются квантовыми компьютерами, но не решаются с помощью детерминированных классических компьютеров. Например, известно, что целочисленная факторизация и проблема дискретного логарифмирования находятся в BQP и предположительно находятся за пределами P.О связи BQP с NP мало что известно, кроме того факта, что некоторые проблемы NP находятся в BQP (целочисленная факторизация и проблема дискретного логарифмирования находится в NP, например). Есть подозрение, что НП BQP; то есть считается, что существуют эффективно проверяемые проблемы, которые не могут эффективно решить квантовый компьютер. Как прямое следствие этого убеждения, есть также подозрение, что BQP не пересекается с классом NP-полных задач (если какая-либо NP-полная проблема была в BQP, то из NP-сложности следует, что все проблемы в NP находятся в BQP ).

Связь BQP с основными классами сложности можно резюмировать следующим образом:

Также известно, что BQP содержится в классе сложности #P (или, точнее, в ассоциированном классе задач решения P #P ), который является подмножеством PSPACE .

Моделирование квантовых схем

Нет известного способа эффективно моделировать квантовую вычислительную модель с помощью классического компьютера. Это означает, что классический компьютер не может моделировать квантовую вычислительную модель за полиномиальное время. Тем не менее, квантовая схема из кубитов с квантовыми воротами может быть смоделирована с помощью классической схемы с классическими воротами . Это количество классических вентилей получается путем определения количества битовых операций, необходимых для моделирования квантовой схемы. Для этого сначала необходимо учесть амплитуды, связанные с кубитами. Каждое из состояний кубитов можно описать двумерным комплексным вектором или вектором состояния. Эти векторы состояния также можно описать линейной комбинацией составляющих его векторов с коэффициентами, называемыми амплитудами. Эти амплитуды представляют собой комплексные числа, нормированные на единицу, что означает, что сумма квадратов абсолютных значений амплитуд должна быть равна единице. Этими амплитудами являются элементы вектора состояния. Какая запись каждая из амплитуд соответствует ненулевой компоненте вектора компонентов, коэффициентами которого они являются в описании линейной комбинации. Как уравнение это описывается как или с использованием обозначений Дирака . Состояние всей системы кубитов можно описать одним вектором состояния. Этот вектор состояния, описывающий всю систему, является тензорным произведением векторов состояния, описывающих отдельные кубиты в системе. Результатом тензорных произведений кубитов является единственный вектор состояния, который имеет размеры и элементы, которые являются амплитудами, связанными с каждым базисным состоянием или вектором компонента. Следовательно, амплитуды должны учитываться с помощью размерного комплексного вектора, который является вектором состояния для системы кубитов. Чтобы получить верхнюю границу количества вентилей, необходимых для моделирования квантовой схемы, нам нужна достаточная верхняя граница для количества данных, используемых для определения информации о каждой из амплитуд. Для этого достаточно битов точности для кодирования каждой амплитуды. Таким образом, для учета вектора состояния системы кубитов нужны классические биты . Далее необходимо учесть применение квантовых вентилей к амплитудам. Квантовые вентили можно представить в виде разреженных матриц . Таким образом, чтобы учесть применение каждого из квантовых вентилей, вектор состояния должен быть умножен на разреженную матрицу для каждого из квантовых вентилей. Каждый раз, когда вектор состояния умножается на разреженную матрицу, должны выполняться арифметические операции. Следовательно, есть битовые операции для каждого квантового логического элемента, применяемого к вектору состояния. Итак, классический вентиль необходим для моделирования схемы кубита с одним квантовым вентилем. Следовательно, классические вентили необходимы для моделирования квантовой схемы кубитов с квантовыми вентилями. Хотя не существует известного способа эффективного моделирования квантового компьютера с помощью классического компьютера, можно эффективно смоделировать классический компьютер с помощью квантового компьютера. Это видно из убеждения, что .

Квантовая сложность запроса

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

Модели запросов ориентированных графов

Одним из типов проблем, которые могут облегчить решения квантовые вычисления, являются проблемы с графами. Если мы хотим рассмотреть количество запросов к графу, которые требуются для решения данной проблемы, давайте сначала рассмотрим наиболее распространенные типы графов, называемые ориентированными графами , которые связаны с этим типом вычислительного моделирования. Короче говоря, ориентированные графы - это графы, в которых все ребра между вершинами однонаправлены. Направленные графы формально определяются как граф , где N - это набор вершин или узлов, а E - набор ребер.

Модель матрицы смежности

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

Модель массива смежности

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

Квантовая сложность запросов для некоторых типов задач с графами

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

Квантовая сложность запросов для некоторых типов задач с графами
Проблема Матричная модель Модель массива
Минимальное остовное дерево
Связь
Сильная связь ,
Кратчайший путь от одного источника , ,

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

Другие типы квантовых вычислительных запросов

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

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

Алгоритм Гровера

Примером, демонстрирующим мощь квантовых вычислений, является алгоритм Гровера для поиска в неструктурированных базах данных. Сложность квантового запроса алгоритма является квадратичным улучшением по сравнению с наилучшей возможной сложностью классического запроса , который представляет собой линейный поиск . Алгоритм Гровера асимптотически оптимален ; фактически, он использует не более чем на долю больше запросов, чем лучший из возможных алгоритмов.

Алгоритм Дойча-Йозса

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

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

Примечания

использованная литература

внешние ссылки