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

набор квантовых вентилей. Если без формальностей, то это означает, что их одних вполне достаточно для квантового компьютера, поскольку при желании мы могли бы выстроить из них сколь угодно точную аппроксимацию любого другого квантового вентиля. (Или, строго говоря, любого вентиля, в унитарной матрице которого присутствуют только действительные, но не комплексные числа. Но в компьютерных делах это, как оказалось, не имеет значения.) Более того, согласно так называемой теореме Соловея — Китаева[70], при помощи любого универсального набора вентилей можно смоделировать любой другой универсальный набор вполне эффективно, то есть с не более чем полиномиальным увеличением числа вентилей. Так что, пока речь идет о теории вычислительной сложности, совершенно неважно, какой именно универсальный набор мы выбрали.

Это вполне аналогично тому, как в классическом мире мы могли бы строить свои схемы на элементах и, или и не, только на элементах и и не или даже только на элементах не-и.

Вы могли бы спросить: какие именно наборы квантовых вентилей обладают свойством универсальности? Наверное, совершенно особые? Напротив, оказывается, что в определенном вполне конкретном смысле почти любой набор одно— и двухкубитовых вентилей (мало того, почти любой единичный двухкубитовый вентиль) будет универсальным. Но, безусловно, из этого правила существуют исключения. Предположим, к примеру, что у вас имеется только вентиль Адамара (определенный выше) и следующий вентиль управляемой инверсии, который меняет второй кубит на противоположный, если первый кубит равен 1:

Казалось бы, это естественный универсальный набор квантовых вентилей, однако это не так. Так называемая теорема Готтесмана — Нилла[71] показывает, что любую квантовую схему, состоящую исключительно из вентилей Адамара и управляемой инверсии, можно эффективно смоделировать при помощи классического компьютера.

С той минуты, когда мы зафиксировали некий универсальный набор (любой универсальный набор) квантовых вентилей, мы будем интересоваться схемами, которые включают в себя не более чем p(n) вентилей из этого набора, где p — это полином, а n — число битов в той реализации задачи, которую мы хотим решить. Мы называем такие схемы квантовыми схемами полиномиального размера.

3. Измерение. Как прочесть ответ, когда вычисление проведено? Просто: измеряем некоторый выделенный кубит и отвергаем, если получаем исход |0〉, и принимаем, если получаем исход |1〉! Не забывайте, что для простоты мы рассматриваем здесь только задачи принятия решения — то есть задачи, требующие ответа «да» или «нет».

Мы условимся также, что если ответ на нашу задачу «да», то финальное измерение должно принимать с вероятностью по крайней мере 2/3, тогда как если ответ «нет», то оно должно принимать с вероятностью не более 1/3. Это в точности то же требование, что вводится для BPP. И, как и в случае с BPP, мы можем заменить 2/3 и 1/3 любыми другими числами по желанию (к примеру, 1–2–500 и 2–500), просто повторив вычисления нужное число раз, а затем подав на выход ответ, оказавшийся в большинстве.

Немедленно возникает вопрос: может быть, мы получили бы более мощную вычислительную модель, если бы разрешили не одно, а множество измерений на протяжении расчета?!

Оказывается, нет, потому что всегда можно смоделировать измерение (за исключением финального, того, что единственно имеет значение) при помощи унитарного квантового вентиля. Можно сказать, что вместо измерения кубита A можно применить к нему вентиль управляемой инверсии, получив при этом кубит B, но затем игнорировать кубит B до конца расчета. Тогда все будет обстоять так, будто какая-то третья сторона измерила кубит A, — эти две точки зрения математически эквивалентны. (Что это — тривиальная техническая подробность или глубокий философский момент? Вам судить…)

4. Однородность. Прежде чем дать определение BQP, нам следует разобраться с последним техническим вопросом. Мы говорили о «квантовой схеме полиномиального размера», но более правильно говорить о бесконечно большом семействе схем, по одной на каждую длину входной строки n. Могут ли схемы из этого семейства выбираться произвольно, полностью независимо одна от другой? Если да, то мы могли бы использовать их для решения, к примеру, проблемы остановки, просто зашив в структуру n-й схемы данные о том, останавливается ли n-я машина Тьюринга. Если мы хотим исключить этот момент, нам нужно поставить условие однородности. Это означает, что должен существовать (классический) алгоритм, который, получив на вход n, выдаст на выходе n-ю квантовую схему за полиномиальное по n время.

Упражнение. Покажите, что, если разрешить полиномиальный по времени квантовый алгоритм, дающий на выходе n-ю схему, определение получится то же самое.

Ну хорошо, мы наконец готовы собрать все кусочки вместе и дать определение BQP.

BQP есть класс языков L ⊆ {0, 1}*, для которых существует однородное семейство полиномиального размера квантовых схем {Cn}, таких, что для всех x ∈ {0, 1}n:

• если x ∈ L, то Cn принимает вход |x〉 |0…0〉 с вероятностью не менее 2/3;

• если x ∉ L, то Cn принимает вход |x〉 |0…0〉 с вероятностью не более 1/3.

Развычисления

Итак, что мы можем сказать о классе BQP?

Ну, для начала пусть у вас имеется BQP-алгоритм, вызывающий другой BQP-алгоритм в качестве подпрограммы. Может ли такая конструкция быть более мощной, чем сам BQP? Или, иными словами, может ли BQPBQP (то есть BQP с BQP-оракулом) быть более мощным, чем BQP?

Лучше бы, чтобы такого не было! Кстати говоря, это связано с одной вещью, о которой я однажды говорил с Дейвом Бэконом. Почему физики с таким трудом воспринимают класс NP? Дело, я подозреваю, в том, что класс NP с его «магическим» экзистенциальным квантификатором, наложенным на вычисления за полиномиальное время, — это штука не того сорта, которую они сами могли бы предложить. Классы, которые с удовольствием предложили бы физики, — классы сложности для физика — трудно обозначить точно, но одно свойство, которым они, на мой взгляд, определенно обладают, — это «не обсуждать очевидные вещи», такие как вызов одним алгоритмом класса другого алгоритма того же класса в качестве подпрограммы.

Я утверждаю, что BQP представляет собой приемлемый «класс сложности для физика» и, в частности, что BQPBQP = BQP. Неужели это трудно показать?

Верно, мусор мешает! Вспомните, что, когда квантовый алгоритм завершен, вы, чтобы получить ответ «да» или «нет», измеряете один-единственный кубит. Что же делать со всеми остальными кубитами? В обычных условиях вы бы их просто отбросили. Но что, если вы получили суперпозицию по различным прогонам некоторого алгоритма и хотите свести результаты этих прогонов воедино и перемешать их? В этом случае мусор может