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

По существу, доказатель подготавливает состояние, которое выглядит как Здесь r — последовательность всех случайных бит, которые вы использовали бы в классическом интерактивном протоколе. Скажем, мы берем классический протокол для решения задачи «co-NP или PSPACE» и хотим только смоделировать его при помощи трехступенчатого квантового протокола. Мы как бы сбиваем воедино все случайные биты, которые проверяющий использовал бы в протоколе, и берем суперпозицию по всем возможным подстановкам этих случайных бит. А что такое тогда q(r)? Это последовательность сообщений, которые доказатель должен был бы послать вам в ответ, если бы вы скормили ему случайные биты r. Далее, доказатель просто возьмет регистр q и второй регистр r и перешлет вам. Конечно, проверяющий может убедиться, что q(r) — правильная последовательность сообщений для заданного r. Но в чем же проблема? Почему этот протокол не годится?

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

вы можете просто повернуть его и убедиться в том, что при измерении в стандартном базисе получите 0 и 1 с примерно равной вероятностью. Точнее, если результат измерения в стандартном базисе окажется случайным, то вы примете с вероятностью единица; если результат окажется далек от случайного, то вы отвергнете с заметной вероятностью.

И все же проблема в том, что наше |r〉 запутано с кубитами |q(r) 〉. Поэтому мы не можем просто применить операции Адамара к |r〉: если бы мы это сделали, мы бы получили в ответ просто мусор. Оказывается, однако, что проверяющий может выбрать случайный проход i моделируемого протокола — пусть всего имеется n таких проходов — и затем попросить доказателя развычислить все, что следует за проходом i. Как только доказатель это сделает, он тем самым ликвидирует запутанность, и тогда проверяющий сможет убедиться, проведя измерение в базисе Адамара, что биты прохода i действительно случайны. Если же доказатель смошенничал на каком-то проходе и выслал неслучайные биты, это позволит проверяющему обнаружить это с вероятностью, обратно пропорциональной числу проходов. Наконец, вы можете повторить весь протокол параллельно полиномиальное число раз, чтобы повысить уверенность в результате. (Я пропускаю многие подробности — моя цель в данном случае лишь намекнуть, натолкнуть на мысль.)

Сравним квантовую ситуацию с положением в классическом мире. Там у вас есть только MA и AM: любой доказательный протокол общения между Артуром и Мерлином с большим постоянным числом проходов схлопывается до AM. Разрешив полиномиальное число проходов, мы поднимаемся до класса IP (равному PSPACE). В квантовом мире у вас есть QMA, QAM, а еще QMAM, который есть то же самое, что QIP = PSPACE. Есть и еще один класс, QIP [2], который отличается от QAM тем, что Артур может переслать Мерлину любую произвольную строку (или даже квантовое состояние) вместо случайной строки. В классическом случае AM и IP [2] — это одно и то же, но в квантовом случае мы этого не знаем.

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

18. Поиграем с антропным принципом[152]

Это глава об антропном принципе и о том, как можно применить байесовские рассуждения там, где приходится рассуждать о вероятности собственного существования, что кажется весьма странным вопросом. Однако это забавный вопрос — можно сказать, что это вопрос, для которого намного проще сформировать мнение, чем получить результат. Но мы можем попытаться по крайней мере прояснить некоторые темы; кроме того, есть все же кое-какие интересные результаты, которые мы можем получить.

Существует центральное положение, вокруг которого многие из тех, кто склонен к рациональности, по идее, должны строить свою жизнь, хотя, как правило, и не делают этого на практике. Это теорема Байеса.

Если вы говорите с философом, то это зачастую единственный математический факт, который ему известен. (Шутка!) Теорема Байеса как таковая не вызывает совершенно никаких возражений. Она говорит о том, как можно уточнить вероятность того, что гипотеза H истинна, при наличии данных о событии E.

Множитель P [E|H] описывает ваши шансы увидеть событие E в случае, если гипотеза H верна. Остальные множители справа, P [H] и P [E], похитрее. Первый из них описывает вероятность того, что гипотеза верна, вне зависимости от каких бы то ни было других событий, а второе описывает вероятность события E, усредненное по всем возможным гипотезам (и взвешенное в соответствии с вероятностями гипотез). Здесь вы заранее предполагаете, что такие вероятности существуют, иными словами, что имеет смысл говорить о том, что байесисты называют априорной информацией. Если вы только что народившийся на свет младенец, вы можете прикинуть, что существует какая-то вероятность того, что вы живете на третьей планете местной звезды, другая вероятность — что вы живете на четвертой планете и т. п. Это и называется априорной информацией: ваши представления о чем-то до того, как вы познакомитесь хоть с какими-то данными об этом. Вы уже поняли, что это понятие, возможно, немножко выдуманное, но если считать, что такое априорное мнение у вас имеется, то теорема Байеса скажет вам о том, как уточнить это мнение при появлении новых данных.

Доказательство этой теоремы тривиально. Умножаем обе стороны уравнения на P[E] и получаем P[H|E]P[E] = P[E|H]P[H]. Это очевидно верно, поскольку обе стороны равны вероятности события и гипотезы вместе.

Таким образом, если вы не видите никакой возможности оспорить теорему Байеса, то я хочу заставить вас