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

≤ G, которая также может быть задана посредством списка генераторов. Задача крайне проста: дается элемент группы x, и мы хотим узнать, входит ли он в подгруппу. Я изложил эту задачу абстрактно, в терминах черных ящиков, но ее всегда можно конкретизировать, если под рукой имеется пример группы. К примеру, в роли генераторов могут выступать матрицы над некоторым конечным полем; вам дается какая-то другая матрица и спрашивается, можете ли вы получить ее при помощи заданных генераторов. Вполне естественный вопрос.

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

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

К примеру, если мы начали с группы ZN, аддитивной по модулю n, и если у нас имеется единственный стартовый элемент 1, мы можем просто раз за разом прибавлять по 1, но тогда, чтобы добраться до 25000, нам потребуется немало времени. Но если мы будем рекурсивно наращивать элементы: 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, относительно которого QMAA ≠ QCMAA. На самом деле такую штуку несложно описать. Для начала, что такое квантовый оракул? Квантовые оракулы — это просто квантовые подпрограммы, к которым, как мы считаем, имеют доступ и QMA-, и QCMA-машины. Если классические оракулы действуют на вычислительном базисе (возможно, в суперпозиции в пределах квантового состояния), то квантовые оракулы способны действовать на произвольном базисе. Попробуем разобраться в том, какая идея стоит за использованным нами оракулом A. Пусть нам дан некоторый n-кубитный