Введение
В теории вычислительной сложности PostBQP - это класс сложности, состоящий из всех вычислительных задач, решаемых в полиномиальное время на квантовой машине Тьюринга с постселекцией и ограниченной ошибкой (в том смысле, что алгоритм правилен по крайней мере 2/3 времени на всех входах). Постселекция не считается особенностью, которой обладает реалистичный компьютер (даже квантовый), но, тем не менее, машины постселекции интересны с теоретической точки зрения. Удаление любой из двух основных особенностей (квантовость, постселекция) из PostBQP дает следующие два класса сложности, оба из которых являются подмножествами PostBQP: BQP такой же, как PostBQP, за исключением того, что без постселекции BPPpath такой же, как PostBQP, за исключением того, что вместо квантового алгоритм является классическим рандомизированным алгоритмом (с постселекцией). Добавление постселекции, кажется, делает квантовые машины Тьюринга намного более мощными: Скотт Ааронсон доказал, что PostBQP равен PP, классу, который, как полагают, относительно мощный, тогда как BQP не известен даже содержащему, казалось бы, меньший класс NP. Используя аналогичные методы, Ааронсон также доказал, что небольшие изменения в законах квантовых вычислений будут иметь значительные последствия. В качестве конкретных примеров, при любом из двух следующих изменений "новая" версия BQP будет равна PP: если мы расширим определение "квантовых ворот", чтобы включить не только единичные операции, но и линейные операции, или если вероятность измерения базового состояния будет пропорциональна вместо любого четного целого числа p > 2.
BQP is the same as PostBQP except without postselection
BPPpath is the same as PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection)
The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal PP:
if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or
if the probability of measuring a basis state was proportional to instead of for any even integer p > 2.
=
Скотт Ааронсон показал, что классы сложности \mathsf{PostBQP} (послевыбранное квантовое многочленное время с ограниченной ошибкой) и PP (вероятностное многочленное время) равны. Результат был значительным, потому что эта квантовая переформулировка вычислений \mathsf{PP} дала новое понимание и более простые доказательства свойств \mathsf{PP} Обычное определение семьи схем \mathsf{PostBQP} - это один с двумя выходными кубитами P (послевыбор) и Q (выход) с измерением P и Q в конце, так что вероятность измерения 1=P = 1 имеет ненулевую вероятность, условная вероятность Pr[Q = 1P = 1] ≥ 2/3, если вход x находится на языке, и Pr[Q = 0P = 1] ≥ 2/3, если вход x не находится на языке. По техническим причинам мы изменяем определение \mathsf{PostBQP} следующим образом: мы требуем, чтобы 1=Pr[P = 1] ≥ 2^(−n^(c)) для некоторой константы c в зависимости от семейства цепей. Обратите внимание, что этот выбор не влияет на основные свойства \mathsf{PostBQP} , а также можно показать, что любой вычисление, состоящий из типичных ворот (например, Хадамард, Тоффоли) имеет это свойство, когда 1=Pr[P = 1] > 0.
The usual definition of a \mathsf{PostBQP} circuit family is one with two outbit qubits P (postselection) and Q (output) with a single measurement of P and Q at the end such that the probability of measuring 1=P = 1 has nonzero probability, the conditional probability Pr[Q = 1|P = 1] ≥ 2/3 if the input x is in the language, and Pr[Q = 0|P = 1] ≥ 2/3 if the input x is not in the language. For technical reasons we tweak the definition of \mathsf{PostBQP} as follows: we require that 1=Pr[P = 1] ≥ 2^(−n^(c)) for some constant c depending on the circuit family. Note this choice does not affect the basic properties of \mathsf{PostBQP} , and also it can be shown that any computation consisting of typical gates (e. g. Hadamard, Toffoli) has this property whenever 1=Pr[P = 1] > 0.
Доказываю
Предположим, что нам дается семейство схем \mathsf{PostBQP} для решения языка L. Мы предполагаем без потери обобщенности (например, см. несущественные свойства квантовых компьютеров), что все ворота имеют матрицы перехода, которые представлены реальными числами, за счет добавления еще одного кубита. Пусть Ψ обозначает окончательное квантовое состояние цепи до выполнения измерения после выбора. Общая цель доказательства состоит в том, чтобы построить алгоритм \mathsf{PP} для решения L. Более конкретно, достаточно, чтобы L правильно сравнил амплитуду ψ в квадрате в состояниях с 1=Q = 1, P = 1 с амплитудой ψ в квадрате в состояниях с 1=Q = 0, P = 1, чтобы определить, какая из них больше. Ключевое понимание заключается в том, что сравнение этих амплитуд можно преобразовать в сравнение вероятности принятия машины с 1/2.
Матричный вид алгоритмов PostBQP
Пусть n обозначает размер входного интервала, 1=B = B(n) обозначает общее количество кубитов в цепи (входные, вспомогательные, выходные и постселекционные кубиты), а 1=G = G(n) обозначает общее количество ворот. Представьте i-й ворота по его матрице перехода Ai (реальной унитарной матрице) и пусть начальное состояние будет (наполненное нулями). Затем определите S1 (отвечает S0) - множество базовых состояний, соответствующих 1=P = 1, Q = 1 (относительно 1=P = 1, Q = 0) и определяет вероятности Определение \mathsf{PostBQP} обеспечивает, что либо или в зависимости от того, находится ли x в L или нет. Наша машина будет сравнивать и Для того, чтобы сделать это, мы расширяем определение матричного умножения: где сумма принимается за все списки G базисных векторов и может быть выражена как сумма парных произведений этих терминов. Интуитивно мы хотим спроектировать машину, вероятность принятия которой будет примерно такая же, как , так как тогда будет подразумевать, что вероятность принятия будет , а будет подразумевать, что вероятность принятия будет .
The definition of \mathsf{PostBQP} ensures that either or according to whether x is in L or not. Our \mathsf{PP} machine will compare and In order to do this, we expand the definition of matrix multiplication:
where the sum is taken over all lists of G basis vectors Now and can be expressed as a sum of pairwise products of these terms. Intuitively, we want to design a machine whose acceptance probability is something like , since then would imply that the acceptance probability is , while would imply that the acceptance probability is .
Техничность: мы можем предположить, что записи переходных матриц являются рациональными с знаменателем для некоторого многочлена f ((n).
Определение \mathsf{PostBQP} говорит нам, что если x находится в L, и что в противном случае Давайте заменим все записи A на ближайшую дроби с знаменателем для большого многочлена f (n), который мы в настоящее время описываем. Что будет использоваться позже, так это то, что новые значения удовлетворяют, если x находится в L, и если x не находится в L. Используя более раннее техническое предположение и анализируя, как меняется 1 норма вычислительного состояния, это считается удовлетворенным, если таким образом явно существует достаточно большое f, которое является многочленным в n.
Анализ
Пусть , который является центром , и пусть будет ортогональным к любой кубит в , когда измеряется в основе , дает значение меньше чем 1/2 времени . С другой стороны, если бы мы выбрали и, то измерение в основе дало бы значение все время. Поскольку мы не знаем s, мы также не знаем точное значение r*, но мы можем попробовать несколько (полиномиально много) различных значений в надежде получить одно, которое "близко" к r*. В частности, обратите внимание и давайте последовательно установить для каждого значения формы для Then элементарные расчеты показывают, что для одного из этих значений i вероятность того, что измерение в основе дает по крайней мере В целом, алгоритм \mathsf{PostBQP} выглядит следующим образом. Пусть k будет любой константой строго между 1/2 и Мы выполняем следующий эксперимент для каждого: построим и измерим в основе общее количество раз, когда C является константой. Если пропорция измерений больше k, то отклоняется. Если мы не отвергаем для любого i, принимаем. Границы Черноффа показывают, что для достаточно большой универсальной константы C мы правильно классифицируем х с вероятностью не менее 2/3. Обратите внимание , что этот алгоритм удовлетворяет техническому допущению , что общая вероятность после выбора не слишком мала: каждое отдельное измерение имеет вероятность после выбора , и поэтому общая вероятность .
Overall, the \mathsf{PostBQP} algorithm is as follows. Let k be any constant strictly between 1/2 and We do the following experiment for each : construct and measure in the basis a total of times where C is a constant. If the proportion of measurements is greater than k, then reject. If we don't reject for any i, accept. Chernoff bounds then show that for a sufficiently large universal constant C, we correctly classify x with probability at least 2/3. Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of has postselection probability and so the overall probability is .