PostBQP - PostBQP

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

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

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

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

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

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

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

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

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

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

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

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

2. Вы можете сделать усиление вероятности в PostBQP. Определение PostBQP не изменится, если мы заменим значение 2/3 в его определении любой другой константой строго между 1/2 и 1. В качестве примера, учитывая PostBQP алгоритм А с вероятностью успеха 2/3, мы можем построить другой алгоритм, который запускает три независимых копии А, выводит бит поствыбора, равный соединение из трех «внутренних» и выводит выходной бит, равный большинство из трех «внутренних»; новый алгоритм будет правильным с условной вероятностью ${displaystyle (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 выполняются независимо, и мы устанавливаем п к соединению P1 и P2, и Q к соединению Q1 и 2 квартал. Нетрудно увидеть по связанный союз что этот составной алгоритм правильно определяет членство в ${displaystyle L1cap L2}$ с (условной) вероятностью не менее 2/3.

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

PostBQP = PP

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

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

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

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

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

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

Позволять п обозначают размер ввода, B = B(п) обозначают общее количество кубитов в схеме (входные, вспомогательные, выходные кубиты и кубиты после выбора), и грамм = грамм(п) обозначают общее количество ворот. я-й вентиль его переходной матрицей А^я (реальный унитарный ${displaystyle 2 ^ {B} imes 2 ^ {B}}$ матрица) и пусть начальное состояние будет |Икс> (дополненный нулями). потом ${displaystyle Psi = A ^ {G} A ^ {G-1} dotsb A ^ {2} A ^ {1} | xangle}$. Определять S₁ (соотв. S₀) как набор базисных состояний, соответствующих п = 1, Q = 1 (соотв. п = 1, Q = 0) и определим вероятности

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

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

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

Наш 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_ { альфа _ {1}}}$

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

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

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

Изготовление машины из полипропилена

Теперь мы предоставляем детальную реализацию нашего 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_ {альфа _ {3}, альфа _ {2}} ^ {2} A_ {альфа _ {2}, альфа _ {1}} ^ {1} x_ {альфа _ {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 _ {омега в S_ {0}} сумма _ {alpha, alpha '} Pi (A, omega, alpha, x) Pi (A, omega, alpha', x).}$

Мы определяем наши PP машина для

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

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

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

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

${displaystyle xin LLeftrightarrow # {rin {0,1} ^ {T} mid f (x, r) = 1} geq 2 ^ {T-1}}$

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

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

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

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

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

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

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

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

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

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

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

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

Анализ

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

В частности, обратите внимание ${displaystyle 2 ^ {- T}$ и давайте последовательно установить ${displaystyle eta / alpha}$ к каждому значению формы ${displaystyle 2 ^ {i}}$ за ${displaystyle -Tleq ileq T}$. Тогда элементарные вычисления показывают, что для одного из этих значений явероятность того, что измерение ${displaystyle | phi _ {2 ^ {i}} angle}$ в основе ${displaystyle {| + angle, | -angle}}$ дает ${displaystyle | + угол}$ по крайней мере ${displaystyle (3 + 2 {sqrt {2}}) / 6approx 0,971.}$

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

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

Подразумеваемое

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

Рекомендации