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

Итак, зададим очевидный следующий вопрос: существует ли нижняя оценка сложности схемы, позволяющая обойти все три барьера одновременно — и релятивизацию, и алгебраизацию, и естественные доказательства? По-моему, первый убедительный пример такой нижней оценки появился совсем недавно, в 2010 г., вместе с прорывным результатом Райана Уильямса[147], который гласит, что NEXP ⊄ ACC0. Здесь NEXP — недетерминистическое экспоненциальное время, тогда как ACC0 — легкое расширение AC0 с целью разрешить модулярную арифметику по любой базе (не забывайте, что мы уже знали бы нижнюю оценку, если бы AC0 был расширен до арифметики по модулю какого-то конкретного простого числа). Вы могли бы заметить, что этот результат кажется довольно жалким в сравнении с теми утверждениями, которые мы считаем истинными! Тем не менее это настоящая веха на нашем пути, потому что здесь удалось обойти все три известных барьера (строго говоря, мы не знаем, применим ли барьер естественного доказательства к ACC0, но если применим, то доказательство Уильямса его обходит!). Чтобы этого добиться, Уильямсу пришлось использовать «кухонную раковину» — диагонализацию, информацию от интерактивных доказательств и различные новые и старые результаты, посвященные нетривиальным структурам в функциях ACC0.

Существует ли четвертый барьер, который не в состоянии обойти даже новые результаты Уильямса? Я не знаю, спросите чего попроще! Общее правило гласит, что прежде чем думать о барьерах, стоящих перед какой-то заданной методикой, я бы сказал, что нам нужно по крайней мере два успешных примера приложения этой методики, примерно по той же причине, по какой нам нужно по крайней мере две точки, чтобы провести прямую.

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

Многие из нас (втайне?) боятся, что для дальнейшего прогресса в вопросе о нижних оценках сложности схем будет необходимо на порядки повысить математическую сложность в этой области информатики. Во всяком случае, это главное утверждение программы Кетана Мулмулея «Геометрическая теория сложности»[148], в которой с нижними оценками схем пытаются разобраться при помощи алгебраической геометрии, теории представлений и, кажется, всех иных средств, о которых только написаны учебники. Геометрическая теория сложности — сама по себе отдельная большая тема, и даже попытка объяснить ее увела бы меня слишком далеко в сторону. Просто скажу, что мне лично нравится называть геометрическую теорию сложности «теорией струн теоретической информатики»: с одной стороны, она сумела установить такие поразительные математические связи, что достаточно только взглянуть на них — и чувствуешь, что эта программа просто обязана быть на верном пути. С другой стороны, если судить об этой программе по тому, сколько ответов она сумела дать на вопросы, которыми изначально планировала заниматься, — вопросы, внешние по отношению к самой программе, — то пока первоначальные надежды не оправдываются.

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

Пока нам приходится ждать продвижения в вопросе нижних оценок классических схем, позвольте мне вернуться назад и рассказать вам кое-что о квантовых системах интерактивных доказательств. Первое, мне кажется, что нужно сказать по этому поводу, — что даже результаты по нижним оценкам классических систем интерактивных доказательств — те, что мы уже видели, — можно использовать для получения нижних оценок квантовой схемы. Так, к примеру, слегка изменив наше доказательство того факта, что PP не имеет схем размера nk, можно доказать, что PP не имеет даже квантовых схем размера nk. Хорошо, но это еще цветочки. Давайте попытаемся добавить квантовый аспект к чему-то еще и получить иной ответ, нежели в классике.

Мы можем определить класс сложности QIP (Quantum Interactive Proofs). Это то же, что IP, но здесь вы — квантовый полиномиальный по времени проверятель, и вместо того чтобы обмениваться с доказателем классическими сообщениями, вы можете обмениваться сообщениями квантовыми. К примеру, вы могли бы послать доказателю половину ЭПР-пары, а вторую половину оставить себе — или поиграть с ним в какие-то другие подобные игры.

Конечно, этот класс по крайней мере столь же мощен, как IP, потому что при желании вы могли бы просто ограничиться классическими сообщениями. Поскольку IP = PSPACE, мы знаем также, что QIP должен быть по крайней мере столь же велик, как PSPACE. Воспользовавшись доводами полуопределенного программирования, Китаев и Ватрус[149] также доказали достаточно рано, что QIP ⊆ EXP. В 2006 г., когда я впервые писал эту главу, мы больше ничего, по существу, о классе QIP не знали. Но в 2009 г. Джейн, Цзи, Упадхиай и Ватрус совершили прорыв: они показали[150], что QIP можно смоделировать даже в PSPACE, и этому QIP = IP = PSPACE. Так что в конечном итоге оказалось, что квантовые интерактивные системы доказательства обладают ровно такой же мощностью, как и классические. Забавно, но в классическом случае самым удивительным было то, что эти системы могут имитировать PSPACE, тогда как в квантовом случае больше всего удивляло, что PSPACE может имитировать их!

Итак, существует ли какой-нибудь аспект, в котором квантовые интерактивные системы доказательства интересно отличаются от классических? Да, есть поразительный факт, который был доказан Китаевым и Ватрусом[151] и сыграл важнейшую роль в доказательстве теоремы QIP = PSPACE. Любой квантовый интерактивный протокол может быть сымитирован протоколом, реализуемым в три круга. В классическом случае нам пришлось отыгрывать ситуацию с Румпельштильцхеном: мы задавали доказателю один вопрос за другим, пока наконец не поймали его на лжи. Нам пришлось задать доказателю полиномиальное количество вопросов. Но в квантовом случае в этом больше нет необходимости. Доказатель посылает вам сообщение, вы посылаете ему ответ, затем доказатель посылает вам еще одно сообщении — и все. Это все, что вам может понадобиться.

Мы не будем здесь доказывать, почему это так, но я могу слегка намекнуть.