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

воронов и посмотреть, все ли они черные. Более современный подход: оглядеться вокруг, посмотреть на все нечерные объекты в комнате и обратить внимание на то, что все эти объекты не являются воронами. Чем дальше, тем больше я буду таким образом убеждаться, что все нечерные объекты не являются воронами или, что эквивалентно, что все вороны черные. Могу ли я таким передовым способом стать лидером в области орнитологии?

Если вы ответите: «Сидя в офисе, вы не получите случайной выборки нечерных объектов», — то я замечу, что вне офиса я также не получу случайной выборки всех воронов.

Вот кое-что, косвенно связанное с нашей задачей, о чем она мне напомнила: есть игра, в которой вам дают четыре карты, на каждой из которых, по априорному условию, с одной стороны имеется буква, а с другой — число. Если вы видите на картах то, что изображено на рисунке, то какую карту вам нужно перевернуть, чтобы проверить правило: все карты с буквой K на одной стороне имеют на другой число 3?

Очевидно, если вы зададите людям этот вопрос, огромное большинство ответит на него неверно. Чтобы проверить правило K ⇒ 3, нужно перевернуть карты K и 1, и только их. С другой стороны, вы можете задать людям совершенно эквивалентную задачку, в которой вам — вышибале в баре — требуется узнать, пьет ли кто-нибудь несовершеннолетний (до 21 года в США или до 19 лет в Канаде) алкоголь; вам известно, что кто-то в баре пьет, кто-то нет, кому-то больше 21 года, кому-то меньше. В этом сценарии, как ни забавно, большинство людей отвечает верно. Нужно опросить тех, кто пьет алкоголь, и несовершеннолетних. Задачка в точности та же, что с картами, но если вы формулируете ее в абстрактных терминах, многие скажут, к примеру, что нужно перевернуть 3 и Q, что неверно. Так что у человека, судя по всему, имеется встроенная способность рассуждать логически о социальных ситуациях, а вот способности применять ту же логику к абстрактным математическим задачам его приходится долго и нудно учить[128].

В любом случае смысл в том, что на свете намного, намного больше нечерных объектов, чем воронов, так что если бы существовала пара (ворон, нечерный), то нам было бы гораздо проще найти ее, выбирая случайные образцы воронов, чем образцы нечерных объектов. Таким образом, если мы делаем выборку воронов и не находим среди них нечерного ворона, мы можем быть намного сильнее уверены в верности утверждения, что «все вороны черные», потому что вероятность опровергнуть нашу гипотезу при помощи выборки воронов намного выше.

Интерактивные доказательства

«Интерактивные доказательства» являются центральными объектами исследований в теоретической информатике и криптографии с 1980-х гг. Поскольку в этой книге речь идет в основном о компьютерных вычислениях, я хотел бы начать обсуждение интерактивных доказательств нестандартно — с вопроса: Можно ли эффективно имитировать квантовые компьютеры при помощи классических?

Некоторое время назад я беседовал с Эдом Фредкином, и он высказал уверенность в том, что вся наша Вселенная есть классический компьютер и, соответственно, все можно смоделировать классически. Но вместо того чтобы сказать далее, что квантовые вычисления невозможны, он поворачивает рассуждения в другом, очень интересном направлении и говорит, что класс BQP должен быть равен P. Хотя у нас имеются алгоритмы разложения на множители для квантовых компьютеров, более быстрые, чем известные классические алгоритмы, это не означает, что не существует быстрого классического алгоритма разложения на множители, о котором мы просто не знаем. С другой стороны, Дэвид Дойч выдвигает аргумент, о котором мы уже говорили несколько раз: если алгоритм Шора не задействует пресловутые «параллельные вселенные», то как он раскладывает число на множители?[129] Где были найдены простые делители числа, если при этом не использовалось экспоненциальное множество вселенных? Мне кажется, возразить Дойчу можно так (разумеется, это не единственное возражение): он априорно считает, что эффективной классической имитации не существует. Мы полагаем, что не существует способа, при помощи которого Природа могла бы реализовать те же вычисления при помощи полиномиальных классических средств, но точно мы этого не знаем. Доказать это мы не можем.

Почему мы не можем это доказать? Принципиальный момент в том, что если можно было бы доказать, что P ≠ BQP, то при этом было бы доказано также, что P ≠ PSPACE. Физики могут считать, что неравенство этих классов очевидно и вообще не требует доказательства, но это другой вопрос… Что до попыток пойти в обратном направлении и доказать P = BQP, то мне кажется, что такие попытки делались неоднократно. Не знаю, стоит ли говорить об этом на лекции, но я тоже посвятил этому несколько дней. По крайней мере, было бы хорошо поместить BQP в АМ или в полиномиальную иерархию — получить хотя бы предварительный результат. К несчастью, мне кажется, что мы пока просто недостаточно хорошо понимаем эффективные вычисления, чтобы отвечать на такие вопросы, даже если оставить в стороне квантовый аспект.

Вот вопрос: если P ≠ BQP, P ≠ NP и т. п., то почему никто не может доказать это? Объяснить это пытались несколькими способами. Один из них — релятивизация. Мы можем говорить о том, чтобы дать P-компьютеру и BQP-компьютеру доступ к одному и тому же оракулу. То есть снабдить их одной и той же функцией, которую они смогут вычислять за один вычислительный шаг. Тогда должен, по идее, существовать оракул, делающий их равными, и другой оракул, делающий их неравными. Роль оракула, делающего их равными, к примеру, мог бы выполнять просто PSPACE-оракул, который как бы прослаивает все и просто делает все равным PSPACE. Роль оракула, который делает их неравными, мог бы играть оракул к задаче Саймона или к какой-то задаче нахождения периода, которую квантовый компьютер решить может, а классический — нет.

Если два класса совпадают, то интуитивно непонятно, как придание большей мощности может сделать их разными? Главное здесь — понять, что когда мы снабжаем класс оракулом, мы действуем не на класс как таковой. Мы действуем на определение класса. Вот вам пример: несмотря на то что мы считаем P = BPP в реальном мире, очень легко построить оракул O, такой, что PO ≠ BPPO. Ясно, что если бы мы реально воздействовали на классы, то одинаковое воздействие на равные классы дало бы столь же равные результаты. Но на самом деле мы делаем не это, и, возможно, способ записи