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

Эта статья о классе вычислительной сложности. Чтобы узнать о других значениях, см. BQP (значения) .

BQP по отношению к другим классам вероятностной сложности ( ZPP , RP , co-RP, BPP , PP ), которые обобщают P в рамках PSPACE . Неизвестно, являются ли какие-либо из этих ограничений строгими.

В сложности вычислений теории квантовое полиномиальное время с ограниченной ошибкой ( BQP ) — это класс задач решения , решаемых квантовым компьютером за полиномиальное время , с вероятностью ошибки не более 1/3 для всех случаев. Это квантовый аналог класса сложности BPP .

Проблема принятия решения является членом BQP, если существует квантовый алгоритм ( алгоритм , работающий на квантовом компьютере), который решает проблему принятия решения с высокой вероятностью и гарантированно работает за полиномиальное время. Запуск алгоритма правильно решит задачу решения с вероятностью не менее 2/3.

Алгоритм BQP (1 прогон)
Отвечать произведено Правильный отвечать	Да	Нет
Да	≥ 2/3	≤ 1/3
Нет	≤ 1/3	≥ 2/3
Алгоритм BQP ( k прогонов)
Отвечать произведено Правильный отвечать	Да	Нет
Да	> 1 - 2 − ск	< 2 − ск
Нет	< 2 − ск	> 1 - 2 − ск
для некоторой константы c > 0

Определение

BQP можно рассматривать как языки с ограниченной ошибкой , связанные с определенными однородными семействами квантовых схем . Язык L находится в BQP тогда и только тогда, когда существует однородное за полиномиальное время семейство квантовых схем. $\{Q_{n}\colon n\in \mathbb {N} \}$, такой, что

• Для всех $n\in \mathbb {N}$, Q _n принимает на вход n кубитов и выводит 1 бит
• Для всех x в L , $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
• Для всех x не из L , $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

В качестве альтернативы можно определить BQP в терминах квантовых машин Тьюринга . Язык L находится в BQP тогда и только тогда, когда существует полиномиальная квантовая машина Тьюринга, которая принимает L с вероятностью ошибки не более 1/3 для всех случаев.

Как и в случае с другими вероятностными классами «ограниченной ошибки», выбор 1/3 в определении произволен. Мы можем запускать алгоритм постоянное количество раз и принимать большинство голосов для достижения любой желаемой вероятности правильности меньше 1, используя границу Чернова . Класс сложности не изменяется, поскольку допускается ошибка до 1/2 − n. ^{− с} с одной стороны, или требующие погрешности всего 2 ^{− п с} с другой стороны, где c — любая положительная константа, а n — длина ввода.

Связь с другими классами сложности

Нерешенная задача в информатике :

Какова связь между ${\mathsf {BQP}}$ и ${\mathsf {NP}}$?

(еще нерешенные проблемы по информатике)

Предполагаемая связь BQP с другими проблемными пространствами

BQP определен для квантовых компьютеров; соответствующий класс сложности для классических компьютеров (или, более формально, для вероятностных машин Тьюринга ) — BPP . Так же, как P и BPP , BQP , сам по себе низкий что означает, что BQP ^{Министерство национальной обороны} = Министерство национальной обороны . Неформально это верно, поскольку алгоритмы с полиномиальным временем замкнуты относительно композиции. Если алгоритм с полиномиальным временем вызывает алгоритмы с полиномиальным временем как подпрограммы, результирующий алгоритм по-прежнему будет иметь полиномиальное время.

BQP содержит P и BPP и содержится в AWPP , ПП и PSPACE . Фактически, BQP низкий , для PP а это означает, что машина PP не получает никакой выгоды от мгновенного решения проблем BQP , что указывает на возможную разницу в мощности между этими схожими классами. Известные связи с классическими классами сложности:

${\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}$

Поскольку проблема ⁠ ${\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}$⁠ еще не решена, доказательство неравенства между BQP и упомянутыми выше классами должно быть трудным. Связь между BQP и NP неизвестна. В мае 2018 года учёные-компьютерщики Ран Раз из Принстонского университета и Авишай Таль из Стэнфордского университета опубликовали статью. который показал, что относительно оракула BQP не содержится в PH . Можно доказать, что существует оракул А такой, что ${\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }$. В крайне неформальном смысле это можно рассматривать как предоставление PH и BQP идентичных, но дополнительных возможностей и проверку того, что BQP с оракулом (BQP ^А ) может делать что-то PH ^А не могу. Хотя разделение оракула было доказано, тот факт, что BQP не содержится в PH, не был доказан. Разделение оракула не доказывает, одинаковы ли классы сложности. Разделение оракула дает представление о том, что BQP может не содержаться в PH.

В течение многих лет подозревалось, что выборка Фурье — это проблема, существующая в BQP, но не в полиномиальной иерархии. Недавние предположения предоставили доказательства того, что аналогичная проблема, проверка Фурье, также существует в классе BQP, но не содержится в полиномиальной иерархии . Эта гипотеза особенно примечательна, поскольку предполагает, что проблемы, существующие в BQP, могут быть классифицированы как более сложные, чем проблемы NP-Complete . В сочетании с тем фактом, что многие практические проблемы BQP, как предполагается, существуют за пределами P (это подозревается, но не проверено, поскольку нет доказательств того, что P ≠ NP ), это иллюстрирует потенциальную мощь квантовых вычислений по сравнению с классическими вычислениями.

Добавление постселекции к BQP приводит к созданию класса сложности PostBQP , который равен PP .

Полная проблема для Promise-BQP

Promise-BQP — это класс задач обещания , которые могут быть решены с помощью однородного семейства квантовых схем (т. е. внутри BQP). Доказательства полноты сосредоточены на этой версии BQP. Подобно понятию NP-полноты и другим полным проблемам, мы можем определить полную проблему как проблему, которая находится в Promise-BQP и к которой любая другая проблема в Promise-BQP сводится к ней за полиномиальное время.

ПРИБЛИЗИТЕЛЬНО-QCIRCUIT-PROB

Задача APPROX-QCIRCUIT-PROB является полной для эффективных квантовых вычислений, а представленная ниже версия является полной для класса сложности Promise-BQP (а не для общего класса сложности BQP, для которого не известны полные задачи). Полнота APPROX-QCIRCUIT-PROB делает его полезным для доказательств, показывающих отношения между другими классами сложности и BQP.

Дано описание квантовой схемы C, действующей на n кубитов с m вентилями, где m — многочлен от n , а каждый вентиль действует на один или два кубита, и два числа $\alpha ,\beta \in [0,1],\alpha >\beta$, различают следующие два случая:

• измерение первого кубита состояния $C|0\rangle ^{\otimes n}$ урожайность $|1\rangle$ с вероятностью $\geq \alpha$
• измерение первого кубита состояния $C|0\rangle ^{\otimes n}$ урожайность $|1\rangle$ с вероятностью $\leq \beta$

Здесь есть обещание на входных данных, поскольку проблема не определяет поведение, если экземпляр не подпадает под эти два случая.

Требовать. Любая проблема BQP сводится к APPROX-QCIRCUIT-PROB.

Доказательство. Предположим, у нас есть алгоритм A , который решает APPROX-QCIRCUIT-PROB, т. е. дана квантовая схема C, действующая на n кубитов, и два числа $\alpha ,\beta \in [0,1],\alpha >\beta$, A различает два вышеуказанных случая. С помощью этого оракула мы можем решить любую проблему в BQP, установив $\alpha =2/3,\beta =1/3$.

Для любого $L\in {\mathsf {BQP}}$, существует семейство квантовых схем $\{Q_{n}\colon n\in \mathbb {N} \}$ такой, что для всех $n\in \mathbb {N}$, государство $|x\rangle$ из $n$ кубиты, если $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$; еще если $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$. Исправить ввод $|x\rangle$ из n кубитов и соответствующая квантовая схема $Q_{n}$. Сначала мы можем построить цепь $C_{x}$ такой, что $C_{x}|0\rangle ^{\otimes n}=|x\rangle$. Это можно легко сделать с помощью проводного подключения. $|x\rangle$ и примените последовательность вентилей CNOT, чтобы перевернуть кубиты. Тогда мы можем объединить две схемы, чтобы получить $C'=Q_{n}C_{x}$, и теперь $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$. И, наконец, обязательно результаты $Q_{n}$ получается путем измерения нескольких кубитов и применения к ним некоторых (классических) логических элементов. Мы всегда можем отложить измерение и перенаправить цепи так, чтобы, измеряя первый кубит $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$, мы получаем результат. Это будет наша схема C , и мы решаем принадлежность $x\in L$ запустив $A(C)$ с $\alpha =2/3,\beta =1/3$. По определению BQP мы попадаем либо в первый случай (принятие), либо во второй случай (неприятие), поэтому $L\in {\mathsf {BQP}}$ сокращается до APPROX-QCIRCUIT-PROB.

БКП и опыт

Начнем с более легкого сдерживания. Чтобы показать это ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$, достаточно показать, что APPROX-QCIRCUIT-PROB находится в EXP, поскольку APPROX-QCIRCUIT-PROB является BQP-полным.

Требовать - ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$

Доказательство

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

Более формально, пусть C — квантовая схема полиномиального размера на n кубитах и ​​m вентилях, где m полиномиально от n. Позволять $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ и $|\psi _{i}\rangle$ быть состоянием после того, как i -й вентиль в схеме применен к $|\psi _{i-1}\rangle$. Каждое государство $|\psi _{i}\rangle$ может быть представлен в классическом компьютере как единичный вектор в $\mathbb {C} ^{2^{n}}$. Кроме того, каждый вентиль может быть представлен матрицей в $\mathbb {C} ^{2^{n}\times 2^{n}}$. Следовательно, окончательное состояние $|\psi _{m}\rangle$ можно вычислить в $O(m\cdot 2^{2n})$ время, а значит, и все вместе, мы имеем $2^{O(n)}$ алгоритм времени для расчета конечного состояния и, следовательно, вероятность того, что первый кубит будет равен единице. Это означает, что ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$.

Обратите внимание, что этот алгоритм также требует $2^{O(n)}$ пространство для хранения векторов и матриц. В следующем разделе мы покажем, что можно улучшить пространственную сложность.

БКП и PSPACE

Сумма историй — это метод, предложенный физиком Ричардом Фейнманом для формулировки интеграла по траектории . APPROX-QCIRCUIT-PROB можно сформулировать с помощью метода суммы историй, чтобы показать, что ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$.

Дерево суммы историй

Рассмотрим квантовую схему C , состоящую из t вентилей: $g_{1},g_{2},\cdots ,g_{m}$, где каждый $g_{j}$ исходит из универсального набора вентилей и действует не более чем на два кубита. Чтобы понять, что такое сумма историй, мы визуализируем эволюцию квантового состояния, учитывая квантовую схему в виде дерева. Корень – это вход $|0\rangle ^{\otimes n}$, и каждый узел дерева имеет $2^{n}$ детей, каждый из которых представляет государство в $\mathbb {C} ^{n}$. Вес на ребре дерева от узла j -го уровня, представляющего состояние $|x\rangle$ к узлу в $j+1$-й уровень, представляющий состояние $|y\rangle$ является $\langle y|g_{j+1}|x\rangle$, амплитуда $|y\rangle$ после подачи заявки $g_{j+1}$ на $|x\rangle$. Амплитуда перехода пути от корня к листу является произведением всех весов на ребрах пути. Чтобы получить вероятность того, что конечное состояние будет $|\psi \rangle$, мы суммируем амплитуды всех корневых путей, которые заканчиваются в узле, представляющем $|\psi \rangle$.

Более формально, для квантовой схемы C ее сумма по дереву историй представляет собой дерево глубины m с одним уровнем для каждого вентиля. $g_{i}$ помимо корня и с фактором ветвления $2^{n}$.

Определить : история — это путь в дереве историй. Обозначим историю последовательностью $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ для некоторого конечного состояния x .

Определить — Пусть $u,v\in \{0,1\}^{n}$. Пусть амплитуда края $(|u\rangle ,|v\rangle )$ на j -м уровне дерева суммирования по историям будет $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$. Для любой истории $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$, амплитуда перехода истории есть произведение $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$.

Претензия — Для истории $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ . Амплитуда перехода истории вычислима за полиномиальное время.

Доказательство

Каждые ворота $g_{j}$ можно разложить на $g_{j}=I\otimes {\tilde {g}}_{j}$ для некоторого унитарного оператора ${\tilde {g}}_{j}$ действующий на два кубита, за которые без ограничения общности можно принять первые два. Следовательно, $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ который можно вычислить за полиномиальное время от n . Поскольку m является полиномиальным по n , амплитуда перехода истории может быть вычислена за полиномиальное время.

Претензия — Пусть $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ быть конечным состоянием квантовой схемы. Для некоторых $x\in \{0,1\}^{n}$, амплитуда $\alpha _{x}$ может быть вычислено с помощью $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$.

Доказательство

У нас есть $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$. Результат достигается непосредственно путем вставки $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ между $g_{1},g_{2}$, и $g_{2},g_{3}$и так далее, а затем разверните уравнение. Тогда каждому члену соответствует $\alpha _{h}$, где $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$

Требовать - ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}$

Обратите внимание, что в алгоритме суммирования по историям вычисляется некоторая амплитуда. $\alpha _{x}$, в любой момент вычислений сохраняется только одна история. Следовательно, алгоритм суммы по историям использует $O(nm)$ пространство для вычислений $\alpha _{x}$ для любого x, поскольку $O(nm)$ биты необходимы для хранения истории в дополнение к некоторым переменным рабочей области.

Следовательно, в полиномиальном пространстве мы можем вычислить $\sum _{x}|\alpha _{x}|^{2}$ по всем x, где первый кубит равен 1 , что представляет собой вероятность того, что первый кубит будет равен 1 к концу схемы.

Обратите внимание, что по сравнению с моделированием, приведенным для доказательства того, что ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$, наш алгоритм занимает гораздо меньше места, но гораздо больше времени. На самом деле это занимает $O(m\cdot 2^{mn})$ пора вычислить одну амплитуду!

БКП и ПП

Аналогичный аргумент суммирования по историям можно использовать, чтобы показать, что ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$.

П и БКП

Мы знаем ${\mathsf {P}}\subseteq {\mathsf {BQP}}$, поскольку каждая классическая схема может быть смоделирована квантовой схемой.

Предполагается, что BQP решает сложные проблемы вне P, в частности, проблемы в NP. Утверждение неопределенно, потому что мы не знаем, = P = NP, поэтому мы не знаем, действительно ли эти проблемы находятся в P. Ниже приведены некоторые доказательства гипотезы:

• Целочисленная факторизация (см. алгоритм Шора )
• Дискретный логарифм
• Моделирование квантовых систем (см. универсальный квантовый симулятор )
• Аппроксимация полинома Джонса при некоторых корнях из единицы
• Алгоритм Харроу-Хассидим-Ллойда (HHL)

См. также

• Проблема скрытой подгруппы
• Полиномиальная иерархия (PH)
• Квантовая теория сложности
• QMA , квантовый эквивалент NP .
• QIP , квантовый эквивалент IP.

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

• Ссылка Complexity Zoo на BQP. Архивировано 3 июня 2013 г. на Wayback Machine.