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

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

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

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

Фон [ править ]

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

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

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

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

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


Класс сложности	Критерии
п	Обещать задачи, для которых детерминированная машина Тьюринга с полиномиальным временем принимает все строки и отклоняет все строки в ^[4] ${\ displaystyle A_ {да}}$ ${\ displaystyle A_ {no}}$
BPP	Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую входящую строку с вероятностью не менее , и принимает каждую строку с вероятностью не более ^[4] ${\ displaystyle A_ {да}}$ ${\ displaystyle {\ frac {2} {3}}}$ ${\ displaystyle A_ {no}}$ ${\ displaystyle {\ frac {1} {3}}}$
BQP	Обещайте такие задачи, что для функций существует генерируемое за полиномиальное время семейство квантовых схем , где - схема, которая принимает кубиты и дает на выходе один кубит. Элемент из принимается с вероятностью больше или равна . Элемент из принят с вероятностью, меньшей или равной . ^[4] ${\ 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_ {да}}$ ${\ displaystyle Q}$ ${\ Displaystyle а (\ влево \ верт х \ вправо \ верт)}$ ${\ displaystyle x}$ ${\ displaystyle A_ {no}}$ ${\ displaystyle Q}$ $b(\left\vert x\right\vert )$
PP	Обещать задачи, для которых вероятностная машина Тьюринга с полиномиальным временем принимает каждую входящую строку с вероятностью больше, чем , и принимает каждую строку с вероятностью не более ^[4] $A_{yes}$ ${\frac {1}{2}}$ $A_{no}$ ${\frac {1}{2}}$
P-SPACE	Обещать задачи, для которых детерминированная машина Тьюринга, работающая в полиномиальном пространстве, принимает каждую строку в и отклоняет все строки в ^[4] $A_{yes}$ $A_{no}$

BQP [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Обратите внимание на несоответствие между сложностями квантовых запросов, связанных с конкретным типом проблемы, в зависимости от того, какая модель запроса использовалась для определения сложности. Например, когда используется матричная модель, квантовая сложность модели связности в нотации 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] $f:\{0,1\}^{n}\rightarrow \{0,1\}$ $f$ $2^{n}$ $2^{n-1}+1$ Алгоритм Дойча-Йозса использует преимущества квантового параллелизма для одновременной проверки всех элементов домена, и ему требуется только один раз запросить оракул, что усложняет его запрос . ^[2] $1$

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

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

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

^ a b Вазирани, Умеш В. (2002). «Обзор квантовой теории сложности» . Материалы симпозиумов по прикладной математике . 58 : 193–217. DOI : 10.1090 / psapm / 058/1922899 . ISBN 9780821820841. ISSN 2324-7088 .
^ a b c d Нильсен, Майкл А., 1974- (2010). Квантовые вычисления и квантовая информация . Чуанг, Исаак Л., 1968- (10-летие изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3. OCLC 665137861 .CS1 maint: multiple names: authors list (link)
^ a b c d e f g Ричард Клив (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 г.
^ Б с д е е г Watrous, Джон (2008-04-21). «Квантовая вычислительная сложность». arXiv : 0804.3401 [ квант-ф ].
^ Нильсен, стр. 42
^ Нильсен, Майкл ; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. п. 41. ISBN 978-0-521-63503-5. OCLC 174527496 .
^ Нильсен, стр. 201
^ а б Бернштейн, Итан; Вазирани, Умеш (1997). «Квантовая теория сложности» . SIAM Journal on Computing . 26 (5): 1411–1473. CiteSeerX 10.1.1.144.7852 . DOI : 10,1137 / S0097539796300921 .
^ Хенер, Томас; Штайгер, Дамиан С. (12.11.2017). «Моделирование 0,5 петабайта квантовой схемы из 45 кубитов» . Труды Международной конференции по высокопроизводительным вычислениям, сетям, хранилищам и анализу . Нью-Йорк, Нью-Йорк, США: ACM: 1–10. arXiv : 1704.01127 . DOI : 10.1145 / 3126908.3126947 . ISBN 978-1-4503-5114-0. S2CID 3338733 .
^ Nykamp, DQ "Определение ориентированного графа" .
^ a b c Дурр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Квантовая сложность запроса некоторых задач графа». SIAM Journal on Computing . 35 (6): 1310–1328. arXiv : квант-ph / 0401091 . DOI : 10.1137 / 050644719 . ISSN 0097-5397 . S2CID 27736397 .
^ Залки, Кристофа (1999-10-01). «Алгоритм квантового поиска Гровера оптимален» . Physical Review . 60 (4): 2746–2751. arXiv : квант-ph / 9711070 . Bibcode : 1999PhRvA..60.2746Z . DOI : 10.1103 / PhysRevA.60.2746 . S2CID 1542077 .

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

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

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

MIT лекции по Ааронсон

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

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

[: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] Б с д е е г Watrous, Джон (2008-04-21). «Квантовая вычислительная сложность». arXiv : 0804.3401 [ квант-ф ].

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

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

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

[BernVazi-8] а б Бернштейн, Итан; Вазирани, Умеш (1997). «Квантовая теория сложности» . SIAM Journal on Computing . 26 (5): 1411–1473. CiteSeerX 10.1.1.144.7852 . DOI : 10,1137 / S0097539796300921 .

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

[10] Nykamp, DQ "Определение ориентированного графа" .

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

[12] Залки, Кристофа (1999-10-01). «Алгоритм квантового поиска Гровера оптимален» . Physical Review . 60 (4): 2746–2751. arXiv : квант-ph / 9711070 . Bibcode : 1999PhRvA..60.2746Z . DOI : 10.1103 / PhysRevA.60.2746 . S2CID 1542077 .

[1]