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

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

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

Учитывая сложность и масштаб некоторых задач из класса NP [132], маловероятно, что их можно решить за полиномиальное вре-
Квантовые алгоритмы 165
мя. Однако, несмотря на огромное внимание, этот факт до сих пор не доказан! Заметим, что в каждом случае приходится привлекать те или иные особенные математические свойства данной структуры - например, решение задачи о гамильтоновой цепи было бы равносильно доказательству некоей новой глубокой теоремы в теории графов.
Вернемся теперь к алгоритму поиска Гровера. Здесь требовалось, чтобы база данных была неструктурированной (в противоположность тому, что только что было описано), и, тем не менее, с помощью квантовых методов, мы достигли ускорения в квадратный корень числа шагов по сравнению с прямым полным классическим поиском. Это ускорение можно применить к поиску вслепую в любой задаче из класса NP. Критический вопрос здесь таков: можно ли ускорить поиск в неструктурированном пространстве с экспоненциально большим числом элементов еще сильнее, используя квантовые эффекты каким-то еще более хитрым образом? Например, мы видели, что можно создать экспоненциально большие суперпозиции за линейное время (4.3), и что можно использовать эти суперпозиции, чтобы за один запрос проверить экспоненциально большое число значений функции (см. (4.4)). В первые дни теории квантовых вычислений была надежда, что этот эффект может привести к методу просмотра за полиномиальное время экспоненциально большого пространства возможностей, что привело бы к квантовому методу решения любой задачи из NP за полиномиальное время. Например, если дан граф, то мы можем рассматривать суперпозиции любых возможных цепей -но можно ли использовать этот эффект, чтобы с высокой вероятностью определить, существует или нет гамильтонова цепь? Эта надежда была разбита в работе [155] Беннетом, Бернстайном, Брассаром и Вацирани, которые строго доказали, что никакой квантовый процесс не может ускорить неструктурированный поиск сильнее, чем ускорение в квадратный корень, которое достигается в алгоритме Гровера. Грубо говоря, их идея состоит в следующем. Хотя мы и можем проверить за один запрос экспоненциально большое число кандидатов, находящихся в суперпозиции, но, в общем случае, регистрация желаемого свойства произойдет с экспоненциально малой амплитудой из-за экспоненциально большого числа элементов в суперпозиции. Следовательно, чтобы зарегистрировать свойство с любым постоянным уровнем вероятности, придется повторить весь процесс экспоненциально большое число раз.
Таким образом, в контексте квантового вычисления, точно так же, как и в классическом вычислении, если мы хотим решить задачу из класса NP за полиномиальное время, то мы должны каким-то хитрым
166 Концепция квантовых вычислений
образом использовать структуру задачи. Например, экспоненциальное ускорение в алгоритмах Саймона и Шора достигается с использованием специальных математических свойств теории периодичности через технику Фурье-анализа. К сожалению, оказывается, что решение важного вопроса о связи всего класса NP с вычислимостью за полиномиальное время выглядит в квантовом контексте ничуть не ближе, чем в контексте классической теории вычислительной сложности.
4.3 Квантовые ЛЭ и квантовое вычисление с захваченными ионами
Дж.И. Цирак, П.Цоллер, О.Ф.Поятос
4.3.1 Введение
Из того, что обсуждалось выше, ясно, что квантовое вычисление может быть удивительно мощным инструментом. Весь вопрос в том, можем ли мы воплотить в реальность основные элементы квантового вычисления - такие, как, например, квантовые логические элементы - и, если да, то в каких физических системах. Вместо общего обсуждение проблемы, мы сосредоточимся на одном конкретном примере. Мы опишем в некоторых деталях проекты, связанные с созданием квантового компьютера на основе системы захваченных ионов [156, 157]. В этой схеме каждый кубит - это суперпозиция основного электронного состояния (|0)) и возбужденного (метастабильного) состояния (|1)) иона в ловушке (см. Рис. 4.9). Будет показано, что набор ионов, двигающихся в линейной ловушке и взаимодействующих с лазерным светом - это реальная физическая система, на основе которой может быть создан квантовый компьютер.
Рис. 4.9. Двойная резонансная структура внутренних уровней одного иона. Два из этих уровней, вместе со слабым переходом между ними, действуют как кубит (|0), (1)), тогда как третий уровень, |2), связанный с состоянием |0) дипольно-разрешенным переходом, служит для охлаждения и измерения, с помощью метода квантового скачка.
|2>
Лазерное охлажде1 Измерение
|е> (|1>)
Переходы в кубите Рабиевские переходы
|g> (|0>)
Квантовые ЛЭ и квантовое вычисление с захваченными ионами 167
4.3.2 Квантовые логические элементы с захваченными ионами
Мы рассмотрим ситуацию, когда N ионов содержатся в линейной ловушке Пауля (со скрещенными полями), которая может захватывать и держать ионы с помощью комбинации статического и переменного электрических полей (см. главу 5). Ионы, в основном, двигаются вдоль оси ловушки, так как в этом направлении захватывающий потенциал довольно слаб, и взаимодействуют с различными лазерными полями
Предыдущая << 1 .. 57 58 59 60 61 62 < 63 > 64 65 66 67 68 69 .. 151 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed