В этой главе речь пойдет о вопросе, вынесенном в заголовок, но для начала небольшое отступление. В науке существует традиционная иерархия, на самом верху которой находится биология, затем, чуть ниже, химия, а затем уже физика. Великодушный физик скажет, что математика идет следующей. А уж информатика теряется где-то там, внизу, вместе с грунтоведением и прочими ненаучными дисциплинами.

Лично я придерживаюсь немного другой точки зрения: теоретическая информатика — посредник между физическим миром и платоновым миром идей. С учетом этого название «теоретическая информатика» как минимум неточно; может быть, лучше было бы называть ее «количественной эпистемологией». Это своего рода изучение способности конечных существ, таких как мы с вами, к познанию математических истин. Надеюсь, мне удалось отчасти показать вам это.

Как примирить это с представлением о том, что любое реальное применение компьютера должно быть основано на физике? Не поменяются ли при этом местами физика и информатика?

Ну, по той же логике можно сказать, что любое математическое доказательство должно быть написано на бумаге, и потому физика должна стоять в этой иерархии ниже математики. Или можно сказать, что математика занимается в основном изучением того, остановится конкретный вид машины Тьюринга или нет, поэтому информатика — основа всего и вся. Тогда математика — это всего лишь особый случай, область, где машины Тьюринга пересчитывают топологические пространства или делают еще что-то, что интересует математиков. Но тогда очень странным кажется то, что физика, особенно в виде квантовой вероятности, в последнее время просачивается вниз по этой интеллектуальной иерархии, засоряя «нижние» уровни математики и информатики. Именно так я всегда представлял квантовые вычисления: как физику, сбежавшую со своего законного места в интеллектуальной иерархии! Если хотите, я профессионально интересуюсь физикой именно в том объеме, в каком она просачивается вниз, на «нижние» уровни, которые считаются наименее произвольными, и заставляет меня заново продумывать все то, что я, как мне казалось, в них понимаю.

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

Грубо говоря, многомировая интерпретация ответила бы: «Абсолютно точно». Это позиция, которую Дэвид Дойч защищает очень красноречиво; но если различные вселенные (или компоненты волновой функции), используемые в алгоритме Шора, не присутствуют здесь физически, то где же было разложено число на простые множители?

Мы говорили также о механике Бома, которая говорит «да», но при этом уточняет, что один компонент вектора «более реален», чем остальные. Далее, есть еще подход, который раньше называли копенгагенским, а сегодня чаще зовут байесовским, информационно-теоретическим и множеством других имен.

В байесовском подходе квантовое состояние — это экспоненциально длинный вектор амплитуд в более или менее том же смысле, в каком классическое распределение вероятности есть экспоненциально длинный вектор вероятностей. Если вы возьмете монетку и бросите ее 1000 раз, вы бы получили некоторое множество из 2¹⁰⁰⁰ возможных исходов, — но ведь мы не готовы по этой причине рассматривать все эти исходы как физически реальные!

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

Подход Бома занимает какое-то странное промежуточное положение. В нем вы все же рассматриваете эти экспоненциальные количества вероятностей как нечто реальное; это направляющее поле, но есть еще та самая «более реальная» штука, которую они направляют. В копенгагенской интерпретации все это экспоненциальное множество возможностей действительно находится только в голове. Считается, что они соответствуют чему-то в реальном мире, но что такое это «что-то», мы либо не знаем, либо не имеем права спрашивать. Крис Фукс говорит, что существует некий физический контекст квантовой механики — нечто внешнее по отношению к нашим головам, но что мы не знаем, что это за контекст. Нильс Бор склонялся скорее к варианту «вы не имеете права спрашивать».

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

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

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

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

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

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

Мы хотим, чтобы существовало квантовое состояние разумного размера, способное убедить вас в ответе «да». Таким образом, если ответ «да», то существует состояние, которое вас убеждает, а когда ответ «нет», то и состояния такого нет. 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 ≤ G, которая также может быть задана посредством списка генераторов. Задача крайне проста: дается элемент группы x, и мы хотим узнать, входит ли он в подгруппу. Я изложил эту задачу абстрактно, в терминах черных ящиков, но ее всегда можно конкретизировать, если под рукой имеется пример группы. К примеру, в роли генераторов могут выступать матрицы над некоторым конечным полем; вам дается какая-то другая матрица и спрашивается, можете ли вы получить ее при помощи заданных генераторов. Вполне естественный вопрос.

Скажем, ответ должен быть «да». Но можно ли это доказать вам?

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

К примеру, если мы начали с группы Z_N, аддитивной по модулю n, и если у нас имеется единственный стартовый элемент 1, мы можем просто раз за разом прибавлять по 1, но тогда, чтобы добраться до 2⁵⁰⁰⁰, нам потребуется немало времени. Но если мы будем рекурсивно наращивать элементы: 2 = 1 + 1, 4 = 2 + 2 и т. п., раз за разом применяя групповую операцию к новым элементам, мы доберемся до желаемого элемента, каким бы он ни был, намного быстрее.

Всегда ли это можно сделать за полиномиальное время? Оказывается, да, для любой группы. Чтобы убедиться в этом, достаточно построить цепочку подгрупп, начиная с оригинальной. Показать это не очень просто, но это делает теорема Бабаи и Семереди, которая верна вне зависимости от того, решаема ли данная группа.

Далее возникает вопрос: что, если x∉H? Могли бы вы продемонстрировать это? Конечно, вы могли бы дать экспоненциально длинное доказательство, и если бы у вас было экспоненциально много времени, то могли бы его и продемонстрировать, но это не метод. Мы до сих пор не понимаем толком, что с этим делать, даже если бы у нас было классической доказательство и разрешение проверить его посредством квантовых вычислений, — хотя на этот счет имеются кое-какие гипотезы.

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

Оно экспоненциально велико, но существуют и другие экспоненциально большие квантовые состояния, которые приготовить легко, так что это определенно не вся причина. Оказывается, вся проблема в том «мусоре», который надо «развычислить».

Итак, мы знаем, как применить к группе метод случайного блуждания; мы знаем также, как выбрать случайный элемент группы. Но здесь от нас требуется нечто большее. От нас требуется когерентная суперпозиция элементов группы. Нетрудно приготовить состояние вида Σ|g〉|мусор_g〉. Но как избавиться от этого мусора? Вот вопрос. Ведь, по существу, этот мусор — след случайного блуждания или любого другого процесса, посредством которого вы дошли до g, но как забыть дорогу к этому элементу?

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

1. Убеждаемся, что нами действительно получено нужное состояние (пока нам достаточно соответствующего допущения).

2. При помощи состояния |H〉 доказываем, что x ∉ H, воспользовавшись контролируемым левосторонним умножением:

Затем применяем вентиль Адамара и измеряем первый кубит. Поясним: левый кубит у вас работает как контрольный. Если x ∈ H, то xH есть перестановка H, поэтому мы получаем интерференционные полосы (свет прошел одновременно через щели x и xH). Если x ∉ H, то мы получаем, что xH — смежная группа и, соответственно, не имеет общих элементов с H. Из этого следует 〈H|xH〉 = 0, так что мы измеряем случайные биты. Эти два случая мы можем различить.

Вам придется также убедиться, что состояние |H〉 — это именно то, что мы получили. Для этого мы проведем тест, аналогичный только что рассмотренному. В данном случае мы выбираем элемент x посредством классической процедуры случайного блуждания по подгруппе H. Затем, если |H〉 действительно является суперпозицией по подгруппе, |xH〉 просто циклично сдвинется на x, а если x ∉ H, мы получим что-то иное. Вам придется доказать, что этот тест не только необходим, но и достаточен. Примерно это и доказал Ватрус.

Это пример того, что иногда наличие квантового состояния реально полезно и позволяет справиться с экспоненциальностью этого состояния. Может, пример не слишком сильный, но все же кое-что.

Встает очевидный вопрос: во всех этих случаях, где квантовое доказательство, кажется, помогает нам, может быть, мы справились бы не хуже, если бы нам было дано классическое доказательство, которое мы проверяли бы при помощи квантовых вычислений? За счет чего на самом деле получается преимущество — за счет наличия квантового состояния или за счет того факта, что у нас имеется квантовый компьютер для проверки? Можно сформулировать вопрос иначе: действительно ли QMA = QCMA, где QCMA — это аналог QMA? Только доказательство в нем должно быть классическим. Мы с Грегом Купербергом написали статью[108], в которой попытались взглянуть на этот вопрос повнимательнее. Один из фактов, которые нам удалось показать, представляется опасным для реалистического взгляда на квантовые состояния (по крайней мере в этом конкретном вопросе): если обычная задача о скрытой подгруппе (в чем именно она состоит, сейчас неважно) может быть решена за квантово-полиномиальное время — а, судя по всему, так и есть — и если мы делаем еще кое-какие предположения по теории групп, которые все специалисты, которых мы спрашивали, считают правдоподобными, то задача о невхождении в группу действительно входит в QCMA. То есть доказательство можно деквантизировать и заменить классическим.

С другой стороны, мы показали, что существует квантовый оракул A, относительно которого QMA^A ≠ QCMA^A. На самом деле такую штуку несложно описать. Для начала, что такое квантовый оракул? Квантовые оракулы — это просто квантовые подпрограммы, к которым, как мы считаем, имеют доступ и QMA-, и QCMA-машины. Если классические оракулы действуют на вычислительном базисе (возможно, в суперпозиции в пределах квантового состояния), то квантовые оракулы способны действовать на произвольном базисе. Попробуем разобраться в том, какая идея стоит за использованным нами оракулом A. Пусть нам дан некоторый n-кубитный унитарный оператор U. Более того, пусть действует априорное ограничение: либо U — матрица тождественного преобразования I, либо существует некое секретное «выделенное состояние» |ψ〉, такое, что U|ψ〉 = —|ψ〉; то есть U имеет какой-то секретный собственный вектор, соответствующий собственному числу, равному –1. Задача состоит в том, чтобы решить, которое из этих условий выполняется.

Несложно убедиться, что эта задача, будучи задачей с оракулом, входит в QMA. Почему это так? Потому что доказатель должен будет всего лишь дать проверяющему |ψ〉, а проверяющий применит U|ψ〉 для проверки, что действительно U|ψ〉 = —|ψ〉. Ничего, в общем-то, особенного.

А доказали мы, что эта задача, будучи задачей с оракулом, не входит в QCMA. Так что даже если бы у вас были и ресурсы унитарной операции U, и полиномиального размера классическая строка, способная указать вам на этот секретный отрицательный собственный вектор, вам все равно потребовалось бы экспоненциально много запросов, чтобы найти |ψ〉.

Этот результат, вообще говоря, указывает в другом направлении — что, может быть, QMA мощнее, чем QCMA. Если бы они были равны по мощности, то это пришлось бы показывать с использованием квантово-нерелятивизирующей методики, то есть методики, чувствительной к присутствию квантовых оракулов. В данный момент нам такие методики неизвестны, если не считать те из них, которые являются также классически нерелятивизирующими и, судя по всему, неприменимы к данной задаче.

Так что здесь возникает другой метавопрос: есть ли какая-то разница между квантовыми и классическими оракулами? В смысле, имеется ли какой-то вопрос, ответить на который можно только при помощи квантовых оракулов. Можно ли при помощи классического оракула различить QMA и QCMA? Мы с Грегом Купербергом поработали над этим, но успеха не добились. Совсем недавно Энди Лютомирский[109] предложил перспективную задачу, способную, как он (и я) предполагает, провести такое различие, но никто пока не сумел этого доказать. Если вы сможете, будет здорово!

Ну хорошо. Мы поговорили о квантовых доказательствах. Существуют и другие способы, которые мы можем попробовать в поиске ответа на вопрос: сколько всего можно извлечь из одного квантового состояния? В теореме Холево речь идет о таком вопросе: если Алиса хочет переслать Бобу какую-то классическую информацию и имеет при этом доступ к квантовому каналу связи, может ли она воспользоваться им с пользой для себя? Если квантовые состояния представляют собой экспоненциально длинные векторы, то интуитивно мы можем ожидать, что если бы Алиса могла переслать Бобу некоторое n-кубитное состояние, то она, возможно, могла бы воспользоваться им, чтобы переслать ему 2ⁿ классических бит. Это утверждение можно получить путем простого подсчета. Число квантовых состояний из n кубитов, дающих попарно почти нулевое внутреннее произведение, дважды экспоненциально по n. Мы говорим только, что для записи такого состояния вам потребуется экспоненциальное число бит. Остается надеяться на обретение какого-то механизма экспоненциального сжатия информации. Увы, теорема Холево гласит, что это невозможно. Необходимо n кубитов, чтобы надежно передать n классических бит всего лишь с некоторым постоянным множителем, отражающим тот факт, что вы готовы терпеть некоторую вероятность ошибки; результат не лучше, чем с классическим вероятностным кодированием.

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

На самом деле эта теорема была известна уже в 1970-е гг. и явно обогнала свое время. И лишь недавно кто-то задал очень естественный и тесно связанный с ней вопрос: что, если Боб не хочет извлекать всю строку? Из теоремы Холево нам известно, что получить всю строку целиком невозможно, но что, если Боб хочет извлечь из сообщения всего один бит и Алиса не знает заранее, который именно? Может ли Алиса построить такое квантовое состояние |ψ_x〉, что, какой бы бит x_i Боб ни захотел узнать, ему достаточно будет для этого просто измерить |ψ_x〉 в подходящем базисе? Узнав x_i, он разрушит состояние и не сможет больше ничего узнать, но это его устраивает. Допустим, Алиса хочет переслать Бобу квантовый телефонный справочник, а Боб хочет посмотреть в нем лишь один номер. Оказывается, согласно доказательству Амбайниса, Наяка и др.[110], это тоже невозможно. Они доказали: чтобы зашифровать n бит таким образом, чтобы можно было прочесть любой один из них, необходимо по крайней мере кубитов.

Может, вам и удастся на этом кое-что выиграть, но экономия точно не будет экспоненциальной. А вскоре после этого Наяк доказал, что на самом деле, если вы хотите зашифровать n бит, вам потребуется n кубитов. Если мы готовы смириться с потерей одного-двух логарифмических множителей, я могу довольно просто показать, как именно это следует из теоремы Холево. Смысл упражнения в том, что оно иллюстрирует технику, при помощи которой мне уже удалось много добиться и в которой, возможно, еще остался немалый потенциал.

Предположим, в порядке противоречия, что у нас имеется протокол, способный надежно закодировать n бит не более чем в log n кубитов таким образом, что любой бит можно затем извлечь из закодированного текста с высокой вероятностью, скажем с вероятностью ошибки не более трети. Затем мы можем взять некоторое количество копий этого состояния. Мы просто хотим снизить вероятность ошибки, так что возьмем тензорное произведение, скажем, log n копий. Что может сделать Боб, имея это состояние? Боб может применить к каждой копии оригинальный протокол, чтобы получить xi, а затем взять мажоритарный ответ. Для некоторой достаточно большой константы, умноженной на log n, это снизит долю ошибок до не более чем n–2. Таким образом, для любого конкретного бита i Боб сможет получить бит y_i, такой, что Pr [y_i = x_i] ≥ 1 — n^–2. А раз Боб это может, то что еще он может сделать? Он может повторять эту процедуру раз за разом и жаждать большего. Я собираюсь прогнать этот процесс и получить x1, но теперь, поскольку результат этого измерения можно было предсказать почти наверняка с учетом текущего состояния, в результате вы можете доказать, что получите совсем немного информации, так что наше состояние будет лишь слегка потревожено измерением. В отношении квантовых измерений это общеизвестный факт. Если результат можно предсказать наверняка, то наше измерение вообще не сможет потревожить состояние[111].

Итак, вот что мы делаем. Мы узнали x₁ и при этом лишь слегка повредили состояние. Прогнав протокол еще раз, мы узнаем x₂ и нанесем лишь небольшой ущерб. Поскольку небольшой ущерб плюс небольшой ущерб будет по-прежнему небольшой ущерб, мы можем затем найти x₃, и т. п. Таким образом, мы можем восстановить все биты оригинальной строки, использовав меньше кубитов, чем предполагает показанная Холево оценка. На основе всего этого можно сказать, что такой протокол невозможен.

Почему подобные вещи нас заботят? Ну, может, и не заботят, но я могу сказать, как все это попало в поле моего зрения. Далее мы не будем говорить о квантовых доказательствах, а переключимся на тесно связанную с ними концепцию под названием квантовый совет. Привлечем класс BQP/qpoly — множество задач, эффективно решаемых квантовым компьютером при наличии полиномиального по размеру состояния квантового совета. В чем разница между советом и доказательством? Как уже говорилось в главе 7, совет зависит только от длины входной строки n, но абсолютно достоин доверия, тогда как доказательство зависит от реального входа, но нуждается в проверке.

Таким образом, преимущество совета состоит в том, что вы можете ему доверять, а недостаток — в том, что совет может оказаться менее полезным, чем мы предполагали, поскольку не подгоняется к конкретной реализации задачи, которую вы пытаетесь решить. Поэтому мы можем догадываться, что квантовым компьютерам, возможно, трудно решать NP-полные задачи, но только в том случае, если этому квантовому компьютеру приходится начинать с некоторого нулевого начального состояния. Возможно, существуют кое-какие очень необычные состояния, возникшие в ходе Большого взрыва и все это время просидевшие в какой-нибудь туманности (и каким-то образом не декогерировавшие). Если мы сядем на космический корабль и отыщем эти состояния, они, очевидно, не смогут предвидеть, какую конкретную реализацию SAT мы захотим решить, но они как бы предвидят, что мы захотим решить какую-то ее реализацию. Может ли существовать то самое обобщенное состояние |ψ_n〉 для решения SAT-задачи, такое, что для любой булевой формулы P размера n мы могли бы, проведя с |ψ_n〉 некоторые квантовые вычисления, выяснить, удовлетворима ли P? На самом деле мы здесь задаемся вопросом: правда ли NP ⊂ BQP/qpoly?

Что мы можем сказать о мощности BQP/qpoly? Можно адаптировать результат Ватруса в отношении квантовых доказательств к данному квантовому совету. Возвращаясь к задаче о невхождении в группу: если бы Большой взрыв предвидел, вхождение в какую подгруппу нас заинтересует, но не то, какой именно элемент мы будем проверять на вхождение в эту подгруппу, то он мог бы снабдить нас состоянием |H〉, представляющим собой суперпозицию по всем элементам H; после этого мы могли бы проверить на вхождение в H любой элемент, какой захотели бы. Отсюда видно, что по крайней мере какая-то версия задачи о невхождении в группу входит в BQP/qpoly.

Я не упоминал об этом раньше, но мы можем доказать[112], что QMA ⊆ PP, так что, очевидно, существует некий предел мощности QMA. Можно заметить, что в худшем случае вам придется всего лишь перебрать все возможные квантовые доказательства (все возможные состояния из n кубитов) и посмотреть, найдется ли среди них такое состояние, которое наша машина примет. Можно добиться и лучшего результата; именно отсюда возникает оценка PP.

А что с BQP/qpoly? Можете ли вы найти какую-нибудь верхнюю оценку для мощности этого класса? То есть можете ли вы найти какой-то способ обосновать, чего он не может делать?

Знаем ли мы хотя бы, что BQP/qpoly не равен ALL — множеству вообще всех языков (включая невычислимые)? Пусть нам дана экспоненциально длинная классическая строка совета. Несложно убедиться, что в этом случае мы могли бы решить вообще любую задачу. Почему? Потому что пусть f:{0, 1}ⁿ → {0, 1} — булева функция, которую мы хотим вычислить. Тогда мы просто объявляем совет полной таблицей истинности для этой функции, и нам достаточно будет найти в этой таблице подходящую строку, чтобы решить любую задачу размера n, какую нам заблагорассудится. Задачу остановки, вообще все что угодно.

В качестве другого примера рассмотрим знаменитую константу Ω, определенную Грегори Хайтином[113]. Неформально Ω есть вероятность того, что «случайно сгенерированная компьютерная программа» остановится, получив на вход пустую строку на некотором фиксированном универсальном по Тьюрингу программном языке. (Технически, чтобы эта вероятность была хорошо определена, программный язык должен быть «самоограничивающим»; это означает, что невозможно создать рабочую программу, добавляя новые биты в конец уже существующей рабочей программы.) Биты двоичной записи Ω можно сравнить едва ли не с божьей премудростью: в них, как сказали бы, максимально эффективным способом зашифрованы ответы на громадное число математических вопросов (гипотеза Гольдбаха, гипотеза Римана и т. п.). Было бы потрясно получить такую штуку в качестве «совета»! (Хотя обратите внимание: с практической точки зрения извлечение из совета интересной информации — о верности или ошибочности гипотезы Гольдбаха и т. п. — потребовало бы невероятного объема вычислений и почти наверняка оказалось бы совершенно непрактичным. На практике, вероятно, вы бы не смогли отличить Ω от простой случайной строки. Но все же: вот глупость!)

Интуитивно сложно себе представить, что BQP/qpoly = ALL, потому что полиномиальное число кубитов совсем не то же самое, что экспоненциальное длинная строка классических битов. Вопрос в том, насколько это «море» экспоненциального количества классических битов, необходимых для описания квантового состояния, определяет то, что мы получим?

Пожалуй, я перейду к главному и расскажу вам, как много лет назад на одном семинаре Гарри Бурман задал мне этот вопрос; мне было очевидно, что BQP/qpoly — это не все, и он попросил меня доказать это. И постепенно я понял, что все, что можно сделать с полиномиального размера квантовым советом, можно сделать и с полиномиального размера классическим советом, если, конечно, вы можете выполнить измерение и затем осуществлять выбор по результатам измерения. Иначе говоря, я доказал[114], что BQP/qpoly ⊆ PostBQP/poly. (Позже, в 2010 г., мы с Эндрю Друкером[115] улучшили этот результат, показав, что на самом деле BQP/qpoly ⊆ QMA/poly, что в определенном смысле дает нам «оптимальную» верхнюю оценку для BQP/poly в терминах класса с классическим советом, при допущении, что BQP/qpoly не является попросту равным BQP/poly. Но пока хватит об этом.) Сухой остаток в том, что все, что вы можете узнать из квантового совета, вы можете узнать и из классического совета сравнимого размера, при условии, что вы готовы тратить экспоненциально больше вычислительных усилий на извлечение информации, которую пытается сообщить совет.

Опять же достаточно будет двух минут, чтобы привести не слишком строгое доказательство того, что BQP/qpoly ⊆ PSPACE/poly. Мне нравится, как Грег Куперберг описал это доказательство. Он сказал: если у нас есть квантовый совет, а мы хотим имитировать его при помощи классического совета посредством постселекции, мы используем «дарвинову обучающую последовательность» входных сигналов. Пусть у нас есть машина, способная принять классический совет, а мы хотим рассказать этой машине про некоторый набор квантовых советов при помощи только классических советов. Для этого мы рассматриваем некоторые тестовые входы X₁, X₂, …, X_T. Заметьте, кстати, что наша машина с классическим советом не знает истинного состояния квантового совета |ψ〉. Машина с классическим советом начинает с предположения о том, что квантовый совет — это максимально смешанное состояние, поскольку без априорного знания любое квантовое состояние имеет равную вероятность оказаться состоянием совета. Далее, X₁ — это входная строка к алгоритму, такая, что если максимально смешанное состояние используется вместо квантового совета, то алгоритм выдает неверный ответ с вероятностью выше одной трети. Если же алгоритм все же угадывает верный ответ, то проведенное измерение изменит состояние совета в некоторое новое состояние ρ₁. Почему же этот процесс описывается как «дарвинов»? Следующая часть классического совета, X₂, описывает некоторый входной сигнал к алгоритму, такой, что неверный ответ будет дан с вероятностью, большей одной трети, если использовать ρ₁ вместо настоящего квантового совета. Если, несмотря на высокую вероятность получения неверного ответа, алгоритм, получив на вход X₁ и X₂, все же даст два верных ответа, то мы используем полученную в результате оценку состояния совета ρ₂, чтобы получить следующую часть классического совета X₃. По существу, мы пытаемся научить нашу машину для классического совета работе с квантовым советом, раз за разом повторяя: «Предположим, ты все предыдущие уроки усвоила успешно, вот тебе новый тест, который ты наверняка провалишь. Иди учись, дитя мое».

Суть в том, что если мы признаем |ψ_n〉 истинным квантовым советом, то, поскольку мы можем разложить максимально смешанное состояние в любом базисе, в каком захотим, мы можем считать его результатом смешения состояния истинного совета, которое мы пытаемся узнать, и кучи других вещей, ортогональных ему. Всякий раз, когда мы даем неверный ответ с вероятностью, большей одной трети, мы как бы отсекаем от этого пространства еще треть. После этого мы делаем постселекцию из того, что получилось. Мы знаем также, что если бы мы начали с истинного состояния совета, мы выдали бы верный ответ, так что этот процесс должен где-то завершиться; постепенно мы отсеем весь мусор, и примеры, на которых алгоритм ошибается, у нас закончатся.

Итак, в этой ситуации квантовые состояния работают не как экспоненциально длинные векторы. Они работают как если бы в них был закодирован лишь полиномиальный объем информации, хотя извлечение того, что вы хотите узнать, может оказаться экспоненциально более эффективным, чем если бы та же информация была представлена классически. Опять же мы получаем неоднозначные ответы, но мы этого и ожидали. Мы знали, что именно квантовые состояния населяют это странное срединное царство между распределениями вероятности и экспоненциально длинными строками. Тем не менее приятно точно знать, как играет интуитивное понимание в каждом из этих конкретных сценариев. Мне кажется, что именно это привлекает меня в квантовой теории сложности. В каком-то смысле это то самое, о чем спорили Бор и Гейзенберг, но мы сегодня можем задавать вопросы намного конкретнее — и иногда даже отвечать на них.