PostBQP

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

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

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

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

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

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

Основные свойства [ править ]

Чтобы описать некоторые свойства PostBQP, мы фиксируем формальный способ описания квантового постселекции. Определите квантовый алгоритм как семейство квантовых схем (в частности, семейство однородных схем ). Обозначим один кубит как postselection кубите 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.

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

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

1. PostBQP будет закрыто под комплемента . Учитывая язык L в PostBQP и соответствующее семейство решающих схем, создайте новое семейство схем, перевернув выходной кубит после измерения, тогда новое семейство схем докажет, что дополнение L находится в PostBQP .

2. Вы можете сделать усиление вероятности в PostBQP . Определение PostBQP не изменится, если мы заменим значение 2/3 в его определении любой другой константой строго между 1/2 и 1. В качестве примера, учитывая алгоритм PostBQP A с вероятностью успеха 2/3, мы можем построить другой алгоритм, который запускает три независимые копии A , выводит бит поствыбора, равный конъюнктуре трех «внутренних», и выводит бит вывода, равный большинству из трех «внутренних»; новый алгоритм будет правильным с условной вероятностью , большей, чем исходный 2/3.${\ Displaystyle (2/3) ^ {3} +3 (1/3) (2/3) ^ {2} = 20/27}$

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

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

PostBQP = PP [ редактировать ]

Скотт Ааронсон показал ^[5], что классы сложности 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^{- n c} для некоторой константы c в зависимости от семейства схем. Обратите внимание, что этот выбор не влияет на основные свойства PostBQP , а также можно показать, что любое вычисление, состоящее из типичных вентилей (например, Адамара, Тоффоли), имеет это свойство всякий раз, когда Pr [ P  = 1]> 0.

Доказательство PostBQP ⊆ PP [ править ]

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

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

Матричный вид алгоритмов PostBQP [ править ]

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

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

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

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

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

${\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}}}$

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

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

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

Конструирование машины PP [ править ]

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

${\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}}}$,

тогда

${\displaystyle \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).}$

Мы определяем нашу машину из полипропилена в

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

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

Доказательство PP ⊆ PostBQP [ править ]

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

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

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

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

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

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

Алгоритм Ааронсона [ править ]

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

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

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

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

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

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

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

Анализ [ править ]

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

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

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

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

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

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

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