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

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

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

Предыстория [ править ]

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

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

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

Обзор классов сложности [ править ]

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


Класс сложности	Критерии
П	Задачи обещаний, для которых полиномиально детерминированная машина Тьюринга принимает все строки в $A_{\text{yes}}$ и отклоняет все строки в $A_{\text{no}}$ ^[4]
БПП	Задачи обещаний, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую строку в $A_{\text{yes}}$ с вероятностью не менее ${\frac {2}{3}}$ и принимает каждую строку в $A_{\text{no}}$ с вероятностью не более ${\frac {1}{3}}$ ^[4]
Министерство национальной обороны	Задачи обещаний такие, что для функций $a,b:\mathbb {N} \to [0,1]$ существует семейство квантовых схем, порождаемое полиномиальным временем $Q={\{Q_{n}:n\in \mathbb {N} \}}$ , где $Q_{n}$ представляет собой схему, которая принимает $n$ кубитов и дает на выходе один кубит. Элемент $x$ из $A_{\text{yes}}$ принимается $Q$ с вероятностью, большей или равной $a(\left\vert x\right\vert )$ . Элемент $x$ из $A_{\text{no}}$ принимается $Q$ с вероятностью меньше или равной $b(\left\vert x\right\vert )$ . ^[4]
ПП	Задачи обещаний, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую строку в $A_{\text{yes}}$ с вероятностью, большей, чем ${\frac {1}{2}}$ и принимает каждую строку в $A_{\text{no}}$ с вероятностью не более ${\frac {1}{2}}$ ^[4]
PSPACE	Задачи обещаний, для решения которых детерминированная машина Тьюринга, работающая в полиномиальном пространстве, принимает каждую строку в $A_{\text{yes}}$ и отклоняет все строки в $A_{\text{no}}$ ^[4]

Министерство национальной обороны [ править ]

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

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

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

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

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

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

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

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

Не существует известного способа эффективного моделирования квантовой вычислительной модели с помощью классического компьютера. Это означает, что классический компьютер не может моделировать квантовую вычислительную модель за полиномиальное время. Однако квантовая схема $S(n)$ кубиты с $T(n)$ квантовые ворота можно смоделировать классической схемой с $O(2^{S(n)}T(n)^{3})$ классические ворота . ^[3] Это количество классических вентилей получается путем определения того, сколько битовых операций необходимо для моделирования квантовой схемы. Для этого сначала необходимо определить амплитуды, связанные с $S(n)$ кубиты необходимо учитывать. Каждое из государств $S(n)$ кубиты могут быть описаны двумерным комплексным вектором или вектором состояния. Эти векторы состояния также можно описать как линейную комбинацию составляющих векторов с коэффициентами, называемыми амплитудами. Эти амплитуды представляют собой комплексные числа, нормированные к единице, то есть сумма квадратов абсолютных значений амплитуд должна быть равна единице. ^[3] Элементами вектора состояния являются эти амплитуды. Какая запись каждая из амплитуд соответствует ненулевой компоненте вектора компонентов, коэффициентами которого они являются в описании линейной комбинации. В виде уравнения это описывается как $\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)$ кубитная система. ^[9] Чтобы получить верхнюю границу количества вентилей, необходимых для моделирования квантовой схемы, нам нужна достаточная верхняя граница количества данных, используемых для указания информации о каждом из вентилей. $2^{S(n)}$ амплитуды. Чтобы сделать это $O(T(n))$ бит точности достаточно для кодирования каждой амплитуды. ^[3] Так что это занимает $O(2^{S(n)}T(n))$ классические биты для учета вектора состояния $S(n)$ кубитная система. Далее применение $T(n)$ квантовые ворота включены $2^{S(n)}$ необходимо учитывать амплитуды. Квантовые ворота можно представить как $2^{S(n)}\times 2^{S(n)}$ разреженные матрицы . ^[3] Таким образом, чтобы учесть применение каждого из $T(n)$ квантовых вентилей, вектор состояния должен быть умножен на $2^{S(n)}\times 2^{S(n)}$ разреженная матрица для каждого из $T(n)$ квантовые ворота. Каждый раз, когда вектор состояния умножается на $2^{S(n)}\times 2^{S(n)}$ разреженная матрица, $O(2^{S(n)})$ необходимо выполнить арифметические действия. ^[3] Поэтому существуют $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)$ квантовые ворота. ^[3] Хотя не существует известного способа эффективного моделирования квантового компьютера с помощью классического компьютера, можно эффективно смоделировать классический компьютер с помощью квантового компьютера. Это видно из того, что ${\mathsf {BPP\subseteq BQP}}$ . ^[4]

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

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

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

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

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

При рассмотрении квантовых вычислений решения задач с ориентированными графами необходимо понимать две важные модели запросов. Во-первых, существует модель матрицы смежности , где график решения задается матрицей смежности: $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')$ , что означает, что между любой парой вершин есть только одно ребро, а количество ребер сведено к минимуму во всей модели ( связующего дерева ). дополнительную информацию см. в разделе Модель ^[11]

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

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

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

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

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

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

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

Алгоритм Гровера [ править ]

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

Алгоритм Германа-Йожсы [ править ]

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

Другие теории квантовой физики [ править ]

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

См. также [ править ]

Примечания [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б Вазирани, Умеш В. (2002). «Обзор квантовой теории сложности» . Материалы симпозиумов по прикладной математике . 58 : 193–217. дои : 10.1090/psapm/058/1922899 . ISBN 9780821820841 . ISSN 2324-7088 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д Нильсен, Майкл А., 1974- (2010). Квантовые вычисления и квантовая информация . Чуанг, Исаак Л., 1968- (изд. к 10-летию). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3 . OCLC 665137861 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Клив, Ричард (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 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Уотрус, Джон (21 апреля 2008 г.). «Квантовая вычислительная сложность». arXiv : 0804.3401 [ квант-ph ].
^ Нильсен, стр. 42.
^ Нильсен, Майкл ; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. п. 41. ИСБН 978-0-521-63503-5 . OCLC 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 «Определение ориентированного графа» .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Дурр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 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 . дои : 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 г.

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[:02-1] Перейти обратно: Перейти обратно: ^а ^б Вазирани, Умеш В. (2002). «Обзор квантовой теории сложности» . Материалы симпозиумов по прикладной математике . 58 : 193–217. дои : 10.1090/psapm/058/1922899 . ISBN 9780821820841 . ISSN 2324-7088 .

[:32-2] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Нильсен, Майкл А., 1974- (2010). Квантовые вычисления и квантовая информация . Чуанг, Исаак Л., 1968- (изд. к 10-летию). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3 . OCLC 665137861 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[:12-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Клив, Ричард (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 г.

[:27-4] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Уотрус, Джон (21 апреля 2008 г.). «Квантовая вычислительная сложность». arXiv : 0804.3401 [ квант-ph ].

[5] Нильсен, стр. 42.

[6] Нильсен, Майкл ; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. п. 41. ИСБН 978-0-521-63503-5 . OCLC 174527496 .

[7] Нильсен, стр. 201.

[BernVazi-8] Перейти обратно: Перейти обратно: ^а ^б Бернштейн, Итан; Вазирани, Умеш (1997). «Квантовая теория сложности» . SIAM Journal по вычислительной технике . 26 (5): 1411–1473. CiteSeerX 10.1.1.144.7852 . дои : 10.1137/S0097539796300921 .

[9] Ханер, Томас; Штайгер, Дамиан С. (12 ноября 2017 г.). «0,5-петабайтная симуляция 45-кубитной квантовой схемы» . Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 1–10. arXiv : 1704.01127 . дои : 10.1145/3126908.3126947 . ISBN 978-1-4503-5114-0 . S2CID 3338733 .

[10] Найкамп, DQ «Определение ориентированного графа» .

[:0-11] Перейти обратно: Перейти обратно: ^а ^б ^с Дурр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Сложность квантовых запросов некоторых задач на графах». SIAM Journal по вычислительной технике . 35 (6): 1310–1328. arXiv : Quant-ph/0401091 . дои : 10.1137/050644719 . ISSN 0097-5397 . S2CID 27736397 .

[12] Залка, Кристоф (1 октября 1999 г.). «Алгоритм квантового поиска Гровера оптимален» . Физический обзор А. 60 (4): 2746–2751. arXiv : Quant-ph/9711070 . Бибкод : 1999PhRvA..60.2746Z . дои : 10.1103/PhysRevA.60.2746 . S2CID 1542077 .

[auto-13] Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .

[14] Ааронсон, Скотт (2005). «NP-полные проблемы и физическая реальность». Новости ACM SIGACT . 2005 . arXiv : Quant-ph/0502072 . Бибкод : 2005quant.ph..2072A . См. раздел 7 «Квантовая гравитация»: «[...] всем, кто хочет проверить или оценить любимую теорию квантовой гравитации, [сноска автора: То есть тому, кто не удосужился делать числовые предсказания и сравнивать их с наблюдениями». ] позвольте мне смиренно предложить следующее: можете ли вы определить полиномиальное время квантовой гравитации [...] до тех пор, пока мы не сможем сказать, что значит для «пользователя» указать «входные данные» и «позже» получить «выходные данные» — такой вещи, как вычисления, не существует, даже теоретически » (курсив в оригинале).

[15] «D-Wave Systems продает свою первую квантовую вычислительную систему корпорации Lockheed Martin» . D-Волна. 25 мая 2011 г. Архивировано из оригинала 22 декабря 2020 г. . Проверено 30 мая 2011 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и Квантовая механика
Background	Introduction History Timeline Classical mechanics Old quantum theory Glossary
Fundamentals	Born rule Bra–ket notation Complementarity Density matrix Energy level Ground state Excited state Degenerate levels Zero-point energy Entanglement Hamiltonian Interference Decoherence Measurement Nonlocality Quantum state Superposition Tunnelling Scattering theory Symmetry in quantum mechanics Uncertainty Wave function Collapse Wave–particle duality
Formulations	Formulations Heisenberg Interaction Matrix mechanics Schrödinger Path integral formulation Phase space
Equations	Dirac Klein–Gordon Pauli Rydberg Schrödinger
Interpretations	Bayesian Consistent histories Copenhagen de Broglie–Bohm Ensemble Hidden-variable Local Superdeterminism Many-worlds Objective collapse Quantum logic Relational Transactional Von Neumann–Wigner
Experiments	Bell test Davisson–Germer Delayed-choice quantum eraser Double-slit Franck–Hertz Mach–Zehnder interferometer Elitzur–Vaidman Popper Quantum eraser Stern–Gerlach Wheeler's delayed choice
Science	Quantum biology Quantum chemistry Quantum chaos Quantum cosmology Quantum differential calculus Quantum dynamics Quantum geometry Quantum measurement problem Quantum mind Quantum stochastic calculus Quantum spacetime
Technology	Quantum algorithms Quantum amplifier Quantum bus Quantum cellular automata Quantum finite automata Quantum channel Quantum circuit Quantum complexity theory Quantum computing Timeline Quantum cryptography Quantum electronics Quantum error correction Quantum imaging Quantum image processing Quantum information Quantum key distribution Quantum logic Quantum logic gates Quantum machine Quantum machine learning Quantum metamaterial Quantum metrology Quantum network Quantum neural network Quantum optics Quantum programming Quantum sensing Quantum simulator Quantum teleportation
Extensions	Quantum fluctuation Casimir effect Quantum statistical mechanics Quantum field theory History Quantum gravity Relativistic quantum mechanics
Related	Schrödinger's cat in popular culture Wigner's friend EPR paradox Quantum mysticism
Category