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

насколько мощным является класс PostBQP. Одна из первых вещей, о которой вы можете сказать, — это то, что, разумеется, PostBPP ⊆ PostBQP. То есть мы можем смоделировать классический компьютер с поствыбором. В другом направлении, мы имеем PostBQP ⊆ PP. Адлеман, Де Маррэ и Хуанг[159] доказали также, что BQP ⊆ PP. В этом доказательстве они, по существу, находят то, что физики называли бы фейнмановским интегралом по траектории, где вы суммируете по всем возможным вкладам в каждую из финальных амплитуд. Это просто большое PP-вычисление. На мой взгляд, Фейнман получил Нобелевскую премию по физике за то, что показал BQP ⊆ PP, хотя сам он это так не формулировал. Во всяком случае, это доказательство несложно обобщить на случай PostBQP ⊆ PP, поскольку для этого нужно просто ограничить суммирование теми траекториями, которые заканчиваются в одном из тех состояний, которые вы поствыбираете. Влияние всех остальных траекторий можно исключить, сделав так, чтобы они вносили равное число плюсов и минусов.

Можно ли смоделировать множественный поствыбор при помощи единственного поствыбора? Еще один серьезнейший вопрос. Ответ: да, можно. Мы приходим к этому при помощи так называемого принципа отложенного измерения, который гласит, что в любом квантовом вычислении мы можем считать без потери общности, что в конце есть лишь одно измерение. Можно смоделировать все остальные измерения при помощи вентилей управляемой инверсии, а затем просто не смотреть на кубиты, содержащие результаты измерения. То же можно сказать и о поствыборе. Все поствыборы можно придержать до конца.

Несколько лет назад я показал, что обратное утверждение тоже верно: PP ⊆ PostBQP[160]. В частности, это означает, что квантовый поствыбор — штука гораздо более мощная, чем классический поствыбор, что кажется удивительным. Классический поствыбор оставляет вас в полиномиальной иерархии, тогда как квантовый поствыбор выводит вас в классы вычислений, которые, как мы считаем, намного больше.

Пробежимся по доказательству. Итак, у нас есть некоторая булева функция f:{0, 1}n → {0, 1}, где f эффективно вычислима. Пусть s — число входных строк x, для которых f(x) = 1. Наша цель — решить, верно ли, что s ≥ 2n–1. Очевидно, что это PP-полная задача. Для простоты будем считать без потери общности, что s > 0. А теперь, используя стандартные квантовые вычислительные фокусы (которые я опущу), сравнительно легко подготовить однокубитное состояние вроде

Это означает также, что мы можем подготовить состояние

Это, по существу, условный вентиль Адамара, приложенный к |ψ〉, для некоторых действительных α и β, которые должны быть определены позже. Запишем в явном виде, чему равно H|ψ〉:

Так что теперь я хочу предположить, что мы берем представленное выше двухкубитное состояние и поствыбираем, что второй кубит должен быть 1, а затем смотрим, что при этом получается в первом кубите. Вы можете провести расчет и получить следующее состояние, которое зависит от выбранных ранее значений α и β:

Используя поствыбор, мы можем подготовить состояние такого вида для любых фиксированных α и β, каких нам заблагорассудится. Имея это в виду, как нам смоделировать PP? Мы будем продолжать подготовку различных вариантов этого состояния, изменяя отношение β/α по значениям {2—n, 2—n+1, …, 1/2, 1, 2, …, 2n}. Далее, возможны два случая: либо s < 2n–1, либо s ≥ 2n–1. Предположим, верно первое. Тогда s и 2n — 2s имеют один и тот же знак. Поскольку α и β — действительные числа, состояние |ψα,β〉 лежит на единичной окружности:

Если s < 2n–1, то при варьировании β/α состояние |ψα,β〉 всегда будет иметь положительную амплитуду как для |0〉, так и для |1〉 (она будет лежать в правом верхнем квадранте). Нетрудно убедиться в том, что в какой-то момент это состояние станет достаточно сбалансированным. То есть амплитуды |0〉 и |1〉 сойдутся в пределы постоянной разницы между ними, как показывает сплошной вектор на рисунке. Если мы будем и дальше измерять эти состояния в базисе {|+〉| — 〉}, то одно из них будет выдавать результат |+〉 с высокой вероятностью.

Во втором случае, где s ≥ 2n–1, амплитуда |1〉 никогда не бывает положительной, какими бы ни были α и β, тогда как амплитуда |0〉 всегда положительна. Следовательно, состояние всегда остается в правом нижнем квадранте. В этом случае при варьировании β/α в пределах полиномиального числа значений, |ψα,β〉 никогда не подходит близко к |+〉. Это вполне обнаружимая разница.

Итак, я написал об этом, считая, что нашел остроумное доказательство. Годом позже я сообразил, что существует теорема Бейгеля — Рейнгольда — Шпильмана[161], которая показала, что PP замкнут относительно пересечения. Это означает, что если два языка входят в PP, то и язык, полученный из них при помощи операции и, тоже входит в PP. Эта теорема решила задачу, остававшуюся открытой на протяжении 20 лет. Я заметил, что замкнутость PostBQP относительно пересечения тривиальна, потому что если вы хотите найти пересечение двух PostBQP-языков, вам достаточно просто прогнать соответствующие им PostBQP-машины и поствыбрать по условию того, что оба вычисления дадут корректный результат, а затем посмотреть, примут обе машины или нет. Чтобы остаться в пределах нужной ошибки, можно воспользоваться усилением.

Поскольку PostBQP тривиально замкнут относительно пересечения, он обеспечивает альтернативное доказательство замкнутости PP относительно пересечения, намного более простое, как мне кажется, чем первоначальное доказательство. Чтобы получить это более простое доказательство, нужно подумать о квантовом антропном поствыборе. Это напоминает язык программирования высокого уровня для построения «пороговых многочленов», необходимых Бейгелю, Рейнгольду и Шпильману для того, чтобы их теорема работала. Дело просто в том, что квантовая механика и поствыбор дают вам гораздо более интуитивный способ построения этих многочленов.

Позвольте мне привести еще одно интересное следствие теоремы PostBQP = PP, на этот раз для квантовых вычислений. Мы уже видели, что PostBPP = BPPpath входит в полиномиальную иерархию. С другой стороны, предположим, что PostBQP = PP входил бы в полиномиальную иерархию. Тогда PPP = P#P также входил бы в PH, но по теореме Тоды (что PH ⊆ P#P) это означало бы, что PH схлопнется до конечного уровня! Так что наш вывод таков: поскольку PH не схлопывается, постольку PostBQP строго больше, чем PostBPP. Да, и квантовый, и классический поствыбор —