М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 69
Текст из файла (страница 69)
)с)+е'~ч-" !О !О)+е а-* )!) О» р),.еь а-ьь р> )О) + е'""" !О Рис. 5.1. Эффективная схема, вычисляющая квантовое преобразование Фурье. Эта схема легко получается из представления квантового преобразования Фурье в виде произведения (бл). На рисунке не отражены операции обмена в конце схемы, обращающие порядок следования кубитов, а также нормализующие множители 1/т/2 в выходных состояниях. Сколько элементов используется в нашей схеме? Сначала мы применяем элемент Адамара и (п — 1) условный фазовый сдвиг к первому кубиту — всего и элементов. Затем мы применяем элемент Адамара и (и-2) условных фазовых сдвига ко второму кубиту — итого (и + (и — 1)) элементов.
Продолжив вычисление, получим, что используются и+ (и — 1) +... + 1 = п(п+ 1)/2 элементов и элементы, необходимые для обращения порядка кубитов. Для выполнения последней задачи требуется не более и/2 обменов, а для каждого обмена нужно три элемента снот. Следовательно, такая схема дает алгоритм для выполнения квыпового преобразования Фурье, работающий за время 9(п ). 5.1. Квантовое преобразование Фурье 279 Вставка 5.1. Трехкубитовое квантовое преобразование Фурье Возможно, стоит рассмотреть конкретный пример схемы, осуществляю- щей квантовое преобразование Фурье на трех кубитах.
Напомним, что Я и Т вЂ” элементы сдвига фазы я/8. В матричном виде преобразование Фурье в этом случае можно записать следующим образом (положив и = ег"'~з = Д): 1 1 1 г 1 ыг ы4 ,„з,„б 4 5 „2 б 4 7 б 1 1 ыг 4 б 1 4 4 7 4 ,„г 5 4 1 1 1 5 б 7 „2 ~4 ~б 7 2 5 4 1 4 б з б „4 2 3 „2 „1 1 ~/8 (5.19) Стоит сравнить это с классическим случаем: лучшие известные классические алгоритмы для вычисления дискретного преобразования Фурье 2"-компонентного вектора, такие, как бььсглрое преобразование Фурье (РРТ), используют В(п2") элементов.
Таким образом, для выполнения преобразования Фурье на классическом компьютере необходимо экспоненциально больше операций, чем для ре1пения той же задачи на квантовом компьютере. На первый взгляд это выглядит потрясающе, поскольку преобразование Фурье является ключевым шагом во многих прикладных задачах обработки данных. Например, при компьютерном распознавании речи первый шаг в распознавании фонемы состоит в том, что к оцифрованному звуку применяется именно преобразование Фурье.
Может быть, стоит применить квантовое преобразование Фурье для ускорения этих вычислений? К сожзлению, неизвестно никакого способа это сделать: проблема в том, что в квантовом компьютере непосредственно измерить амплитуды невозможно, так что не существует способа найги амплитуды состояния, полученного преобразованием Фурье из исходного.
Более того, нет, вообще говоря, и способа приготовить исходное состояние (то, к которому мы хотим применить квантовое преобразование Фурье) в нужном виде. Так что найти црименения квантовому преобразованию Фурье — задача более деликатная, чем можно было бы предположить. В этой и следующей главах мы приведем примеры нескольких алгоритмов, основанных на более тонком применении квантового преобразования Фурье. 280 Глава 5. Квантовое преобразование Фурье и его приложения лпражнение 5.3 (классическое быстрое преобразование Фурье).
Предположим, требуется получить на классическом компьютере преобразование Фурье вектора с 2" комплексными компонентами. Проверьте, что при непосредственном применении формулы (5.1) для этого потребуется 6(2»") элементарных арифметических операций. Найдите способ (основанный на формуле (5.4)) сократить число таких операций до 9(п2").
упражнение 5.4. Разложите элемент «управляемое Я»» в композицию однокубитовых и скот-элементов. Упражнение 5.5. Постройте квантовую схему, реализуюшую обратное квантовое преобразование Фурье. э'пра»кнение 5.6 (приближенное квантовое преобразование Фурье).
Очевидно, что в схеме, реализующей квантовое преобразование Фурье, применяются элементы экспоненциэльной (в зависимости от числа кубитов) точности. На самом деле, однако, ни в какой квантовой схеме полиномиального размера такая точность не требуется. Пусть, например, У вЂ” идеальное квантовое преобразование Фурье на и кубит и»' — преобразование, которое получится, если элементы «управляемое г»»» реализованы с точностью Ь = 1/р(п), где р(п) — многочлен.
Покажите, что ошибка Е(У, '»') ьз шах~,р> ~((У вЂ” Ъ")((ф) Н имеет порядок 6(и /р(п)) и тем самым полиномиальной точности в каждом элементе достаточно, чтобы гарантировать полиномиальную точность схемы в целом. 5.2 Определение собственного числа Преобразование Фурье играет ключевую роль в процедуре, известной под названием олределекпе собстеенноао числа, которая в свою очередь является ключом ко многим квантовым алгоритмам. Предположим, что унитарный оператор У имеет собственный вектор ~и) с собственным числом е~ "', где значение ~р неизвестно. Цель процедуры определения собственного числа — найти оценку для ~р.
Мы получим такую оценку в предположении, что нам доступны черные ящика (называемые также оракулами), способные приготовить состояние ~и) и выполнить операцию «управляемое У» для целого неотрицательного (. Поскольку используются черные ящики, определение собственного числа не является само по себе настоящим квантовым алгоритмом: его нужно представлять как «подпрограмму» (или «модуль»), которая в сочетании с другими подпрограммами может решать интересные вычислительные задачи.
В конкретных приложениях процедуры определения собственного числа будем действовать именно так: описывать, как можно осуществить операции, выполняемые черными ящиками, и затем использовать определение собственного числа для решения действительно интересных задач. В данный момент, однако, содержимым черных ящиков мы интересоваться не будем. 5.2. Определение собственного числа 281 —,~з(!О)+2 * Р!1))(!О)+е ' ~)1)) ...
(/О)+е * "!1)) = Э'-1 э=с (5.20) Про второй регистр мы здесь не упоминаем, поскольку на протяжении всего вычисления он остается в состоянии 1и). Ю> + е алей е> П > Первый регистр (г нубитов) Р> + е лагг а> 11 > !0) +еаый и П) 6) + е алю М П ) !0> 10> пеРвый РегистР !и) 1и) Рис. 5.2. Первый этап процедуры определения собственного числа В правой части опущены нормирующие множители 1/~/2 упражнение 5.7. Вы лучше поймете, как работает схема на рис.
5.2, если покажете, что изображенная на нем последовательность управляемых У переводит состояние 1Я!и) в 1,у) УУ!и). (Отметим, что зто верно и в том случае, если 1и) не является собственным вектором У.) Второй этап процедуры определения собственного числа состоит в том, что к первому регистру применяют обратное квантовое преобразование Фурье. Чтобы это сделать, надо обратить схему для квантового преобразования Фурье В процедуре квантового определения собственного числа используются два регистра.
Первый содержит 1 кубитов, изначально находящихся в состоянии 1О). Выбор значения 1 зависит от двух факторов: требуемой точности приближенного значения уэ и необходимой вероятности успешного выполнения проце пуры. Зависимость | от этих параметров будет ясна из последующего анализа. Второй регистр содержит столько кубитов, сколько нужно для того, чтобы записать в него 1и), и его начальное состояние есть !и). Определение собственного числа проводится в два этапа. В начале применяется схема, изображенная на рис. 5.2. Начинается работа этой схемы с того, что к каждому биту первого регистра применяется элемент Адамара, а затем ко второму регистру — управляемые варианты операции У, возведенной в степени, равные последовательным степеням двойки.
Легко видеть, что конечное состояние первого регистра равно 282 Глава 5. Квантовое преобразование Фурье и его приложения 1 21/г — !О)+егслср,(1))(!О)+с~ 1свч-,тч(1)) ... (/0)+ег аснар, р,(1)) (52ц — ( На втором этапе определения собственного числа применим обратное преобра- зование Фурье. Если теперь сравнить (5.21) с формулой (5.4) для преобразова- ния Фурье, то на втором этапе получим состояние (ут... <ра); теперь измерение в вычислительном базисе дает точное значение со! (0) (и) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
