М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 68
Текст из файла (страница 68)
Абрамс и Ллойд [12] разработали процедуру для моделирования фермионных систем многих тел на квантовом компьютере. Терхел и ДиВинченцо изучили проблему моделирования перехода системы в равновесное гиббсовское состояние [384]. Метод моделирования уравнения Шредингерв, описанный,во вставке 4.2, принадлежит Залке [430] и Виснеру [417]. Упражнение 4.25 было предложено Вандерсипеном; оно связано с работой Чау и Вильчека [110]. Авторы упр. 4.45 — Бойкин, Мор, Пулвер и др. [62]. Задача 4.2 принадлежит Готтесману, а 4.6 — Готтесмаиу и Чуангу [161]. Предположение о том, что использование начальных состояний, не принадлежащих вычислительному базису, может давать дополнительные возможности по сравнению с моделью квантовых схем (см.
равд. 4.6), было сделано Готтесманом и Нильсеном. Глава 5 КВАНТОВОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ Будь на квантах компьютперэг этпи,т Захотпят их все воры на свете. Наши цифры поймут, нашу почту прочтутп, Но мы квантовылт крипта ответим! Дж. и П. Шор Нашу почтпу читать будут скоро На компьютере квантовом воры, Но утешься: сперва Разлагать 22 Научитпься должнтя их приборыт тР. Штрассен Программирование — это такое же искусство, как сочинение стихов или музыки. Д. Кнут Наиболее ярким открытием в теории квантовых вычислений является на сегодняшний день то, что квантовые компьютеры оказались способны эффективно решать задачи, с которыми не могут справиться классические компьютеры.
Например, для разложения на простые множители п-битового целого числа с помощью лучшего из известных на момент написания книги классических алгоритмов (так называемого теоретико-числового решета) необходимо ехр(9(п'те 1ой~т~ п)) операций. Это количество экспоненциально по размеру числа, так что задача факторизации целого числа считается не имеющей эффективного решения на классическом компьютере: уже для чисел, выражаемых не слишком большим количеством цифр, найти разложение за разумное время немыслимо.
А вот квантовый алгоритм может выполнить эту задачу за 0(пг 1оя п 1оя1ок п) операций, так что квантовый компьютер может выполнять разложение чисел экспоненциально быстрее, чем классический. Этот ре- г Перевод этого и следующего стихотворного эпиграфа принадлежит В.Н.Панову.— Прим. ред 5.1. Квантовое преобразование Фурье 275 зультат важен и сам по себе, но интересен вопрос, который возникает в связи с этим: какие еще трудные для классических компьютеров задачи можно эффективно решить на квантовом компьютере? В этой главе будет рассмотрено хвантовов преобразование Фурье, являющееся основой для квантовой факторизации и многих других интересных квантовых алгоритмов. Квантовое преобразование Фурье, которому посвящен равд.
5.1, — это эффективный квантовый алгоритм для выполнения преобразования Фурье квантовомеханических амплитуд. Оно не ускоряет вычисление преобразования Фурье классических данных, но позволяет при определенных условиях найти хорошие приближения для собственных чисел унитарного оператора (задача определения собственного числа); об этом речь пойдет в разд 5.2.
Это позволит решить несколько других интересных задач, включая задачи нахождения порядка и факторизации (равд. 5.3). Определение собственного числа в сочетании с квантовым алгоритмом поиска приводит к решению задачи перечисления (подсчета решений в задаче поиска — см.
следуюшую главу). В завершающем главу рэзд. 5.4 обсуждается, как с помощью квантового преобразования Фурье можно решить задачу о скрытой подгруппе — обобщение задач определения собственного числа и нахождения порядка, частным случаем которой является задача о дисхрегпнам логарифме, — еще одна задача, считающаяся трудной для классического компъютера. 5.1 Квантовое преобразование Фурье Хорошая идея имеет обыкновение становиться со временем проще и при этом может использоваться для решения задач, отличных от тех, ради которых сна была придумана.
Р. Тарьян 1 Ж-1 уь ен — ~~~ х.е хи 7 чу з=с (5.1) 1В Один из наиболее удачных способов решения задачи в математике или информатике — преобразовать зту задачу в другую, решение которой уже известно. Среди такого рода преобразований имеется несколько используемых столь часто и в столь разнообразных ситуациях, что сами эти преобразования стали предметом изучения. Основное открытие в теории квантовых вычислений— это то, что некоторые из этих преобразований на квантовом компьютере вычисляются гораздо быстрее, чем на классическом, и именно благодаря этому стало возможно строить быстрые алгоритмы для квантовых компьютеров.
Один из примеров таких преобразований — дискретное преобразование Фурье. В обычных математических обозначениях входом для преобразования Фурье является вектор с комплексными компонентами хс,..., хм м где длина Ю фиксирована. На выходе получаются преобразованные данные, а именно вектор с комплексными компонентами ус,..., ум и определенный по формуле 276 Глава 5. Квантовое преобразование Фурье и его приложения Квантовое преобразование Фурье — это в точности то же преобразование, но немного по-другому записанное. В ортонормальном базисе ~0),..., ~Л вЂ” 1) кван- товое преобразование Фурье определяется как линейный оператор, действую- щий на базисных состояниях по формуле 1 И-1 )у) ~ егвпэ/и ~~ ) (5.2) Аналогичным образом действие этого оператора на произвольном состоянии можно записать в виде и-1 И-1 х )Я вЂ” + 1 уь(й), (5.3) щ+ г юд.р))(р) ь г оз,.,г,.(1)) ...
(р) гыод,у,-й„)1)) Ом",у ) ( 2в/г (5.4) Это представление настолько полезно, что порой его рассматривают как определение квантового преобразования Фурье. Ниже будет объяснено, что данное представление позволяет построить квантовую схему, эффективно вычисляющую преобразование Фурье, и это доказывает унитарность такого преобразования. Указанное представление позволяет понять алгоритмы, основанные на квантовом преобразовании Фурье. В качестве полезного побочного продукта будет получено (в упражнениях) классическое быстрое преобразование Фурье.
Эквивалентность формулы (5.4) и определения (5.2) устанавливается с помощью элементарной алгебры: где амплитуды уь — дискретные преобразования Фурье амплитуд ху. Хотя это и не очевидно из определения, этот оператор является унитарным и тем самым может быть реализован ца квантовом компьютере. Мы докажем унитарность преобразования Фурье, построив вычисляюшую его квантовую схему, которая, естественно, будет унитарна. Унитарность преобразования Фурье нетрудно доказать и непосредственно: Упражнение 5.1. Приведите прямое доказательство того, что линейное преобразование, заданное формулой (5.2), унитарно.
'Упражнение 5.2. Вычислите в явном виде преобразование Фурье п-кубитового состояния )00... 0). В дальнейшем будем считать, что М = 2", где и — целое число, и что базис ~0),..., ~2" — 1) есть вычислительный базис для и-кубитового квантового компьютера. Удобно записывать состояние ~Я в виде двоичного числа у = уДг... у„.
Это означает, что у = у~2" ~ + уг2" г + ... + уа2о. Можно такгке пользоваться обозначением О.нгц+г ... г~, для записи двоичных дробей д/2 + (4+,, +у Д ~+г. С помощью небольших алгебраических манипуляций можно представить квантовое преобразование Фурье в виде произведения 5.1. Квантовое преобразование Фурье 277 г"-~ )Я -+ — ~~~ е 0 7 )Й) (5.5) ь-о 1 1 — е~ о(~ = мэ )~Й~...Й„) а,=с ь„=с 1 1 э — ®е ~о ' ~Йд (5.7) ь,=с ь,.=с ~=~ и ~ 1 ь,=с е — (3 [)О) + е~""~ (1)~ (5.9) ам )О) -~- ез"'ав )1)) ((О) + сз"'с у"-'у" (1)) ((О) + ез'*с Ы"'" Я) (5.10) (5.6) (5. 8) Представление преобразования Фурье в виде (5.4) дает возможность легко по- строить схему, которая эффективно его вычисляет.
Эта схема изображена на рис. 5.1. Через Вь обозначено унитарное преобразование еэм/2 (5.11) Чтобы убедиться, что изображенная на рисунке схема действительно вычисляет квантовое преобразование Фурье, посмотрим, что происходит со входным состоянием Ц~... 1„). Применяя элемент Адамара к первому биту, получим состояние — „, (~0) + е""' ~ 1)) (1,...уа), (5.12) поскольку е~ 'с у' = — 1 при 7~ = 1 и +1 в противном случае. Применяя управляемое Вг, имеем (щ+ г сдд,р))~. (5.13) Далее будем применять управляемое Вз, управляемое Вч, и т.д. до Я„, добавляя на каждом шаге по биту к фазе первого из векторов )1).
По завершении этой процедуры придем к состоянию ()О) + еа сз У з ~1)) )7з... у ). (5.14) Теперь используем ту же процедуру для второго кубита. Элемент Адамара переводит в состояние 1 ((О) -1. еэ"'с.з У -З Я) ()0) + Р~~с.мф)(Уз У' ) (5 15) 278 Глава 5. Квантовое преобразование Фурье и его приложения а применение управляемых В2,..., В з даст состояние вида 1 2 2 ()О) + е 4'/з "4")1)) ()О) + е ' 4'"4")1)))Хз .у ) (5 16) Продолжая выполнять те же действия для остальных кубитов, придем в конце концов к состоянию 1 22/2 ~ — !О) + е * З'~' ' (1)) (!О) + езхс/*-/"!1)) ...
()О) + езвсн"!1)). (5.17) Теперь с помощью операций обмена (см. подразд. 1.3.4), ие показанных для простоты на рис. 5.1, обратим порядок кубитов. После этого получим состояние 1 !О) + ез™сн !1)) (р) + е2я$0 1 -ьу !1)) (!О) + е хснмз-4 )1)) (5 18) 2п/2 — ( Если сравнить данный результат с формулой (5.4), то окажется, что мы произвели квантовое преобразование Фурье, что и требовалось! Наша конструкция доказывает также унитарность квантового преобразования Фурье (поскольку каждый из использованных элементов унитарен). Явный пример схемы, осуществляющей квантовое преобразование Фурье на трех кубитах, приведен во вставке 5.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
