Квантовые вычисления со времен Демокрита - Скотт Ааронсон

возможных решений плюс это фиктивное решение, которое выбирается с какой-то крохотной вероятностью вроде 2–2n. Если выбирается это фиктивное решение, то делать ничего не надо. Если нет, то вы кончаете с собой в том и только том случае, если выбранное решение вас не удовлетворяет. При условии, что решения не существует, а вы живы, получается, что вы выбрали фиктивное решение. Иначе если решение существует, то вы почти наверняка выбрали удовлетворительное решение, опять же при условии, что вы живы.

Естественно, на основании этого принципа можно определить класс сложности BPPpath. Вспомните определение BPP: класс задач, решаемых при помощи вероятностного полиномиального по времени алгоритма с ограниченной ошибкой. То есть если ответ на задачу «да», по крайней мере 2/3 траекторий BPP-машины должны принимать, тогда как если ответ «нет», то принимать должны не более 1/3 траекторий. BPPpath — то же самое, за исключением того, что все вычислительные траектории могут иметь разную длину[158]. Все длины должны быть полиномиальными, но могут различаться между собой.

Вот в чем смысл: в классе BPPpath, если какой-то выбор ведет к большему числу различных траекторий, то он и просчитывается большее число раз. Скажем, к примеру, что в 2n — 1 ветвях мы просто принимаем или отвергаем, то есть машина просто останавливается, но в одной ветви мы будем бросать дополнительные монетки и делать что-то еще. В BPPpath мы можем сделать так, чтобы одна ветвь абсолютно доминировала над остальными. Такой пример показан на рисунке ниже: предположим, мы хотим, чтобы ветвь, окрашенная в серый цвет, доминировала над всеми остальными. Тогда мы можем подвесить целое дерево на эту траекторию, и она будет доминировать над траекториями, которые нам не нужны (окрашены в черный цвет).

Простое рассуждение показывает, что BPPpath эквивалентно классу, который я назову PostBPP (BPP с поствыбором). PostBPP — это опять же множество задач, решаемых полиномиальным по времени вероятностным алгоритмом, где условия приема у вас опять же определяются вероятностями 2/3 и 1/3, но здесь, если вам не нравится выборка случайных битов, вы можете просто покончить с собой. Можно в качестве условия взять такой выбор случайных битов, при котором вы останетесь живы. Физики называют это поствыбором. Вы можете поствыбрать получение случайных битов с каким-нибудь очень специфическим свойством. При условии наличия этого свойства, ответ «да» должен вызывать принятие у 2/3 траекторий, а ответ «нет» — не более чем у 1/3 траекторий.

Если вам нужно формальное определение, то PostBPP — это класс всех языков L, для которых существуют полиномиальные по времени машины Тьюринга A и B (из них A решает, принять или отвергнуть, а B делает постселекцию), такие, что

1. Для любого x ∈ L, Prr[A(x, r)B(x, r)] ≥ 2/3;

2. Для любого x ∉ L, Prr[A(x, r)B(x, r)] ≤ 1/3.

Здесь x — входная строка, а r — строка, которая устанавливает флаг постселекции. В качестве технического условия мы требуем также Pr[B(x, r)] > 0.

Видите, почему это эквивалентно BPPpath?

Во-первых, вот доказательство того, что PostBPP ⊆ BPPpath. Для заданного алгоритма с поствыбором вы делаете множество случайных выборов, и если они вам нравятся, вы делаете еще множество случайных выборов, и этих траекторий становится намного больше тех, в которых случайные биты вам не понравились.

А как насчет обратного утверждения? BPPpath ⊆ PostBPP?

Суть в том, что в BPPpath мы имеем то самое дерево траекторий разной длины. Мы можем дополнить его, чтобы получилось сбалансированное двоичное дерево. Затем мы могли бы воспользоваться поствыбором, чтобы придать всем этим призрачным траекториям устраивающие нас более низкие вероятности, чем имеют траектории истинные, и таким образом смоделировать BPPpath в PostBPP.

Теперь, когда мы знаем, что PostBPP = BPPpath, мы можем задать вопрос о том, насколько велик класс BPPpath. Согласно приведенным ранее рассуждениям, NP ⊆ BPPpath.

С другой стороны, верно ли NP = BPPpath? Конечно, даже если это так, показать это будет трудно. Одна из причин состоит в том, что BPPpath замкнут относительно дополнения. Еще одна причина в том, что он включает в себя BPP. Более того, можно показать, что BPPpath содержит также MA и P||NP (P с параллельными запросами некоторому NP-оракулу, то есть запросами, которые не могут зависеть от ответов на предыдущие запросы). Я оставлю это вам в качестве упражнения. В другом направлении, можно показать, что BPPpath содержится в BPP||NP и, соответственно, в полиномиальной иерархии. Таким образом, согласно гипотезе дерандомизации получаем, что антропный принцип дает нам ту же вычислительную мощность, что и P||NP.

А как насчет верхней оценки? Покажем, что BPPpath ⊆ PP. Принятие решения о том, что делать с входным сигналом — принять или отвергнуть, напоминает экспоненциальную задачу суммирования. Вы можете сказать, что каждая из траекторий, которая является фиктивной, вносит оба варианта — и принятие, и непринятие, тогда как каждая из принимающих траекторий вносит два принятия, а каждая из отвергающих траекторий — два непринятия. В таком случае достаточно просто спросить, чего получается больше — принятий или непринятий. Тем самым мы промоделировали его в PP.

Разумеется, ничто из сказанного не было бы полным, если бы мы не рассмотрели квантовый поствыбор. Именно этим я хотел завершить этот разговор. По прямой аналогии с PostBPP, мы можем определить PostBQP как класс задач принятия решений, решаемых за полиномиальное время квантовым компьютером с возможностью поствыбора. Я имею в виду, что это класс задач, в которых вы должны проводить полиномиальное по времени квантовое вычисление, а затем некоторое измерение. Если вам не нравится результат измерения, вы кончаете с собой и выставляете в качестве условия то, что вы должны остаться в живых.

В PostBQP нам придется определить кое-что немного иначе, потому что там нет аналога строки r. Вместо этого скажем, что следует выполнить некоторое полиномиальное по времени квантовое вычисление, провести измерение, принимающее с вероятностью большей нуля, а затем оговорить условие по результатам этого измерения. Наконец, следует провести следующее измерение редуцированного квантового состояния, которое скажет вам, принять или отвергнуть. Если ответ на задачу «да», то второе измерение должно принимать с вероятностью по крайней мере 2/3 при условии, что первое измерение принимает. Аналогично если ответ на задачу «нет», то второе измерение должно принимать с вероятностью не более 1/3 при условии, что первое измерение принимает.

Далее мы можем спросить,