Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
Можно увидеть, что корни ключевых квантово-механических эффектов, приводящих к экспоненциальному ускорению в перечисленных выше квантовых алгоритмах, лежат в различных свойствах квантового перепутывания. Мы начнем с обсуждения двух основных ускоряющих эффектов; мы будем их называть «квантовое параллельное вычисление» (раздел 4.2.2) и «принцип локальных операций» (раздел 4.2.3).
4.2.2 Квантовое параллельное вычисление
Рассмотрим функцию f: А —> В, где А и В - конечные множества. Обычно А и В - это наборы из всех 2я строк из п битов (для некоторого и) - как, например, в алгоритмах Дойча и Саймона, - или множество целых чисел по модулю N (для некоторого АО, - как в алгоритме Шора. В наших приложениях А и В будут также Абелевыми группами. Пусть JfA (соответственно, JfB) будет гильбертовым пространством с ортонормальным базисом, состоящим из элементов А (соответственно, В). В контексте квантового вычисления, вычисление f соответствует унитарной эволюции Uf, которую обычно определяют как операцию на переводящей |о)|6) в |о)|6®/(а)) (см. Рис. 4.4).
Здесь ® обозначает абелеву групповую операцию на В.
\а) ----->
|Ь) ------
Рис. 4.4. Картина квантового логического элемента для унитарного преобразования Uj, соответствующего вычислению функции / Верхняя и нижняя линии представляют, соответственно, верхний и нижний регистры.
JfK - это пространство состояний входного регистра, а Ль - пространство состояний выходного регистра. Состояние на входе |а) не меняется, чтобы Uf была гарантированно унитарной операцией для
142 Концепция квантовых вычислений
любой возможной /. Если изначально b было равно 0, то f{a) можно считать непосредственно с выходного регистра с помощью стандартного измерения в данном базисе.
Предположим теперь, что входной регистр установлен в виде суперпозиции значений, скажем, в виде равной суперпозиции L |а) (где мы опустили нормировочный множитель). Тогда, применив Ufc b=О, мы получаем на выходе, благодаря линейности квантовой эволюции, суперпозицию ?|а)|/(а)) (см. Рис. 4.5).
Запустив Uj всего один раз, мы вычислили все значения / в суперпозиции. Это и есть процесс квантового параллельного вычисления, введенный Дойчем в [124]. Заметим, что состояние на выходе I |а)|/(а))- это, в общем случае, перепутанное состояние входного и выходного регистров. Разумеется, феномен суперпозиции - это свойство также и классических линейных систем, и любой эффект, зависящий только от суперпозиции, может быть легко применен и в классической системе. Однако, у феномена квантового перепутывания нет классического аналога, и его фундаментальная роль в квантовом вычислении была подчеркнута и исследована в [133, 134].
Пусть 5={0,1} обозначает аддитивную группу целых по модулю 2, и SB обозначает гильбертово пространство одного кубита, то есть, двумерное гильбертово пространство с заданным стандартным базисом обозначаемым {|0>, |1)}. SBn будет обозначать 2л-мерное гильбертово пространство SB ® ... ® SB п кубитов с базисом {| х):еВп}, задаваемым всеми /i-битными строками. Пусть Нобозначает фундаментальную одно-кубитную унитарную операцию
Рассмотрим функцию f:Bn—>В. В качестве примера вычисления с помощью квантового параллелизма, мы можем задать суперпози-
Рис. 4.5. Квантовое параллельное вычисление
(4.1)
Тогда
(4.2)
Квантовые алгоритмы 143
цию всех входных значений, а затем вычислить все значения / для этой суперпозиции следующим образом:
(i) Начнем со стандартного состояния п (входных) кубитов |0)...|0), и применим Н по отдельности к каждому кубиту. В результате получим во входном регистре состояние
it о
(ii) Добавим единственный (выходной) кубит в состоянии |0) и применим Uf . Получим состояние:
Заметим, что для (i) требуется только 0(п) операций, - то есть, полиномиальное число по п, - но этот шаг приводит к суперпозиции экспоненциально большого числа значений/ в (4.4).
Квантовое перепутывание играет также и еще одну роль в представлении суперпозиций. Если бы мы хотели построить общую суперпозицию 2" мод классически, нам бы понадобилось по одной системе для каждой моды, например, 2" колебательных мод колеблющейся струны. Эти моды будут соответствовать все более и более высоким уровням некоторого физического ресурса, например, энергии колеблющейся струны, и, представление общей суперпозиции 2" мод потребовало бы экспоненциального (по п) объема ресурса. В противоположность этому, в квантовой теории мы можем представить суперпозицию 2” мод с помощью п двухуровневых систем - благодаря эффекту перепутывания. Для представления такой общей суперпозиции необходим всего лишь линейный объем физических ресурсов, поскольку необходимо возбудить независимо не более чем п систем. Следовательно, хотя суперпозиция и встречается в классических системах, феномен квантового перепутывания приводит к экспоненциальной экономии физических ресурсов, необходимых для работы с большими суперпозициями.
4.2.3 Принцип локальных операций
В любом вычислении, будь то классическое или квантовое, обрабатываемая информация воплощается в идентичности физического состояния компьютера (его части). Сравним описание идентичности состояния п классических битов с его квантовой аналогией, состоянием п кубитов. Хотя п битов могут находиться в любом из экспоненциально большого числа состояний, можно полностью описать каждое состояние, задав всего лишь п битов информации. Напротив, в
