Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
Начнем с ряда из п (входных) кубитов и одного (выходного) кубита. Пусть вначале все кубиты в находятся стандартном состоянии |0). Применим Н к каждому из входных кубитов. Согласно (4.3), это приведет к равной суперпозиции всех возможных значений на входе в первых п кубитах. Точно также как и в предыдущем случае, приготовим последний (выходной) кубит в состоянии 1/л/~2(|0>—11 >). Затем предложим получившееся состояние л+1 кубитов оракулу. Это формально совпадает с (4.9) с той разницей, что теперь х пробегает все значения из Вп, а не из В. После работы оракула первые п кубитов будут в состоянии
f .B" ->В
(4.10)
Квантовые алгоритмы 149
(Попутно заметим, что в оригинальной версии алгоритма Дойча [138] 1992 года было необходимо обратиться к оракулу два раза, чтобы произвести состояние |<^)). Далее, если / была постоянной функцией, то | окажется в такой же равной суперпозиции всех возможных |х) с общим знаком плюс или минус. В то же время, если/ была сбалансирована, то | <^) окажется суперпозицией, в которую половина членов будет входить со знаком плюс, а другая - со знаком минус. Эти две суперпозиции взаимно ортогональны, и существует соответствующее измерение над |<^), которое с определенностью отличит сбалансированную функцию от постоянной.
Мы должны описать в явном виде, как можно выполнить это измерение. Мы не можем предполагать, что можно выполнить произвольное измерение в произвольном квантовом алгоритме за один вычислительный шаг (точно так же, как нельзя предполагать, что за один шаг можно выполнить произвольную унитарную операцию). Чтобы оценить сложность произвольного вычисления, предположим, что мы можем только детектировать состояния |0) или |1) любого кубита в вычислительном базисе, и это считается одним вычислительным шагом. Любое общее измерение можно свести к последовательности таких стандартных измерений, если сначала унитарно перевести собственный базис измерения в вычислительный базис, а затем последовательно считать биты. Сложность измерения тогда определяется как число шагов, необходимых, чтобы выполнить унитарное преобразование, плюс число кубитов, которые надо считать.
В нашем случае измерение, которое отличает сбалансированные
от постоянных, можно осуществить следующим образом. Вспомним, что операция Н обратна самой себе (НН = Г), и что Н, примененная к каждому кубиту состояния |0)|0)...|0) даёт равную суперпозицию всех |х) (см. 4,3). Следовательно, если Н применить к этой суперпозиции еще раз, то получится состояние |0)|0)...|0). Поэтому мы применяем Н к каждому кубиту состояния |<^) (на это требуется п шагов). Если функция / была постоянной, то получится состояние ±|0)|0)...|0). Если же/была сбалансирована, то получится какое-то ортогональное состояние, то есть, суперпозиция |х), включающая в себя какое-то х Ф 00...0. Таким образом, мы считываем каждый из п кубитов и смотрим, все ли они равны 0, или нет (еще п шагов), и на этом измерение завершается. В целом, квантовому алгоритму Дойча требуется 0(п) шагов (включая одно обращение к оракулу) для того, чтобы наверняка отличить сбалансированную функцию от постоянной, тогда как любому классическому алгоритму для достижения той же цели требуется 0(2”) шагов.
Алгоритм Дойча является так называемым «результатом ора-
150 Концепция квантовых вычислений
куда» или «относительным» результатом (по отношению к оракулу). Он не дает абсолютного экспоненциального разделения между классическим и квантовым вычислением, но дает такое разделение, только если сделать некоторые дальнейшие (правдоподобные, но недоказанные) вычислительные предположения относительно того факта, что у нас нет доступа к внутреннему устройству оракула. Вследствие этого предположения, если нам дана программа, вычисляющая f то не существует механического способа использовать общий синтаксис такой программы, чтобы узнать, сбалансированна /или постоянна, быстрее, чем запустив эту программу достаточное число раз. Конечно, для вычисления постоянной функции требуется только очень короткая программа, которую легко распознать. Но можно столкнуться и с очень сложной и запутанной программой, которая также будет вычислять постоянную функцию - так, что этот факт будет очень трудно увидеть из ее синтаксиса. Хотя наше предположение весьма правдоподобно, оно остается недоказанным, поскольку очень трудно анализировать такие алгоритмы, которые в качестве входных данных рассматривают синтаксис программы! Заметим, что, если бы можно было доказать абсолютное экспоненциальное разделение между классическим и квантовым вычислениями, то это бы разрешило некоторые старые фундаментальные вопросы в классической теории вычислительной сложности (например, это бы означало, что Р Ф PSPACE; см. определение этих терминов в [131]). Похоже, что очень трудно формально доказать экспоненциальное превосходство квантового вычисления над классическим.
Еще одна важная черта алгоритма Дойча состоит в следующем. Если не требуется, чтобы алгоритм работал совершенно, то есть, если мы допускаем некоторую (произвольно малую) ошибку, то показанное здесь экспоненциальное разделение между классическим и квантовым вычислениями исчезает. Дело в том, что для любого s > О существует классический (вероятностный) алгоритм, который за фиксированное (не зависящее от и!) число шагов для любой заданной/отличит сбалансированную функцию от постоянно с вероятностью (1 - е). Этот алгоритм работает следующим образом. Мы оцениваем/для некоторых К случайно выбранных входных значений. Если все ответы одинаковы, то считаем, что/- «константа». В противном случае считаем, что она сбалансирована. Небольшое размышление показывает, что ответ «сбалансирована» будет верен всегда, а ответ «константа» будет верен с вероятностью ошибки, не превышающей 1/2*. Таким образом, для любого заданного е > О выбираем К настолько большим, чтобы было (1/2*) < s. Заметим, что К не зависит от п, так что К запросов оракула приводят к постоянному числу шагов в алгоритме.
