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

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

Прежде чем отправиться в этот квест, нам необходимо вооружиться кое-какими классами сложности. Знаю, знаю: классы сложности у нас уже есть, но кажутся сплошной эзотерикой. Так исторически сложилось — может быть, к сожалению, — что мы пользуемся для изложения своих идей аббревиатурами, а не какими-нибудь эротическими названиями, вроде «черной дыры», «кварка» или «суперсимметрии», как это делают физики. Это как в истории про заключенных, которые, вместо того чтобы рассказывать анекдоты, называют лишь их номера. Один произносит: «37», — и все с хохотом катаются по полу, а затем кто-то другой произносит: «22», — но никто не смеется, потому что все дело в том, как это сказано. Есть потрясающие, головоломные тайны, связанные с истиной, доказательством, компьютерами, физикой и пределами познаваемого, — а мы для краткости ссылки прячем их за невнятными последовательностями из трех или четырех заглавных букв. Возможно, нам не стоило этого делать.

Но мы все равно будем так поступать и начнем с класса QMA (квантовый Мерлин-Артур) — квантового обобщения MA. QMA можно рассматривать как множество истин, таких, что если у вас есть квантовый компьютер, то вы можете убедиться в ответе, если получите некое квантовое состояние. Более формально, это множество задач, принимающих полиномиальный по времени квантовый алгоритм Q, такой, что для любой входной строки x верно следующее.

• Если при входной строке x ответ на задачу будет «да», то существует некоторое квантовое состояние |ϕ〉 из полиномиального числа кубитов, такого, что Q принимает |x〉|ϕ〉 с вероятностью больше 2/3.

• Если при входе x ответ на задачу будет «нет», то не существует никакого полиномиального по размеру квантового состояния |ϕ〉, такого, что Q принимает |x〉|ϕ〉 с вероятностью больше 1/3.

Я имею в виду, что число кубитов в |ϕ〉 должно быть ограничено полиномом от n — длины входной строки x. Невозможно получить состояние из 2n кубитов. Если бы это было возможно, наша задача стала бы тривиальной.

Мы хотим, чтобы существовало квантовое состояние разумного размера, способное убедить вас в ответе «да». Таким образом, если ответ «да», то существует состояние, которое вас убеждает, а когда ответ «нет», то и состояния такого нет. QMA — своего рода квантовый аналог NP. Вспомните, что у нас есть теорема Кука — Левина, которая гласит, что задача выполнимости булевых формул (SAT) является NP-полной. Существует и квантовая теорема Кука — Левина — замечательное название, если учесть, что и Кук, и Левин очень скептически относятся к квантовым вычислениям (хотя Левин намного больший скептик, чем Кук). Квантовая теорема Кука — Левина гласит, что мы можем определить квантовую версию задачи 3-SAT, которая оказывается QMA-полной как задача с априорными ограничениями на входные данные.

Задача с априорными ограничениями на входные данные, или задача с обещанием — это задача, в которой вы можете получить верный ответ только в том случае, если на входные данные наложены некоторые ограничения. Если вы — алгоритм и вас облапошила крапленая входная строка, то любой суд вынесет решение в вашу пользу, и вы можете далее делать все, что вам заблагорассудится. Не исключено, что понять, соответствуют ли входные данные «обещанию», будет очень трудно и для этого потребуются сложные вычисления, но это не ваша забота. Есть классы сложности, в отношении которых мы далеко не уверены, что для них существуют полные задачи, но задачи, полные при априорных ограничениях на входные данные, для них существуют. QMA — именно такой класс. Основная причина, по которой нам нужны априорные ограничения на вход, заключается в разрыве между 1/3 и 2/3. Возможно, вы получите некую входную строку и примете ее с вероятностью, которая не превосходит 2/3, но и не меньше 1/3. В таком случае окажется, что вы поступили противозаконно, поэтому будем считать, что такой строки на вход вы не получите.

Итак, что представляет собой квантовая задача 3-SAT? Представьте себе n кубитов, застрявших в ионной ловушке (эй, обратите внимание, я пытаюсь привлечь к делу физику), и мы описываем уйму измерений, в каждом из которых задействовано не более трех кубитов. Каждое измерение i принимает с вероятностью, равной Pi. Эти измерения описать несложно, поскольку в каждом из них речь идет не более чем о трех кубитах. Далее мы находим сумму n таких измерений. Тогда априорное ограничение будет таким: либо существует состояние, такое, что эта сумма очень велика, либо для всех состояний эта сумма намного-намного меньше. Задача же состоит в том, чтобы решить, которое из двух условий выполняется. Это QMA-полная задача в том же смысле, в каком ее классический аналог 3-SAT полон в NP. Первым это доказал Китаев, а позже его результат был не единожды улучшен[106].

Но настоящий интерес появляется вместе с вопросом о том, насколько мощным является класс QMA. Есть ли утверждения, которые можно проверить за разумное время при помощи квантовых компьютеров, но которые невозможно проверить при помощи компьютеров классических? Это пример того, о чем мы уже говорили ранее: мы пытаемся устроить дуэль между реалистичным и субъективным взглядами на квантовые состояния и посмотреть, который из них выйдет победителем.

В статье Джона Ватруса[107] приводится пример, в котором, судя по всему, получение экспоненциально длинного вектора реально дает вам некоторые возможности. Задача называется задачей о непринадлежности к группе. Дана конечная группа G. Мы считаем ее экспоненциально большой, поэтому она не может быть задана явно, посредством гигантской таблицы умножения. Она задается более утонченным способом. Мы рассматриваем ее как группу — черный ящик; это означает, что у нас есть некий черный ящик, который будет выполнять для нас все групповые операции. То есть он будет перемножать и инвертировать элементы группы. Дан также полиномиально длинный список генераторов группы.

Каждый элемент группы закодирован некоторой n-битной строкой, хотя как именно закодирован, вы не знаете. Главное, что элементов в группе экспоненциально много, а генераторов — лишь полиномиальное количество.

Далее нам дается подгруппа H