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

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

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

Фон

Смотрите также: Вычислительная сложность и Класс сложности

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

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

Как квантовая вычислительная сложность функций, так и классическая вычислительная сложность функций часто выражаются с помощью асимптотическая запись. Некоторые общие формы асимптотических понятий функций: ${\displaystyle O(T(n))}$, ${\displaystyle \Omega (T(n))}$, и ${\displaystyle \Theta (T(n))}$. ${\displaystyle O(T(n))}$ выражает, что что-то ограничено сверху ${\displaystyle cT(n)}$ куда ${\displaystyle c}$ константа такая, что ${\displaystyle c>0}$ и ${\displaystyle T(n)}$ является функцией ${\displaystyle n}$, ${\displaystyle \Omega (T(n))}$ выражает, что что-то ограничено снизу ${\displaystyle cT(n)}$ куда ${\displaystyle c}$ константа такая, что ${\displaystyle c>0}$ и ${\displaystyle T(n)}$ является функцией ${\displaystyle n}$, и ${\displaystyle \Theta (T(n))}$ выражает оба ${\displaystyle O(T(n))}$ и ${\displaystyle \Omega (T(n))}$.^[3] Эти обозначения также имеют собственные имена. ${\displaystyle O(T(n))}$ называется Обозначение Big O, ${\displaystyle \Omega (T(n))}$ называется нотацией Big Omega, и ${\displaystyle \Theta (T(n))}$ называется нотацией Big Theta.

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

Некоторые важные классы сложности: P, BPP, BQP, PP и P-Space. Чтобы определить их, мы сначала определяем проблему обещания. Проблема обещания - это проблема решения, в которой предполагается, что вход выбран из набора всех возможных входных строк. Проблема с обещанием - это пара ${\displaystyle A=(A_{yes},A_{no})}$. ${\displaystyle A_{yes}}$ это набор экземпляров yes, ${\displaystyle A_{no}}$ - это множество без экземпляров, и пересечение этих множеств таково, что ${\displaystyle A_{yes}\cap A_{no}=\emptyset }$. Все предыдущие классы сложности содержат проблемы с обещаниями.^[4]

Класс сложности	Критерии
п	Обещать задачи, для которых детерминированная машина Тьюринга с полиномиальным временем принимает все строки в ${\displaystyle A_{yes}}$ и отклоняет все строки в ${\displaystyle A_{no}}$[4]
BPP	Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую строку в ${\displaystyle A_{yes}}$ с вероятностью не менее ${\displaystyle {\frac {2}{3}}}$, и принимает каждую строку в ${\displaystyle A_{no}}$ с вероятностью не более ${\displaystyle {\frac {1}{3}}}$[4]
BQP	Обещайте такие проблемы, что для функций ${\displaystyle a,b:\mathbb {N} \rightarrow [0,1]}$существует порожденное полиномиальным временем семейство квантовых схем ${\displaystyle Q={\{Q_{n}:n\in \mathbb {N} \}}}$, куда ${\displaystyle Q_{n}}$ это схема, которая принимает ${\displaystyle n}$ кубитов и дает на выходе один кубит. Элемент ${\displaystyle x}$ из ${\displaystyle A_{yes}}$ принимается ${\displaystyle Q}$ с вероятностью больше или равной ${\displaystyle a(\left\vert x\right\vert )}$. Элемент ${\displaystyle x}$ из ${\displaystyle A_{no}}$ принимается ${\displaystyle Q}$ с вероятностью меньше или равной ${\displaystyle b(\left\vert x\right\vert )}$.[4]
PP	Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую строку в ${\displaystyle A_{yes}}$ с вероятностью больше, чем ${\displaystyle {\frac {1}{2}}}$, и принимает каждую строку в ${\displaystyle A_{no}}$ с вероятностью не более ${\displaystyle {\frac {1}{2}}}$[4]
P-SPACE	Обещайте задачи, для которых детерминированная машина Тьюринга, работающая в полиномиальном пространстве, принимает каждую строку в ${\displaystyle A_{yes}}$ и отклоняет все строки в ${\displaystyle A_{no}}$[4]

BQP

Основная статья: BQP

Алгоритм BQP (1 запуск)

Отвечать произведено Правильный отвечать	да	Нет
да	≥ 2/3	≤ 1/3
Нет	≤ 1/3	≥ 2/3

Предполагаемая связь BQP с другими классами сложности.^[5]

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

Как класс вероятностных задач BQP является квантовым аналогом BPP («ограниченная ошибка, вероятностное, полиномиальное время»), класс задач, которые могут быть эффективно решены с помощью вероятностные машины Тьюринга с ограниченной ошибкой.^[6] Известно, что БПП${\displaystyle \subseteq }$BQP и многие подозревают, но не доказали, что BQP${\displaystyle \nsubseteq }$BPP, что интуитивно означало бы, что квантовые компьютеры более мощные, чем классические, с точки зрения временной сложности.^[7] BQP - это подмножество PP.

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

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

${\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}}$

Также известно, что BQP содержится в классе сложности #П (или, точнее, в соответствующем классе задач принятия решений п^#П),^[8] который является подмножеством PSPACE.

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

Нет известного способа эффективно моделировать квантовую вычислительную модель с помощью классического компьютера. Это означает, что классический компьютер не может моделировать квантовую вычислительную модель за полиномиальное время. Однако квантовая схема из ${\displaystyle S(n)}$ кубиты с ${\displaystyle T(n)}$ квантовые вентили можно моделировать классической схемой с ${\displaystyle O(2^{S(n)}T(n)^{3})}$ классические ворота.^[3] Это количество классических вентилей получается путем определения количества битовых операций, необходимых для моделирования квантовой схемы. Для этого сначала амплитуды, связанные с ${\displaystyle S(n)}$ кубиты необходимо учитывать. Каждое из состояний ${\displaystyle S(n)}$ кубиты могут быть описаны двумерным комплексным вектором или вектором состояния. Эти векторы состояния также можно описать как линейная комбинация своего составляющие векторы с коэффициентами, называемыми амплитудами. Эти амплитуды представляют собой комплексные числа, нормированные на единицу, что означает, что сумма квадратов абсолютных значений амплитуд должна быть равна единице.^[3] Этими амплитудами являются элементы вектора состояния. Какая запись каждая из амплитуд соответствует ненулевой компоненте вектора компонента, коэффициентами которого они являются в описании линейной комбинации. В виде уравнения это описывается как ${\displaystyle \alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$ или же ${\displaystyle \alpha \left\vert 1\right\rangle +\beta \left\vert 0\right\rangle ={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$ с помощью Обозначение Дирака. Состояние всего ${\displaystyle S(n)}$ Система кубитов может быть описана одним вектором состояния. Этот вектор состояния, описывающий всю систему, является тензорным произведением векторов состояния, описывающих отдельные кубиты в системе. Результат тензорных произведений ${\displaystyle S(n)}$ кубиты - это единственный вектор состояния, который имеет ${\displaystyle 2^{S(n)}}$ размеры и записи, которые представляют собой амплитуды, связанные с каждым базисным состоянием или вектором компонента. Следовательно, ${\displaystyle 2^{S(n)}}$амплитуды должны учитываться ${\displaystyle 2^{S(n)}}$ размерный комплексный вектор, который является вектором состояния для ${\displaystyle S(n)}$ система кубитов.^[9] Чтобы получить верхнюю границу количества вентилей, необходимых для моделирования квантовой схемы, нам нужна достаточная верхняя граница для количества данных, используемых для определения информации о каждом из ${\displaystyle 2^{S(n)}}$ амплитуды. Сделать это ${\displaystyle O(T(n))}$ бит точности достаточно для кодирования каждой амплитуды.^[3] Так что это требует ${\displaystyle O(2^{S(n)}T(n))}$ классические биты для учета вектора состояния ${\displaystyle S(n)}$ система кубитов. Далее приложение ${\displaystyle T(n)}$ квантовые ворота на ${\displaystyle 2^{S(n)}}$ амплитуды должны быть учтены. Квантовые ворота можно представить в виде ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ разреженные матрицы.^[3] Итак, чтобы учесть применение каждого из ${\displaystyle T(n)}$ квантовых вентилей, вектор состояния необходимо умножить на ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ разреженная матрица для каждого из ${\displaystyle T(n)}$ квантовые ворота. Каждый раз, когда вектор состояния умножается на ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ разреженная матрица, ${\displaystyle O(2^{S(n)})}$ арифметические операции должны быть выполнены.^[3] Следовательно, есть ${\displaystyle O(2^{S(n)}T(n)^{2})}$ битовые операции для каждого квантового вентиля, применяемого к вектору состояния. Так ${\displaystyle O(2^{S(n)}T(n)^{2})}$ классические ворота необходимы для моделирования ${\displaystyle S(n)}$ схема кубита с одним квантовым вентилем. Следовательно, ${\displaystyle O(2^{S(n)}T(n)^{3})}$ классические вентили необходимы для моделирования квантовой схемы ${\displaystyle S(n)}$ кубиты с ${\displaystyle T(n)}$ квантовые ворота.^[3] Хотя нет известного способа эффективно моделировать квантовый компьютер с помощью классического компьютера, можно эффективно моделировать классический компьютер с помощью квантового компьютера. Это очевидно из убеждения, что ${\displaystyle BBP\subseteq BQP}$.^[4]

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

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

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

Одним из типов проблем, которые могут облегчить решения квантовые вычисления, являются проблемы с графами. Если мы хотим рассмотреть количество запросов к графу, которые требуются для решения данной проблемы, давайте сначала рассмотрим наиболее распространенные типы графов, называемые ориентированные графы, связанные с этим типом вычислительного моделирования. Вкратце, ориентированные графы - это графы, в которых все ребра между вершинами однонаправлены. Направленные графы формально определяются как граф ${\displaystyle G=(N,E)}$, где N - множество вершин или узлов, а E - множество ребер.^[10]

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

При рассмотрении квантового вычисления решения задач ориентированного ориентированного графа необходимо понимать две важные модели запросов. Во-первых, это модель матрицы смежности, в которой график решения задается матрицей смежности: ${\displaystyle M\in \{0,1\}a^{n\mathrm {X} n}}$, с ${\displaystyle M_{ij}=1}$, если и только если ${\displaystyle (v_{i},v_{j})\in E}$.^[11]

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

Далее следует несколько более сложная модель массива смежности, построенная на идее списки смежности, где каждая вершина, ${\displaystyle u}$, связан с массивом соседних вершин, таких что ${\displaystyle f_{i}:[d_{i}^{+}]\rightarrow [n]}$, для внешних степеней вершин ${\displaystyle d_{i}^{+},...,d_{n}^{+}}$, куда ${\displaystyle n}$ - минимальное значение верхней границы этой модели, а ${\displaystyle f_{i}(j)}$ возвращает "${\displaystyle j^{th}}$"вершина, смежная с ${\displaystyle i}$. Кроме того, модель массива смежности удовлетворяет условию простого графа, ${\displaystyle \forall i\in [n],j,j^{'}\in [k],j\neq j^{'}:f_{i}(j)\neq f_{i}(j^{'})}$, что означает, что между любой парой вершин есть только одно ребро, а количество ребер минимизировано по всей модели (см. Остовное дерево модель для получения дополнительной информации).^[11]

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

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

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

Проблема	Матричная модель	Модель массива
Минимальное связующее дерево	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Theta ({\sqrt {nm}})}$
Связь	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Theta (n)}$
Сильная связь	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Omega ({\sqrt {nm}})}$, ${\displaystyle O({\sqrt {nmlog(n)}})}$
Кратчайший путь от одного источника	${\displaystyle \Omega (n^{3/2})}$, ${\displaystyle O(n^{3/2}log^{2}n)}$	${\displaystyle \Omega ({\sqrt {nm}})}$, ${\displaystyle O({\sqrt {nm}}log^{2}(n))}$

Обратите внимание на несоответствие между сложностями квантовых запросов, связанных с конкретным типом проблемы, в зависимости от того, какая модель запроса использовалась для определения сложности. Например, когда используется матричная модель, квантовая сложность модели связности в Обозначение Big O является ${\displaystyle \Theta (n^{3/2})}$, но когда используется модель массива, сложность ${\displaystyle \Theta (n)}$. Дополнительно для краткости мы используем сокращение ${\displaystyle m}$ в некоторых случаях, когда ${\displaystyle m=\Theta (n^{2})}$.^[11] Важным выводом здесь является то, что эффективность алгоритма, используемого для решения задачи построения графика, зависит от типа модели запроса, используемой для моделирования графа.

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

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

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

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

Пример, демонстрирующий возможности квантовых вычислений: Алгоритм Гровера для поиска в неструктурированных базах данных. Сложность квантового запроса алгоритма составляет ${\textstyle O{\left({\sqrt {N}}\right)}}$, квадратичное улучшение наилучшей возможной классической сложности запроса ${\displaystyle O(N)}$, что является линейный поиск. Хотя алгоритм Гровера более оптимизирован, чем лучший из возможных классический алгоритм, мы знаем, что алгоритм Гровера не является оптимальным на сто процентов.^[12] Оптимизация алгоритма запроса относится к тому, как алгоритм сравнивается с наиболее эффективным теоретическим алгоритмом, который решает ту же проблему. Алгоритм называется асимптотически оптимизированный в худшем случае он работает с постоянным коэффициентом хуже, чем наиболее эффективный из возможных алгоритмов. Обратите внимание, что алгоритм по-прежнему считается оптимизированным, если он работает хуже, чем наиболее эффективный из возможных алгоритмов, при условии, что алгоритм не становится экспоненциально хуже, чем наиболее эффективный из возможных алгоритмов, по мере увеличения количества входов.

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

Алгоритм Дойча-Йозса - это квантовый алгоритм, разработанный для решения игрушечной задачи с меньшей сложностью запроса, чем это возможно с классическим алгоритмом. Задача с игрушкой спрашивает, может ли функция ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$ является постоянным или сбалансированным, это единственные две возможности.^[2] Единственный способ оценить функцию ${\displaystyle f}$ проконсультироваться с черный ящик или же оракул. Классический детерминированный алгоритм необходимо будет проверить более половины возможных входов, чтобы убедиться, является ли функция постоянной или сбалансированной. С ${\displaystyle 2^{n}}$ возможных входов сложность запроса наиболее эффективного классического детерминированного алгоритма равна ${\displaystyle 2^{n-1}+1}$.^[2] Алгоритм Дойча-Йозса использует преимущества квантового параллелизма для одновременной проверки всех элементов домена и требует только один раз запросить оракул. Это означает, что сложность запроса алгоритма Дойча-Йозса равна ${\displaystyle 1}$.^[2]

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

• Квантовые вычисления
• Квантовая машина Тьюринга
• Полиномиальная иерархия (PH)

Примечания

1. Вазирани, Умеш В. (2002). «Обзор квантовой теории сложности». Материалы симпозиумов по прикладной математике. 58: 193–217. Дои:10.1090 / psapm / 058/1922899. ISBN  9780821820841. ISSN  2324-7088.
2. Нильсен, Майкл А., 1974- (2010). Квантовые вычисления и квантовая информация. Чуанг, Исаак Л., 1968- (10-летие изд.). Кембридж: Издательство Кембриджского университета. ISBN  978-1-107-00217-3. OCLC  665137861.
3. Клив, Ричард (2000), «Введение в теорию квантовой сложности», Квантовые вычисления и квантовая теория информации, МИРОВАЯ НАУЧНАЯ, стр. 103–127, arXiv:Quant-ph / 9906111, Bibcode:2000qcqi.book..103C, Дои:10.1142/9789810248185_0004, ISBN  978-981-02-4117-9, S2CID  958695, получено 10 октября, 2020
4. Уотроус, Джон (2008-04-21). «Квантовая вычислительная сложность». arXiv: 0804.3401 [квант-ф]. arXiv:0804.3401.
5. Нильсен, стр. 42
6. Нильсен, Майкл; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета. п. 41. ISBN  978-0-521-63503-5. OCLC  174527496.
7. Нильсен, стр. 201
8. Бернштейн, Итан; Вазирани, Умеш (1997). «Квантовая теория сложности». SIAM Журнал по вычислениям. 26 (5): 1411–1473. CiteSeerX  10.1.1.144.7852. Дои:10.1137 / S0097539796300921.
9. Хенер, Томас; Штайгер, Дамиан С. (12.11.2017). «Моделирование 0,5 петабайта квантовой схемы из 45 кубитов». Труды Международной конференции по высокопроизводительным вычислениям, сетям, хранилищам и анализу. Нью-Йорк, Нью-Йорк, США: ACM: 1–10. arXiv:1704.01127. Дои:10.1145/3126908.3126947. ISBN  978-1-4503-5114-0. S2CID  3338733.
10. Nykamp, ​​D.Q. «Определение ориентированного графа».
11. Дурр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Квантовая сложность запросов некоторых задач с графами». SIAM Журнал по вычислениям. 35 (6): 1310–1328. arXiv:Quant-ph / 0401091. Дои:10.1137/050644719. ISSN  0097-5397. S2CID  27736397.
12. Амбайнис, Андрис (28 октября 2005 г.). «Степень полинома против квантовой сложности запроса». Журнал компьютерных и системных наук. 72 (2): 220–238. Дои:10.1016 / j.jcss.2005.06.006.

Рекомендации

• Нильсен, Майкл; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-63503-5. OCLC  174527496.
• Арора, Санджив; Варак, Вооз (2016). Вычислительная сложность: современный подход. Издательство Кембриджского университета. стр.201 –236. ISBN  978-0-521-42426-4.
• Джон Уотроус (2008). «Квантовая вычислительная сложность». arXiv:0804.3401v1 [Quant-ph ].
• Уотроус Дж. (2009) Квантовая вычислительная сложность. В: Мейерс Р. (ред.) Энциклопедия сложности и системологии. Спрингер, Нью-Йорк, Нью-Йорк

внешняя ссылка

• Лекции MIT к Скотт Ааронсон