Научная литература
booksshare.net -> Добавить материал -> Физика -> Бауместер Д. -> "Физика квантовой информации" -> 57

Физика квантовой информации - Бауместер Д.

Бауместер Д., Экерт А., Цайлингер А. Физика квантовой информации — М.: Постмаркет, 2002. — 376 c.
ISBN 5-94057-017-8
Скачать (прямая ссылка): fizikakvantovoyinformacii2002.pdf
Предыдущая << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 151 >> Следующая

Квантовые алгоритмы 151
Экспоненциальное разделение между классическим и квантовым вычислением происходит только в предельном случае е = 0. Можно возразить, что предельная ситуация не имеет физического смысла, так как любой компьютер, будучи физическим прибором, не может быть абсолютно изолирован от своего окружения. Следовательно, всегда есть (небольшая) вероятность того, что он сработает неправильно - например, в какой-то момент какой-нибудь бит может поменять значение под воздействием космического луча. Поэтому было бы очень интересно найти такую задачу, вычислительная сложность которой в квантовом и в классическом случае различалась бы экспоненциально, даже если допустима небольшая ошибка. Первый такой пример был дан Бернстайном и Вацирани [140]. С помощью рекурсивной конструкции они описали вычислительную задачу, которая могла бы быть решена на квантовом компьютере за полиномиальное время, но которой потребовалось бы 0(и'°8") шагов на классическом компьютере. Затем Саймон [141] описал более простую задачу, которую на квантовом компьютере можно было бы решить за время 0(п2), но которой на классическом компьютере требовалось полное экспоненциальное время (т.е. 0(2")). Апофеозом этой линии развития стал алгоритм Шора [36] для факторизации, который устранил также и зависимость от оракула. Алгоритм Шора дает метод факторизации целого числа N за число шагов, полиномиальное (с менее, чем кубической зависимостью) от числа цифр (log N) в N, и дает правильный результат с вероятностью (1 - ё) для любого заданного е > 0. Несмотря на многочисленные попытки, которые делались в течение нескольких сотен лет (такими выдающимися математиками, как Гаусс, Лежандр, Ферма, и другими), мы не знаем классического полиномиального по времени вероятностного алгоритма для решения этой задачи. В отличие от алгоритмов Дойча и Саймона, алгоритм Шора не связан с оракулом. Однако это не доказывает абсолютного экспоненциального превосходства квантового вычисления над классическим, поскольку нет доказательства того, что не существует классического полиномиального по времени алгоритма для факторизации (а есть только огромное число неудавшихся попыток сконструировать такой алгоритм!)
4.2.5. Преобразование Фурье и периоды
Квантовый алгоритм факторизации Шора и алгоритм Саймона будут существенным образом зависеть от замечательной способности квантового компьютера определять период заданной периодической функции. Мы проиллюстрируем используемые при этом идеи в следующем базовом примере. Предположим, что у нас есть черный ящик,
152 Концепция квантовых вычислений
который вычисляет заведомо периодическую функцию / : ZN->Z периода г:
Вспомним, что ZN обозначает группу целых чисел по модулю N, и сложение здесь делается по модулю N. Мы также предполагаем, что / не принимает дважды за период одного и того же значения. Заметим, что (4.11) может выполняться, только если N делится на г без остатка.
Наша цель - определить г. В классическом подходе (при отсутствии дальнейшей информации о /), мы можем только подставлять в черный ящик различные значения х в надежде получить два одинаковых ответа, и, через них - информацию о периоде функции. В общем случае, чтобы с высокой вероятностью получить два одинаковых значения, потребуется 0(N) случайных попыток. С помощью квантовых эффектов мы сможем найти г всего лишь за 0((log АО2) шагов, что представляет собой экспоненциальное ускорение по сравнению с классическим алгоритмом.
Для начала, используем квантовое параллельное вычисление, чтобы получить все значения /в равной суперпозиции. В результате получим состояние
Хотя это состояние содержит в себе все свойства периодичности функции/, пока неясно, как извлечь из него информацию об г! Если мы измерим состояние второго регистра и обнаружим, например, число у0, то состояние в первом регистре сократится до равной суперпозиции всех таких |х), так чтоДх) =у0. Если х0 - одно из таких х, и N=Kr, то мы получим в первом регистре периодическое состояние
Здесь важно отметить, что число 0 <х0 < г-1 было сгенерировано случайным образом, поскольку все значения у0 функции / могли выпасть с равной вероятностью. Поэтому, если теперь измерить значение этого регистра, результатом будет случайно выпавшее число между 0 и N--1, и он не даст нам абсолютно никакой информации об г!
Разрешение этой трудности состоит в использовании преобразования Фурье, которое, как известно, даже в классическом случае способно выловить из набора данных периодические формы, не взирая на то, как эти формы сдвинуты. Дискретное преобразование Фурье ?7 для целых чисел по модулю N - это унитарная матрица NxN, элементы которой равны
f(x + r) = f(x) для всех х.
(4.11)
(4.12)
(4.13)
Квантовые алгоритмы 153
^~}ке
2ni
аЬ
(4.14)
Если мы применим это унитарное преобразование к состоянию | у/), описанному выше, то получим [144]
1 ^ 2 *М
¦F\yf)=-rlLe г
1=0
J—
(4.15)
Важный момент, который здесь надо отметить - это то, что в метках кет-векторов больше не появляется случайный сдвиг х0 (см. Рис. 4.7).
Предыдущая << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 151 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed