Читать книгу Квантовые вычисления со времен Демокрита - Скотт Ааронсон - Страница 5

Просматривая рукопись перед публикацией в виде книги, я больше всего удивился тому, как много всего произошло в этих областях между моментом, когда я читал этот курс впервые (2006 г.), и «настоящим» моментом (2013 г.). Эта книга замышлялась как посвященная глубоким вопросам, древним, как физика и философия, или по крайней мере возникшим одновременно с квантовой механикой и информатикой почти столетие назад. На повседневном уровне никак не ощущается, чтобы в дискуссии по этим вопросам что-то менялось. Поэтому необходимость существенно перерабатывать и расширять лекции по прошествии всего лишь шести лет стала для меня невыразимо приятной обязанностью.

Чтобы проиллюстрировать развитие вещей, позвольте мне привести неполный список достижений, о которых пойдет речь в книге, но о которых не могла идти речь на лекциях 2006 г. по той простой причине, что события эти на тот момент еще не произошли. Компьютер Watson фирмы IBM выиграл у чемпиона мира по «Своей игре» Кена Дженнингса, вынудив меня дополнить разговор об ИИ новым примером (см. главу 4), совершенно иным по характеру, чем предыдущие, такие как ELIZA и Deep Blue. Вирджиния Василевская-Уильямс, опираясь на работы Эндрю Стозерса, нашла способ перемножить две матрицы n × n с использованием всего O(n^2,373) шагов, слегка превзойдя при этом результат Копперсмита и Винограда O(n^2,376), который держался так долго, что число 2,376 начало уже восприниматься как природная константа (см. главу 5).

Достаточно серьезные события произошли в области криптографии на решетках, которая представляется самой перспективной базой для создания систем шифрования с открытым ключом, устойчивых даже против квантовых компьютеров (см. главу 3). Следует особо отметить, что Крейг Джентри смог решить задачу, которая никому не давалась 30 лет: он использовал решетки, чтобы предложить первые полностью гомоморфные криптосистемы. Эти системы позволяют клиенту доверить любые вычисления незащищенному серверу, при этом на сервер передаются зашифрованные входные данные, а обратно получаются зашифрованные результаты, и только сам клиент может расшифровать результат и удостовериться в его подлинности; сервер же не получает никакой информации о том, что именно ему поручили считать.

Если говорить об основах квантовой механики, Чирибелла с соавторами (см. главу 9) привели новый аргумент в пользу того, «почему» в квантовой механике должны действовать именно такие правила. А именно: они доказали, что только эти правила совместимы с некоторыми общими аксиомами теории вероятностей и одновременно с немного загадочной аксиомой о том, что «любые смешанные состояния могут быть очищены», то есть всякий раз в том случае, когда мы знаем о физической системе A не все, что можно знать, наше незнание должно полностью объясняться предположением о корреляциях между A и некоторой далекой системой B, такой, что мы должны иметь полные данные об объединенной системе AB.

В теории квантовых вычислений задача Бернштейна – Вазирани о «рекурсивной выборке Фурье», которой в лекциях 2006 г. я посвятил довольно много времени, была вытеснена моей задачей о «проверке коэффициентов Фурье» (см. главу 10). Задача Бернштейна – Вазирани осталась в истории как первая когда-либо предложенная задача с черным ящиком, которую квантовый компьютер доказуемо может решить сверхполиномиально быстрее, чем классический вероятностный компьютер, и, следовательно, как важный предшественник прорывных открытий Саймона и Шора. Но сегодня, если нам потребуется кандидат на роль задачи класса BQP/PH, иными словами, задачи, которую квантовый компьютер может решить с легкостью, но которая вообще не входит в классическую «полиномиальную иерархию», то представляется, что «проверка коэффициентов Фурье» во всех отношениях превосходит «рекурсивную выборку Фурье».

Несколько задач, которые излагались в моих лекциях 2006 г. как нерешенные, успели с тех пор изменить свой статус. Так, мы с Эндрю Друкером показали, что класс BQP/qpoly входит в класс QMA/poly (к тому же доказательство получилось релятивизирующее), опровергнув тем самым мою гипотезу о том, что эти классы должны различаться по оракулам (см. главу 14). Кроме того, произошел справедливо отмеченный прорыв в теории квантовых вычислений: Джайн с соавторами доказал, что QIP = PSPACE (см. главу 17); это означает, что квантовые интерактивные системы доказательства не мощнее классических. В этом случае я по крайней мере угадал правильный ответ!

(На самом деле был еще один прорыв в исследовании квантовых интерактивных систем доказательства, о котором я не буду рассказывать в этой книге. Недавно мой постдок Томас Видик вместе с Цуёси Ито[8] показал, что NEXP ⊆ MIP*; это означает, что любую интерактивную систему доказательства с многими доказателями можно «привить» против того, чтобы эти доказатели втайне скоординировали свои отклики посредством квантовой запутанности.)

В главе 20 этой книги обсуждается предложенная Дэвидом Дойчем модель квантовой механики в присутствии замкнутых времениподобных траекторий, а также мой и Джона Ватруса новый (на тот момент) вывод о том, что модель Дойча обеспечивает в точности вычислительную мощность PSPACE. (Отсюда, в частности, следует, что путешествующие во времени квантовые компьютеры оказались бы не более мощными, чем классические компьютеры того же назначения, если вас почему-то интересовал этот вопрос.) Однако после 2006 г. вышли новые важные статьи, в которых подвергаются сомнению предположения, положенные в основу модели Дойча, и предложены альтернативные модели, что, как правило, ведет к вычислительной мощности меньшей, чем PSPACE. К примеру, одна из моделей, предложенная Ллойдом с соавторами, «всего лишь» позволит путешественнику во времени решить все задачи класса PP! Об этих достижениях речь пойдет в главе 20.

А что с нижними оценками сложности схемы (для специалистов по теоретической информатике это, по существу, кодовое слово, обозначающее «попытку доказать P ≠ NP», точно так же как для физиков «замкнутые времени подобные траектории» – кодовое слово для обозначения путешествий во времени)? Рад сообщить, что и здесь после 2006 г. имеются интересные подвижки – безусловно, более серьезные, чем можно было тогда ожидать. В качестве примера скажу, что Рахул Сантханам при помощи интерактивных методик доказательства получил нерелятивизирующий результат, согласно которому класс PromiseMA не имеет схем какого бы то ни было фиксированного полиномиального размера (см. главу 17). Результат Сантханама, в частности, побудил меня и Ави Вигдерсона в 2007 г. сформулировать теорему о барьере алгебраизации (см. там же) – обобщение теоремы о барьере релятивизации Бейкера, Гилла и Соловея, сформулированной еще в 1970-е гг. (см. так же главу 17). Алгебраизация объясняет, почему методики интерактивного доказательства в попытке доказать P ≠ NP позволяют нам лишь дойти до определенного предела и не более того – к примеру, почему эти методики привели к сверхлинейной нижней оценке сложности схемы для класса PromiseMA, но не для класса NP, который всего лишь «чуть ниже его». Мы поставили задачу разработки новых методик поиска нижней оценки сложности схемы, которые позволяли бы убедительно обойти барьер алгебраизации. Эту задачу решил в 2010 г. Райан Уильямс своим прорывным доказательством того, что NEXP ⊄ ACC⁰ (речь об этом идет в главе 17).

Конечно, даже интереснейший результат Уильямса чертовски далек еще от доказательства P ≠ NP. Но в последние шесть лет наблюдается еще и растущий интерес – и, соответственно, прогресс – к программе создания геометрической теории сложности Кетана Мулмулея (см. главу 17); теория эта играет для доказательства P ≠ NP почти в точности ту же роль, что теория струн в физике для цели создания Теории Всего. То есть, если говорить о конкретных результатах, программа геометрической теории сложности пока даже отдаленно не приблизилась к конечному результату, и даже самые рьяные ее сторонники предсказывают несколько десятилетий кропотливой работы, тогда как остальных просто отпугивает ее математическая сложность. В активе этой программы две вещи: во-первых, то, что она создает математические связи, «слишком глубокие и поразительные, чтобы их можно было считать простым совпадением», и во-вторых, то, что (хотя так считают далеко не все!) на безрыбье и рак рыба и что это единственный реальный претендент на успех, имеющий хоть какие-то шансы.

Позвольте мне упомянуть еще три открытия, сделанных после 2006 г. и важных для содержания этой книги.

В 2011 г. мы с Алексом Архиповым предложили «бозонную выборку» (см. главу 18) – рудиментарную, почти наверняка не универсальную модель квантовых вычислений с участием невзаимодействующих фотонов, которая совсем недавно была продемонстрирована в небольшом масштабе. Уверенность в том, что бозонную выборку трудно смоделировать на классическом компьютере, кажется, даже выше, чем в том, что трудно смоделировать (к примеру) алгоритм Шора разложения на множители.

В 2012 г. Умеш Вазирани и Томас Видик, опираясь на более ранние работы Пиронио с соавторами, показали, как можно использовать нарушения неравенства Белла для достижения экспоненциального расширения случайности (см. главу 19), то есть превращения n случайных бит в 2n бит, которые гарантированно будут почти совершенно случайными, если только Природа не воспользуется сверхсветовой связью, чтобы их изменить.

Тем временем дебаты об «информационном парадоксе черной дыры» – то есть об очевидном конфликте между принципами квантовой механики и локальностью пространства-времени, когда биты и кубиты падают в черную дыру, – развивались с 2006 г. в новых направлениях. Самыми, возможно, важными достижениями здесь стали возросшая популярность и подробность модели черной дыры как «пушистого клубка», выдвинутой Самиром Матхуром, и спорное утверждение Алмхейри с соавторами о том, что наблюдатель, падающий в черную дыру, никогда даже не приблизится к сингулярности, а встретит на своем пути «огненную стену» и сгорит на горизонте событий. Я в меру своих сил расскажу об этих достижениях в главе 22.

Несколько дополнений и изменений в книге объясняются не какими-то новыми открытиями или аргументами, а просто тем, что я (ну надо же!) изменил мнение о чем-то. Один из примеров – мое отношение к аргументам Джона Сёрла и Роджера Пенроуза против «сильного искусственного интеллекта». Как вы увидите в главах 4 и 11, я по-прежнему считаю, что Сёрл и Пенроуз неправы в принципиальных моментах, причем Сёрл в большей степени, нежели Пенроуз. Но я, перечитав свой текст 2006 г., посвященный причинам, по которым они неправы, испытал неприятное чувство. Мне не понравился мой легкомысленный тон, моя готовность посмеяться над этими знаменитыми учеными, пытающимися завернуться в логический крендель в отчаянной и очевидно обреченной попытке обосновать человеческую уникальность. В результате я пребывал в ленивой уверенности, что все вокруг заранее согласны со мной: что для (по большей части) физиков и специалистов по информатике попросту самоочевидно, что человеческий мозг есть не что иное, как «горячая и влажная машина Тьюринга», – и считал, что глупо тратить лекционное время на такой давно решенный вопрос. С тех пор, кажется, я лучше проникся невероятной сложностью этих вопросов, и в частности необходимостью выдвигать такие аргументы, которые действовали бы на людей отличных от моей философских позиций.

С надеждой на то, что в 2020 г. эта книга будет так же сильно нуждаться в переработке, как нуждаются в ней сегодня, в 2013 г., конспекты лекций 2006 года,

Скотт Ааронсон, Кембридж (штат Массачусетс), январь 2013 г.