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

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

Главный итог — то, что этот интуитивный размен сжимаемости прошлых данных на предсказуемость будущих данных может реально быть формализован и доказан; иначе говоря, при разумных допущениях бритва Оккама является теоремой.

Но что, если вещь, которую мы пытаемся узнать, — это квантовое состояние, скажем некоторое смешанное состояние ρ? Мы могли бы провести измерение E с двояким результатом. В квантовой механике самый общий тип измерения называется положительной операторной мерой (POVM, positive operator valued measure). POVM — это всего лишь обычное «проективное» измерение — измерение того типа, который мы обсуждали ранее, за исключением того, что перед измерением как таковым вы должны провести произвольное унитарное преобразование измеряемого состояния ρ вместе с некоторым дополнительным «вспомогательным состоянием», не зависящим от ρ. В данном случае вам достаточно знать следующее: если у вас имеется POVM M с двумя возможными исходами, действующее на n-мерном смешанном состоянии ρ, то вы можете полностью характеризовать M при помощи эрмитовой матрицы E размера n × n, все собственные величины которой принадлежат [0, 1]. Тогда вероятность того, что M «принимает» ρ, просто равна tr(Eρ) (где tr, или ранг, есть сумма диагональных элементов), а вероятность того, что M «отвергает» ρ, равна 1 — tr(Eρ).

Далее, если нам дано некоторое состояние ρ, то мы бы хотели иметь возможность предсказывать результат любого измерения, проведенного над этим состоянием, то есть оценивать вероятность принятия tr(Eρ) для любого двухвариантного POVM-измерения E. Легко убедиться, что это эквивалент томографии квантового состояния, то есть выяснения самой матрицы плотности ρ.

Но что такое ρ? Это некоторое n-кубитное состояние, представленное в виде матрицы 2n × 2n с 4n независимых параметров. Хорошо известно, что число измерений, необходимых для томографии n-кубитного состояния, растет экспоненциально с n. Уже одно это представляет серьезную практическую проблему для экспериментаторов. Чтобы узнать восьмикубитное состояние, вам, может быть, придется настроить свой детектор 65536 разными способами и провести с каждой настройкой не одну сотню измерений, чтобы добиться приемлемой точности.

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

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

В 2006 г. я опубликовал статью[125], в которой попытался использовать для ответа на этот аргумент теорию вычислительного обучения. Вот как Умеш Вазирани объяснил мой результат. Он сказал: предположим, вы младенец, который пытается усвоить некое правило, позволяющее предсказывать, является ли заданный объект стулом. Вы видите кучу предметов с ярлыками «стул» или «не стул» и на основании этого вырабатываете собственные общие правила («у стула четыре ножки», «на стуле можно сидеть» и т. п.), отлично работающие в большинстве случаев. Правда, эти правила могут отказать, если (скажем) вы находитесь в музее современного искусства, но мы не будем об этом беспокоиться. В теории вычислительного обучения мы хотим предсказывать не все, а лишь большую часть будущих наблюдений. Если вы простой обыватель и не ходите в музей современного искусства, то вам нечего беспокоиться о стулоподобных объектах, которые можно там обнаружить. Нам следует принимать во внимание будущие намерения обучающегося, поэтому мы смягчаем цель томографии квантового состояния и говорим, что она заключается в предсказании исхода большинства измерений, взятых из некоторого распределения вероятностей D.

Более формально, если задано смешанное состояние ρ на n кубитах, а также измерения E1, E2, …, Em ~ D и расчетные вероятности pj ≈ Tr(Ejρ) для каждого j ∈ {1, 2, …, m}, то цель состоит в том, чтобы сформировать гипотетическое состояние σ, которое с вероятностью не менее 1 — δ имеет свойство

Для этой цели существует теорема, ограничивающая число необходимых образцовых измерений.

Теорема. Зафиксируем параметры ошибки ε, δ и γ и зафиксируем также η > 0, такое, что γε ≥ 7η. Назовем E = (E1, …, Em) «хорошим» обучающим множеством измерений, если любое гипотетическое состояние σ, удовлетворяющее условию |Tr(Eiσ) — Tr(Eiρ) | ≤ η, удовлетворяет также

В этом случае существует константа K > 0, такая, что E будет хорошим обучающим множеством с вероятностью по крайней мере 1 — δ над E1, …, Em, извлеченными из D, при условии что m удовлетворяет условию

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

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