Квантовая теория сложности

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

Двумя важными классами квантовой сложности являются BQP и QMA .

Фон

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

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

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

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

Важные классы сложности P, BPP, BQP, PP и PSPACE можно сравнить на основе задач обещания . Проблема обещания — это проблема принятия решения, в которой предполагается, что входные данные выбираются из набора всех возможных входных строк. Проблема промиса — это пара , где — набор экземпляров «да» и — набор «нет экземпляров», а пересечение этих наборов пусто: . Все предыдущие классы сложности содержат проблемы обещаний. ^[4] $A=(A_{\text{да}},A_{\text{нет}})$ $A_{\text{да}}$ $A_{\text{нет}}$ $A_{\text{да}}\cap A_{\text{no}}=\varnothing$

БКП

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

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

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

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

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

Также известно, что BQP содержится в классе сложности (или точнее в ассоциированном классе задач решения ), ^[8] который является подмножеством PSPACE . $\color {Blue}{\mathsf {\#P}}$ ${\mathsf {P^{\#P}}}$

Моделирование квантовых цепей

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

Сложность квантового запроса

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

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

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

Матричная модель смежности

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Дойча-Йожы

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

Другие теории квантовой физики

Было высказано предположение, что дальнейшие достижения в физике могут привести к созданию еще более быстрых компьютеров. Например, было показано, что нелокальный квантовый компьютер со скрытыми переменными, основанный на механике Бома , может реализовать поиск в базе данных $из N$ элементов за большинство шагов, что является небольшим ускорением по сравнению с алгоритмом Гровера , который выполняется поэтапно . Однако обратите внимание, что ни один из методов поиска не позволит квантовым компьютерам решать NP-полные задачи за полиномиальное время. ^[13] Теории квантовой гравитации , такие как М-теория и петлевая квантовая гравитация , могут позволить создать еще более быстрые компьютеры. Однако определение вычислений в этих теориях является открытой проблемой из-за проблемы времени ; то есть в рамках этих физических теорий в настоящее время нет очевидного способа описать, что значит для наблюдателя отправлять входные данные в компьютер в один момент времени, а затем получать выходные данные в более поздний момент времени. ^[14]^[15] $O({\sqrt[{3}]{N}})$ $O({\sqrt {N}})$

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

Примечания

^ аб Вазирани, Умеш В. (2002). «Обзор квантовой теории сложности». Материалы симпозиумов по прикладной математике . 58 : 193–217. дои : 10.1090/psapm/058/1922899. ISBN 9780821820841. ISSN 2324-7088.
^ abcd Nielsen, Майкл А., 1974- (2010). Квантовые вычисления и квантовая информация. Чуанг, Исаак Л., 1968- (изд. к 10-летию). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3. ОСЛК 665137861.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ abcdefg Клив, Ричард (2000), «Введение в квантовую теорию сложности», Квантовые вычисления и квантовая теория информации , WORLD SCIENTIFIC, стр. 103–127, arXiv : quant-ph/9906111 , Bibcode : 2000qcqi.book..103C , doi : 10.1142/9789810248185_0004, ISBN 978-981-02-4117-9, S2CID 958695 , получено 10 октября 2020 г.
^ abcdefg Уотрус, Джон (21 апреля 2008 г.). «Квантовая вычислительная сложность». arXiv : 0804.3401 [квант-ph].
^ Нильсен, с. 42
^ Нильсен, Майкл ; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета. п. 41. ИСБН 978-0-521-63503-5. ОКЛК 174527496.
^ Нильсен, с. 201
^ аб Бернштейн, Итан; Вазирани, Умеш (1997). «Квантовая теория сложности». SIAM Journal по вычислительной технике . 26 (5): 1411–1473. CiteSeerX 10.1.1.144.7852 . дои : 10.1137/S0097539796300921.
^ Ханер, Томас; Штайгер, Дамиан С. (12 ноября 2017 г.). «0,5-петабайтное моделирование 45-кубитной квантовой схемы». Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 1–10. arXiv : 1704.01127 . дои : 10.1145/3126908.3126947. ISBN 978-1-4503-5114-0. S2CID 3338733.
^ Найкамп, DQ «Определение ориентированного графа».
^ abc Дурр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Сложность квантовых запросов некоторых задач на графах». SIAM Journal по вычислительной технике . 35 (6): 1310–1328. arXiv : Quant-ph/0401091 . дои : 10.1137/050644719. ISSN 0097-5397. S2CID 27736397.
^ Залка, Кристоф (1 октября 1999 г.). «Алгоритм квантового поиска Гровера оптимален». Физический обзор А. 60 (4): 2746–2751. arXiv : Quant-ph/9711070 . Бибкод : 1999PhRvA..60.2746Z. doi : 10.1103/PhysRevA.60.2746. S2CID 1542077.
^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .
^ Ааронсон, Скотт (2005). «NP-полные проблемы и физическая реальность». Новости ACM SIGACT . 2005 . arXiv : Quant-ph/0502072 . Бибкод : 2005quant.ph..2072A.См. раздел 7 «Квантовая гравитация». ] позвольте мне смиренно предложить следующее: можете ли вы определить полиномиальное время квантовой гравитации? [...] до тех пор, пока мы не сможем сказать, что значит для «пользователя» указать «входные данные» и «позже» получить «выходные данные» — такой вещи, как вычисления, не существует, даже теоретически ». (курсив в оригинале)
^ «D-Wave Systems продает свою первую систему квантовых вычислений корпорации Lockheed Martin» . D-Волна. 25 мая 2011 г. Архивировано из оригинала 22 декабря 2020 г. . Проверено 30 мая 2011 г.

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

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