Итак, что мы можем сказать о классе BQP?
Ну, для начала пусть у вас имеется BQP-алгоритм, вызывающий другой BQP-алгоритм в качестве подпрограммы. Может ли такая конструкция быть более мощной, чем сам BQP? Или, иными словами, может ли BQPBQP (то есть BQP с BQP-оракулом) быть более мощным, чем BQP?
Лучше бы, чтобы такого не было! Кстати говоря, это связано с одной вещью, о которой я однажды говорил с Дейвом Бэконом. Почему физики с таким трудом воспринимают класс NP? Дело, я подозреваю, в том, что класс NP с его «магическим» экзистенциальным квантификатором, наложенным на вычисления за полиномиальное время, — это штука не того сорта, которую они сами могли бы предложить. Классы, которые с удовольствием предложили бы физики, — классы сложности для физика — трудно обозначить точно, но одно свойство, которым они, на мой взгляд, определенно обладают, — это «не обсуждать очевидные вещи», такие как вызов одним алгоритмом класса другого алгоритма того же класса в качестве подпрограммы.
Я утверждаю, что BQP представляет собой приемлемый «класс сложности для физика» и, в частности, что BQPBQP = BQP. Неужели это трудно показать?
Верно, мусор мешает! Вспомните, что, когда квантовый алгоритм завершен, вы, чтобы получить ответ «да» или «нет», измеряете один-единственный кубит. Что же делать со всеми остальными кубитами? В обычных условиях вы бы их просто отбросили. Но что, если вы получили суперпозицию по различным прогонам некоторого алгоритма и хотите свести результаты этих прогонов воедино и перемешать их? В этом случае мусор может воспрепятствовать взаимодействию различных ветвей! Что же делать, чтобы исправить ситуацию?
Решение, предложенное Чарльзом Беннеттом в 1980-е гг., состоит в развычислении. Вот как это работает.
1. Запускаете подпрограмму.
2. Копируете кубит, выданный подпрограммой в качестве ответа, в отдельное место.
3. Прогоняете всю подпрограмму задом наперед, стирая таким образом все, кроме кубита-ответа. (Если эта подпрограмма имеет какую-то вероятность ошибки, то этап стирания пройдет неидеально; тем не менее все сработает достаточно хорошо.)
Если вы побываете у меня дома, то увидите, что это не та методика, которой я обыкновенно пользуюсь. Но если вы — квантовый компьютер, то прибрать за собой мусор — неплохая идея.