PostBQP

редактировать

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

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

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

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

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

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

Содержание

1 Основные свойства
2 PostBQP = PP
3 Доказательство PostBQP ⊆ PP
- 3.1 Матричный вид алгоритмов PostBQP
  - 3.1.1 Технические аспекты: мы можем предположить, что элементы матриц перехода A являются рациональными со знаминателем 2 для некоторого полинома f (n).
- 3.2 Построение машина PP
4 Доказательство PP ⊆ PostBQP
- 4.1 Алгоритм Ааронсона
- 4.2 Анализ
5 Последствия
6 Ссылки

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

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

P = 1 с ненулевой вероятностью
, если вход x находится в L, тогда Pr [Q = 1 | P = 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 {\ displaystyle (2/3) ^ {3} +3 ( 1/3) (2/3) ^ {2} = 20/27}$ $(2/3) ^ {3} +3 (1/3) (2/3) ^ {2} = 20/27$ , больше исходных 2/3.

3. PostBQP закрывается на перекрестке . Предположим, у нас есть семейства схем PostBQP для двух языков L1 и L2, с соответствующими кубитами после выбора и выходными кубитами P1, P2, Q1, Q2. Путем усиления вероятности мы можем предположить, что оба семейства схем имеют вероятность успеха не менее 5/6. Затем мы создаем составной алгоритм, в котором схемы для L1 и L2 выполняются независимо, и мы устанавливаем P равным соединению P1 и P2, а Q - соединению Q1 и Q2. По границе объединения нетрудно увидеть, что этот составной алгоритм правильно определяет принадлежность к $L 1 ∩ L 2 {\ displaystyle L1 \ cap L2}$ $L1 \ cap L2$ с (условным) вероятность не менее 2/3.

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

PostBQP = PP

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

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

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

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

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

Матричное представление алгоритмов PostBQP

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

π 1: = Pr [P = 1, Q = 1] = ∑ ω ∈ S 1 Ψ ω 2 {\ displaystyle \ pi _ {1}: = {\ text {Pr}} [P = 1, Q = 1] = \ sum _ {\ omega \ in S_ {1}} \ Psi _ {\ omega} ^ {2}}

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

π 0: = Pr [P = 1, Q = 0] = ∑ ω ∈ S 0 Ψ ω 2. {\ displaystyle \ pi _ {0}: = {\ text {Pr}} [P = 1, Q = 0] = \ sum _ {\ omega \ in S_ {0}} \ Psi _ {\ omega} ^ { 2}.}

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

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

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

Ψ ω = ∑ α 1,…, α GA ω, α GGA α G, α G - 1 G - 1 ⋯ A α 3, α 2 2 A α 2, α 1 1 Икс α 1 {\ Displaystyle \ 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}}}

\ 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 $α я {\ Displaystyle \ альфа _ {я}}$ $\ alpha _ {i}$ . Теперь $π 1 {\ displaystyle \ pi _ {1}}$ $\ pi _ {1}$ и $π 0 {\ displaystyle \ pi _ {0}}$ $\ pi _ {0}$ можно выразить как сумму попарных произведений этих слагаемых. Интуитивно мы хотим разработать машину, вероятность приемки которой равна примерно $1 2 (1 + π 1 - π 0) {\ displaystyle {\ tfrac {1} {2}} (1+ \ pi _ {1} - \ pi _ {0})}$ ${\ displaystyle {\ tfrac {1} {2}} (1+ \ pi _ {1} - \ pi _ {0})}$ , с тех пор $x ∈ L {\ displaystyle x \ in L}$ $x \ in L$ будет означать, что вероятность принятия будет $1 2 (1 + π 1 - π 0)>1 2 {\ displaystyle {\ tfrac {1} {2}} (1+ \ pi _ {1} - \ pi _ {0})>{\ tfrac {1} { 2}}}$ ${\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})>{\ tfrac {1} {2}}$ , а $x ∉ L {\ displaystyle x \ not \ in L}$ $x \ not \ in L$ будет означать, что вероятность принятия составляет $1 2 (1 + π 1 - π 0) < 1 2 {\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})<{\tfrac {1}{2}}}$ ${\ displaystyle {\ tfrac {1} {2}} (1+ \ pi _ {1} - \ pi _ {0}) <{\ tfrac {1} {2}} }$ .

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

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

Создание машины PP

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

Π (A, ω, α, x): = A ω, α GGA α G, α G - 1 G - 1 ⋯ A α 3, α 2 2 A α 2, α 1 1 x α 1 { \ displaystyle \ 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 (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}}}

, тогда

π 1 - π 0 = ∑ ω ∈ S 1 ∑ α, α ′ Π (A, ω, α, x) Π (A, ω, α ′, x) - ∑ ω ∈ S 0 ∑ α, α ′ Π (A, ω, α, x) Π (A, ω, α ′, x). {\ displaystyle \ pi _ {1} - \ pi _ {0} = \ sum _ {\ omega \ in S_ {1}} \ sum _ {\ alpha, \ alpha '} \ Pi (A, \ omega, \ альфа, х) \ Pi (A, \ omega, \ alpha ', x) - \ sum _ {\ omega \ in S_ {0}} \ sum _ {\ alpha, \ alpha'} \ Pi (A, \ omega, \ alpha, x) \ Pi (A, \ omega, \ alpha ', x).}

\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).

Мы определяем нашу машину PP, чтобы

выбрать базовое состояние ω равномерно и случайным образом
если $ω ∉ S 0 ∪ S 1 {\ displaystyle \ omega \ not \ in S_ {0} \ cup S_ {1}}$ $\ omega \ not \ in S_ {0} \ cup S_ {1}$ , то ОСТАНОВИТЕСЬ и примите с вероятностью 1/2, отклонить с вероятностью 1/2
выбрать две последовательности $α, α ′ {\ displaystyle \ alpha, \ alpha '}$ $\alpha,\alpha '$ базисных состояний G равномерно случайным образом
вычислить $Икс = Π (A, ω, α, x) Π (A, ω, α ′, x) {\ displaystyle X = \ Pi (A, \ omega, \ alpha, x) \ Pi ( A, \ omega, \ alpha ', x)}$ $X=\Pi (A,\omega,\alpha,x)\Pi (A,\omega,\alpha ',x)$ (дробь со знаминателем $2 2 f (n) G (n) {\ displaystyle 2 ^ {2f (n) G ( n)}}$ $2 ^ {{2f (n) G (n)}}$ такой, что $- 1 ≤ X ≤ 1 {\ displaystyle -1 \ leq X \ leq 1}$ $-1 \ leq X \ leq 1$ )
, если $ω ∈ S 1 {\ displaystyle \ omega \ в S_ {1}}$ $\ omega \ in S_ {1}$ затем принять с вероятностью ity $1 + X 2 {\ displaystyle {\ tfrac {1 + X} {2}}}$ ${\ displaystyle {\ tfrac {1 + X} {2}}}$ и отклонить с вероятностью $1 - X 2 {\ displaystyle {\ tfrac {1- X} {2}}}$ ${\ displaystyle {\ tfrac {1-X} {2}}}$ (что занимает не более $2 f (n) G (n) + 1 {\ displaystyle 2f (n) G (n) +1}$ ${\ displaystyle 2f (n) G (n) +1}$ подбрасывание монеты)
в противном случае (тогда $ω ∈ S 0 {\ displaystyle \ omega \ in S_ {0}}$ $\ omega \ in S_ { 0}$ ) принять с вероятностью $1 - X 2 {\ displaystyle {\ tfrac {1-X} {2}}}$ ${\ displaystyle {\ tfrac {1-X} {2}}}$ и отклонить с вероятностью $1 + X 2 {\ displaystyle {\ tfrac {1 + X} {2}}}$ ${\ displaystyle {\ tfrac {1 + X} {2}}}$ (что снова занимает не более $2 f (n) G (n) + 1 {\ displaystyle 2f (n) G (n) +1}$ ${\ displaystyle 2f (n) G (n) +1}$ подбрасывание монеты)

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

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

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

x ∈ L ⇔ # {r ∈ {0, 1} T ∣ f (x, r) = 1} ≥ 2 T - 1 {\ displaystyle x \ in L \ Leftrightarrow \ # \ {r \ in \ {0,1 \} ^ {T} \ mid f (x, r) = 1 \} \ geq 2 ^ {T-1}}

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

Таким образом, мы нужен алгоритм PostBQP, который может определить, истинно ли приведенное выше утверждение.

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

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

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

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

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

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

| ψ⟩: = (2 Тл - с) | 0⟩ + s | 1⟩. {\ displaystyle | \ psi \ rangle: = (2 ^ {T} -s) | 0 \ rangle + s | 1 \ rangle.}

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

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

H | ψ⟩ знак равно (2 T | 0⟩ + (2 T - 2 s) | 1⟩) / 2 {\ displaystyle H | \ psi \ rangle = (2 ^ {T} | 0 \ rangle + (2 ^ {T}) -2s) | 1 \ rangle) / {\ sqrt {2}}}

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

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

| ϕ β / α⟩: = α s | 0⟩ + β 2 (2 Тл - 2 с) | 1⟩ {\ displaystyle | \ phi _ {\ beta / \ alpha} \ rangle: = \ alpha s | 0 \ rangle + {\ frac {\ beta} {\ sqrt {2}}} (2 ^ {T} - 2s) | 1 \ rangle}

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

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

Анализ

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

В частности, обратите внимание на $2 - T < r ∗ < 2 T {\displaystyle 2^{-T}$ $2 ^ {{- T}} <r * <2 ^ {T}$ и давайте последовательно установим $β / α {\ displaystyle \ beta / \ alpha}$ $\ beta / \ alpha$ на каждое значение формы $2 я {\ displaystyle 2 ^ {i}}$ $2^{i}$ для $- T ≤ i ≤ T {\ displaystyle -T \ leq i \ leq T}$ $-T \ leq i \ leq T$ . Затем элементарные вычисления показывают, что для одного из этих значений i вероятность того, что измерение $| ϕ 2 я⟩ {\ displaystyle | \ phi _ {2 ^ {i}} \ rangle}$ $| \ phi _ {{2 ^ {i}}} \ rangle$ в основе ${| +⟩, | -⟩} {\ displaystyle \ {| + \ rangle, | - \ rangle \}}$ $\ {| + \ rangle, | - \ rangle \}$ дает $| +⟩ {\ Displaystyle | + \ rangle}$ $| + \ rangle$ не менее $(3 + 2 2) / 6 ≈ 0,971. {\ displaystyle (3 + 2 {\ sqrt {2}}) / 6 \ приблизительно 0,971.}$ $(3 + 2 {\ sqrt {2}}) / 6 \ приблизительно 0,971.$

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

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

Последствия

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

Ссылки

^Y. Хан и Хемаспандра, Л. и Тиерауф, Т. (1997). «Пороговые вычисления и криптографическая безопасность». Журнал SIAM по вычислительной технике. 26: 59–78. CiteSeerX 10.1.1.23.510. doi : 10.1137 / S0097539792240467. CS1 maint: несколько имен: список авторов (ссылка )
^ Ааронсон, Скотт (2005). «Квантовые вычисления, поствыбор, и вероятностное полиномиальное время ". Труды Королевского общества A. 461 (2063): 3473–3482. arXiv : Quant-ph / 0412187. Bibcode : 2005RSPSA.461.3473A. doi : 10.1098 / rspa.2005.1546.. Препринт доступен на [1]
^Ааронсон, Скотт (2004-01-11). «Класс сложности недели: PP». Журнал вычислительной сложности. Проверено 2 мая 2008 г.
^Ethan Bernstein Умеш Вазирани (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 11–20. CiteSeerX 10.1.1.144.7852. doi : 10.1137 / s0097539796300921.
^Ааронсон, Скотт (2005). «Квантовые вычисления, поствыбор и вероятностное полиномиальное время». Труды Королевского общества A. 461 (2063): 3473–3482. arXiv : Quant-ph / 0412187. Bibcode : 2005RSPSA.461.3473A. doi :10.1098/rspa.2005.1546.