ПостBQP

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

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

Удаление одной из двух основных функций (квантовость, поствыбор) из PostBQP дает следующие два класса сложности, оба из которых являются подмножествами PostBQP :

• BQP аналогичен PostBQP, но без поствыбора.
• BPP _Путь такой же, как и PostBQP, за исключением того, что вместо квантового алгоритма используется классический рандомизированный алгоритм (с поствыбором).

Добавление постселекции , кажется, делает квантовые машины Тьюринга намного более мощными: Скотт Ааронсон доказал PostBQP равен PP , классу, который считается относительно мощным, тогда как BQP неизвестно, что содержит даже кажущийся меньшим класс NP . Используя аналогичные методы, Ааронсон также доказал, что небольшие изменения в законах квантовых вычислений будут иметь значительные последствия. В качестве конкретных примеров: при любом из двух следующих изменений «новая» версия BQP будет равна PP :

• если бы мы расширили определение «квантовых вентилей», включив в него не только унитарные операции, но и линейные операции, или
• если вероятность измерения базисного состояния $|x\rangle$ был пропорционален $|\alpha _{x}|^{p}$ вместо $|\alpha _{x}|^{2}$ для любого четного целого числа p > 2 .

Основные свойства

Чтобы описать некоторые свойства PostBQP, мы зафиксируем формальный способ описания квантового постселектора. Определите квантовый алгоритм как семейство квантовых схем (в частности, семейство однородных схем ). Мы обозначаем один кубит как кубит P после выбора , а другой — как выходной кубит Q. Затем PostBQP определяется путем поствыбора в случае, если кубит после выбора $|1\rangle$. Явно, язык L находится в PostBQP, если существует квантовый алгоритм A, так что после запуска A на входе x и измерения двух кубитов P и Q ,

• P = 1 с ненулевой вероятностью
• если вход x находится в L , то Pr[ Q = 1| Р = 1] ≥ 2/3
• если входной сигнал x не принадлежит L, то Pr[ Q = 0| P знак равно 1] ≥ 2/3 .

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

Вот три основных свойства PostBQP (которые также справедливы и для BQP посредством аналогичных доказательств):

1. PostBQP закрывается при дополнении . Учитывая язык L в PostBQP и соответствующее семейство решающих схем, создайте новое семейство схем, перевернув выходной кубит после измерения, затем новое семейство схем докажет, что дополнение L находится в PostBQP .
2. Вы можете сделать усиление вероятности в PostBQP . Определение PostBQP не изменится, если мы заменим значение 2/3 в его определении на любую другую константу строго между 1/2 и 1. В качестве примера, учитывая PostBQP алгоритм A с вероятностью успеха 2/3, мы можем построить другой алгоритм, который запускает три независимых копии A , выводит бит поствыбора, равный соединению трех «внутренних» битов, и выводит выходной бит, равный большинству трех «внутренних»; новый алгоритм будет правильным с условной вероятностью $(2/3)^{3}+3(1/3)(2/3)^{2}=20/27$, больше исходных 2/3.
3. PostBQP закрыт под пересечением . Предположим, у нас есть семейства схем PostBQP для двух языков. $L_{1}$ и $L_{2}$, с соответствующими кубитами поствыбора и выходными кубитами $P_{1},P_{2},Q_{1},Q_{2}$. Путем усиления вероятности мы можем предположить, что оба семейства схем имеют вероятность успеха не менее 5/6. Затем мы создаем составной алгоритм, в котором схемы для $L_{1}$ и $L_{2}$ выполняются независимо, и мы устанавливаем P на соединение $P_{1}$ и $P_{2}$, а Q к конъюнкции $Q_{1}$ и $Q_{2}$. нетрудно увидеть С помощью оценки объединения , что этот составной алгоритм правильно определяет принадлежность к $L_{1}\cap L_{2}$ с (условной) вероятностью не менее 2/3.

В более общем смысле, комбинации этих идей показывают, что PostBQP закрыт при сокращении таблицы истинности объединения и BQP.

PostBQP = PP

Скотт Ааронсон показал что классы сложности ${\mathsf {PostBQP}}$ (поствыбранное квантовое полиномиальное время ошибки с ограниченной ошибкой) и PP (вероятностное полиномиальное время) равны. Результат был значительным, поскольку эта переформулировка квантовых вычислений ${\mathsf {PP}}$ дал новое понимание и более простые доказательства свойств ${\mathsf {PP}}$.

Обычное определение А. ${\mathsf {PostBQP}}$ Семейство схем — это семейство схем с двумя выходными кубитами P (поствыбор) и Q (выход) с единственным измерением P и Q на конце, так что вероятность измерения P = 1 имеет ненулевую вероятность, условная вероятность Pr[ Q = 1 | P = 1] ≥ 2/3 , если входной сигнал x находится в языке и Pr[ Q = 0| P = 1] ≥ 2/3 , если ввод x отсутствует на языке. По техническим причинам мы корректируем определение ${\mathsf {PostBQP}}$ следующим образом: потребуем, чтобы Pr[ P = 1] ≥ 2 ^{− п с} для некоторой константы c, зависящей от семейства схем. Обратите внимание, что этот выбор не влияет на основные свойства ${\mathsf {PostBQP}}$, а также можно показать, что любое вычисление, состоящее из типичных вентилей (например, Адамара, Тоффоли), обладает этим свойством всякий раз, когда Pr[ P = 1] > 0 .

Доказательство PostBQP ⊆ PP

Предположим, нам дан ${\mathsf {PostBQP}}$ для определения языка L. семейство схем Мы предполагаем без потери общности (см., например, несущественные свойства квантовых компьютеров ), что все ворота имеют матрицы перехода, представленные действительными числами, за счет добавления еще одного кубита.

Пусть Ψ обозначает конечное квантовое состояние схемы перед выполнением измерения после выбора. Общая цель доказательства — построить ${\mathsf {PP}}$ алгоритм принятия решения L . Более конкретно, достаточно, чтобы L правильно сравнил квадрат амплитуды Ψ в состояниях с Q = 1, P = 1 с квадратом амплитуды Ψ в состояниях с Q = 0, P = 1, чтобы определить, какое из них больше. Ключевой вывод заключается в том, что сравнение этих амплитуд можно преобразовать в сравнение вероятности принятия ${\mathsf {PP}}$ машина с 1/2.

представление

Пусть n обозначает входной размер, B = B ( n ) обозначает общее количество кубитов в схеме (входные, вспомогательные, выходные кубиты и кубиты поствыбора), а G = G ( n ) обозначает общее количество вентилей.Представьте i -й вентиль его матрицей перехода A ^я (настоящий унитарный $2^{B}\times 2^{B}$ матрица) и пусть начальное состояние будет $|x\rangle$ (дополняется нулями). Затем $\Psi =A^{G}A^{G-1}\dotsb A^{2}A^{1}|x\rangle$. Определим S ₁ (соответственно S ₀ ) как набор базисных состояний, соответствующих P = 1, Q = 1 (соответственно P = 1, Q = 0 ), и определим вероятности

$\pi _{1}:={\text{Pr}}[P=1,Q=1]=\sum _{\omega \in S_{1}}\Psi _{\omega }^{2}$

$\pi _{0}:={\text{Pr}}[P=1,Q=0]=\sum _{\omega \in S_{0}}\Psi _{\omega }^{2}.$

Определение ${\mathsf {PostBQP}}$ гарантирует, что либо $\pi _{1}\geq 2\pi _{0}$ или $\pi _{0}\geq 2\pi _{1}$ в зависимости от того, находится ли x в L или нет.

Наш ${\mathsf {PP}}$ машина сравнит $\pi _{1}$ и $\pi _{0}$. Для этого расширим определение умножения матриц:

$\Psi _{\omega }=\sum _{\alpha _{1},\ldots ,\alpha _{G}}A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}$

где сумма берется по всем спискам G базисных векторов $\alpha _{i}$. Сейчас $\pi _{1}$ и $\pi _{0}$ может быть выражено как сумма попарных произведений этих слагаемых. Интуитивно мы хотим спроектировать машину, вероятность приемлемости которой будет примерно такой: ${\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})$, с того времени $x\in L$ будет означать, что вероятность принятия равна ${\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})>{\tfrac {1}{2}}$, пока $x\not \in L$ будет означать, что вероятность принятия равна ${\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})<{\tfrac {1}{2}}$.

Формальность: можно предположить, что элементы переходных матриц A ^я являются рациональными числами со знаменателем 2 ^{ж ( п )} для некоторого полинома f ( n ).

Определение ${\mathsf {PostBQP}}$ говорит нам, что $\pi _{1}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})$ если x находится в L , и что в противном случае $\pi _{0}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})$. Заменим все элементы A ближайшей дробью со знаменателем $2^{f(n)}$ для большого полинома $f(n)$ что мы сейчас опишем. Позже будет использовано то, что новые значения π удовлетворяют $\pi _{1}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})$ если x находится в L и $\pi _{0}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})$ если x не находится в L . Используя ранее сделанное техническое предположение и анализируя, как изменяется 1-норма вычислительного состояния, можно увидеть, что это выполняется, если $(1+2^{-f(n)}2^{B})^{G}-1<{\tfrac {1}{6}}2^{-n^{c}},$ таким образом, очевидно, что существует достаточно большое f , полиномиальное по n .

Конструкция машины ПП

Теперь мы обеспечиваем детальную реализацию нашего ${\mathsf {PP}}$ машина. Обозначим через α последовательность $\{\alpha _{i}\}_{i=1}^{G}$ и определим сокращенное обозначение

$\Pi (A,\omega ,\alpha ,x):=A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}$,

затем

$\pi _{1}-\pi _{0}=\sum _{\omega \in S_{1}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)-\sum _{\omega \in S_{0}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x).$

Мы определяем наши ${\mathsf {PP}}$ машина для

• выбрать базисное состояние ω равномерно случайным образом
• если $\omega \not \in S_{0}\cup S_{1}$ затем СТОП и принять с вероятностью 1/2, отклонить с вероятностью 1/2
• выберите две последовательности $\alpha ,\alpha '$ случайным образом состояний базиса G равномерно и
• вычислить $X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)$ (это дробь со знаменателем $2^{2f(n)G(n)}$ такой, что $-1\leq X\leq 1$)
• если $\omega \in S_{1}$ тогда примите с вероятностью ${\tfrac {1+X}{2}}$ и отвергнуть с вероятностью ${\tfrac {1-X}{2}}$ (что занимает не более $2f(n)G(n)+1$ подбрасывание монеты)
• иначе (тогда $\omega \in S_{0}$) принять с вероятностью ${\tfrac {1-X}{2}}$ и отвергнуть с вероятностью ${\tfrac {1+X}{2}}$ (что опять-таки занимает не более $2f(n)G(n)+1$ подбрасывание монеты)

Тогда нетрудно вычислить, что эта машина с вероятностью принимает ${\frac {1}{2}}+{\frac {\pi _{1}-\pi _{0}}{2^{1+B(n)+2B(n)G(n)}}},$так что это ${\mathsf {PP}}$ машина для языка L по мере необходимости.

Доказательство PP ⊆ PostBQP

Предположим, у нас есть ${\mathsf {PP}}$ машина с временной сложностью $T:=T(n)$ на входе x длины $n:=|x|$. машина подбрасывает монету не более T Таким образом, за время вычислений раз. Таким образом, мы можем рассматривать машину как детерминированную функцию f (реализованную, например, классической схемой), которая принимает два входа ( x, r ), где r , двоичная строка длины T , представляет результаты случайных подбрасываний монеты, которые выполняются. путем вычисления, и выходной сигнал f равен 1 (принять) или 0 (отклонить). Определение ${\mathsf {PP}}$ говорит нам, что

$x\in L\Leftrightarrow \#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}>2^{T-1}$

Таким образом, мы хотим ${\mathsf {PostBQP}}$ алгоритм, который может определить, верно ли приведенное выше утверждение.

Определите s как количество случайных строк, которые приводят к принятию,

$s:=\#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}$

и так $2^{T}-s$ — количество отклоненных строк.Легко утверждать, что, не ограничивая общности, $s\not \in \{0,2^{T}/2,2^{T}\}$; подробнее см. аналогичное без ограничения общности предположение в доказательстве того, что ${\mathsf {PP}}$ закрыт при дополнении .

Алгоритм Ааронсона

Алгоритм Ааронсона решения этой задачи следующий. Для простоты будем писать все квантовые состояния как ненормированные. Сначала готовим состояние $|x\rangle \otimes \sum _{r\in \{0,1\}^{T}}|r\rangle |f(x,r)\rangle$. Во-вторых, мы применяем вентили Адамара ко второму регистру (каждому из первых T кубитов), измеряем второй регистр и выполняем поствыборку того, что он представляет собой строку, состоящую из всех нулей. Легко проверить, что при этом последний регистр (последний кубит) остается в остаточном состоянии.

$|\psi \rangle :=(2^{T}-s)|0\rangle +s|1\rangle .$

Где H обозначает ворота Адамара, мы вычисляем состояние

$H|\psi \rangle =(2^{T}|0\rangle +(2^{T}-2s)|1\rangle )/{\sqrt {2}}$.

Где $\alpha ,\beta$ положительные действительные числа, которые будут выбраны позже с помощью $\alpha ^{2}+\beta ^{2}=1$, мы вычисляем состояние $\alpha |0\rangle |\psi \rangle +\beta |1\rangle |H\psi \rangle$ и измерить второй кубит, постселектируя его значение, равное 1, что оставляет первый кубит в остаточном состоянии в зависимости от $\beta /\alpha$ который мы обозначаем

$|\phi _{\beta /\alpha }\rangle :=\alpha s|0\rangle +{\frac {\beta }{\sqrt {2}}}(2^{T}-2s)|1\rangle$.

Визуализируя возможные состояния кубита в виде круга, мы видим, что если $s>2^{T-1}$, (т.е. если $x\in L$) затем $\phi _{\beta /\alpha }$ лежит в открытом квадранте $Q_{acc}:=(-|1\rangle ,|0\rangle )$ в то время как если $s<2^{T-1}$, (т.е. если $x\not \in L$) затем $\phi _{\beta /\alpha }$ лежит в открытом квадранте $Q_{rej}:=(|0\rangle ,|1\rangle )$. Фактически для любого фиксированного x (и соответствующего ему s ), когда мы варьируем соотношение $\beta /\alpha$ в $(0,\infty )$, обратите внимание, что изображение $|\phi _{\beta /\alpha }\rangle$ является в точности соответствующим открытым квадрантом. В оставшейся части доказательства мы уточняем идею о том, что мы можем различать эти два квадранта.

Анализ

Позволять $|+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}$, который является центром $Q_{rej}$, и пусть $|-\rangle$ быть ортогональным $|+\rangle$. Любой кубит в $Q_{acc}$, при измерении в базисе $\{|+\rangle ,|-\rangle \}$, дает значение $|+\rangle$ менее 1/2 времени. С другой стороны, если $x\not \in L$ и мы выбрали $\beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)$ затем измеряю $|\phi _{\beta /\alpha }\rangle$ в основе $\{|+\rangle ,|-\rangle \}$ дал бы значение $|+\rangle$ все время. Поскольку мы не знаем s, мы также не знаем точного значения r* , но мы можем попробовать несколько (полиномиально много) разных значений для $\beta /\alpha$ в надежде получить тот, который «близок» к r* .

В частности, обратите внимание $2^{-T}<r*<2^{T}$ и давайте последовательно установим $\beta /\alpha$ каждому значению формы $2^{i}$ для $-T\leq i\leq T$. Тогда элементарные расчеты показывают, что для одного из этих значений i вероятность того, что измерение $|\phi _{2^{i}}\rangle$ в основе $\{|+\rangle ,|-\rangle \}$ урожайность $|+\rangle$ по крайней мере $(3+2{\sqrt {2}})/6\approx 0.971.$

В целом, ${\mathsf {PostBQP}}$ алгоритм следующий. Пусть k — любая константа строго между 1/2 и $(3+2{\sqrt {2}})/6$.Проделаем следующий эксперимент для каждого $-T\leq i\leq T$: построить и измерить $|\phi _{2^{i}}\rangle$ в основе $\{|+\rangle ,|-\rangle \}$ в общей сложности $C\log T$ раз, где C является константой. Если доля $|+\rangle$ измерения больше k , то отклоните. Если мы не отвергаем ни по одному i , примите. Тогда границы Чернова показывают, что для достаточно большой универсальной константы C мы правильно классифицируем x с вероятностью не менее 2/3.

Обратите внимание, что этот алгоритм удовлетворяет техническому предположению, что общая вероятность после выбора не слишком мала: каждое отдельное измерение $|\phi _{2^{i}}\rangle$ имеет вероятность постселекции $1/2^{O(T)}$ и поэтому общая вероятность равна $1/2^{O(T^{2}\log T)}$.

Последствия

• См. переформулировку PP для квантовых вычислений.