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

унитарный оператор U. Более того, пусть действует априорное ограничение: либо U — матрица тождественного преобразования I, либо существует некое секретное «выделенное состояние» |ψ〉, такое, что U|ψ〉 = —|ψ〉; то есть U имеет какой-то секретный собственный вектор, соответствующий собственному числу, равному –1. Задача состоит в том, чтобы решить, которое из этих условий выполняется.

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

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

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

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

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

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

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

кубитов.

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

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

Итак, вот что мы делаем. Мы узнали x1 и при этом лишь слегка повредили состояние. Прогнав протокол еще