Ну хорошо, теперь у нас есть прекрасная теория квантовой механики и, возможно, еще более прекрасная теория вычислительной сложности. Ясно, что, имея две теории такой невероятной красоты, мы не можем оставить их обе в одиночестве — мы просто обязаны их познакомить и посмотреть, что из этого выйдет.
Это приводит нас к классу BQP — квантовому с ограниченной ошибкой за полиномиальное время. В главе 7 мы говорили о классе BPP, вероятностном с ограниченной ошибкой за полиномиальное время. Если говорить неформально, BPP — это класс вычислительных задач, эффективно решаемых в физическом мире в том случае, если классическая физика верна. Теперь мы задаемся вопросом о том, какие задачи эффективно решаемы в том же физическом мире, если (что представляется более вероятным) верна квантовая физика.
Меня поражает от факт, что сколько-нибудь серьезно этот вопрос додумались задать только в 1990-е годы, при том что все инструменты для его рассмотрения были в наличии уже в 1960-х, если не раньше. Поневоле начинаешь задумываться: какие очевидные на первый взгляд вопросы никто не додумывается задать сегодня?
Итак, как мы определяем BQP? Ну, существует четыре момента, о которых нам следует позаботиться.
1. Инициализация. Мы говорим, что у нас есть система, состоящая из n квантовых битов (или кубитов), и все они инициализированы в некоторое простое, легкое и удобное в подготовке состояние. Для удобства мы обычно считаем его «вычислительным базисным состоянием», хотя позже имеет смысл подумать о более мягком подходе. В частности, если входная строка равна x, то начальное состояние будет иметь вид |x〉|0…0〉, то есть |x〉 плюс столько дополнительных кубитов, сколько мы хотим инициализировать в нулевом состоянии.
2. Преобразования. В любой момент состояние нашего компьютера будет суперпозицией по всем 2p(n) p(n) — битным строкам, где p — некоторый полином от n переменных:
Но какие операции мы можем использовать для преобразования одного состояния-суперпозиции в другое? Поскольку речь идет о квантовой механике, это должны быть унитарные преобразования, но какие именно? Для любой булевой функции f:{0, 1}n → {0, 1} существует какое-то унитарное преобразование, которое мгновенно вычислит для нас эту функцию. К примеру, мы могли бы взять произвольное унитарное преобразование, которое отображает каждое базисное состояние вида |x〉|0〉 на |x〉|f(x) 〉.
Но, конечно, для большинства функций f мы не в состоянии применить это преобразование эффективно. В точности по аналогии с классическими вычислениями, где нас интересуют только те схемы, которые можно построить из небольшого числа логических элементов и, или и не, здесь нас интересуют только те унитарные преобразования, которые можно построить из небольшого числа квантовых вентилей. Под «квантовым вентилем» я буду просто иметь в виду унитарное преобразование, действующее на небольшое число кубитов, скажем один, два или три.
Ну хорошо, рассмотрим примеры квантовых вентилей. Один известный пример — вентиль Адамара, действующий на единичный кубит следующим образом:
Еще один пример — вентиль Тоффоли, который действует на три кубита так:
Или, если сказать словами, вентиль Тоффоли меняет третий кубит на противоположный в том и только том случае, если оба первых кубита равны 1. Обратите внимание: вентиль Тоффоли имеет смысл и в классических компьютерах.
Далее, Ши[69] показал, что Тоффоли и Адамар уже составляют универсальный набор квантовых вентилей. Если без формальностей, то это означает, что их одних вполне достаточно для квантового компьютера, поскольку при желании мы могли бы выстроить из них сколь угодно точную аппроксимацию любого другого квантового вентиля. (Или, строго говоря, любого вентиля, в унитарной матрице которого присутствуют только действительные, но не комплексные числа. Но в компьютерных делах это, как оказалось, не имеет значения.) Более того, согласно так называемой теореме Соловея — Китаева[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.