М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 85
Текст из файла (страница 85)
Рассмотрим более общий случай, когда задано к состояний ~ф1),..., ~фь), а неизвестный оракул О выбирается из набора Уь»1>,..., Уь»0. Сколько потребуется обращений к оракулу, чтобы идентифицировать его с высокой вероятностью? Задача 6.3 (понск по базе данных). Квантовый оракул выдает в качестве результата ~й, у ® Хь), если на его вход были поданы состояние (запрос из и кубвт) и один вспомогательный кубит ~р). Покажите, что с большой вероятностью все г7 = 2" битов множества Х могут быть получены с использованием только И/2+ ~/Ф обращений к оракулу.
Это дает общую оценку сверху Яэ(г') » (И/2 + 1/У для любого г'. Задача 6.4 (квантовый поиск и криптография). Квантовый поиск потенциально может быть использован для ускорения поиска криптографических ключей. Основная идея состоит в поиске по пространству всех возможных ключей для дешифрования, причем в каждом случае применяется ключ и осуществляется проверка, есть ли «смысл» в полученном при дешифровании оюбщении. Объясните, почему эта идея «не работает» при исследовании шифра Вернама (см. равд.
12.6). В каком случае она могла быть реализована для таких систем, как РЕЯ? (Для описания системы ВЕЗ см. например, (298) или [351].) 344 Глава 6. Квантовые алгоритмы поиска Краткое содержание главы ° Квантовый алгоритм поиска. Для задачи поиска с М решениями из Н = 2" возможностей следует приготовить состояние 2 ]х), после чего повторить 0(~/Й/М) раз операцию О ы На"УНа"О, где 0 — оракул, состояние [х) переводится в — [х), если [х) — решение; в противном случае зто состояние не меняется; У переводит состояние [О) в — [О) и оставляет все остальные состояния вычислительного базиса неизменными. Измерение дает решение задачи поиска с высокой вероятностью. ° Квантовый алгоритм перечисления. Предположим, что число решений М задачи поиска неизвестно.
Собственные числа оператора О равны ехр(хд), где з1п~(д/2) = М/Н. Процедура оценки фазы, основанная на преобразовании Фурье, позволяет оценить М с высокой точностью, используя 0(~/Л) обращений к оракулу. Квантовое перечисление, в свою очередь, позволяет определить, имеет ли задача поиска хотя бы одно решение, а также найти его, если решения действительно существуют, даже если их число заранее не известно. ° Полиномиальные оценки. Для задач, которые описываются как оценки везде определенных функций Г (в отличие от частично определенных), квантовые алгоритмы в модели черного ящика могут дать не более чем полиномиальное ускорение по сравнению с классическими. В частности, ЩЕ) ) [0(Р)/13824]~~ .
Более того, реализация квантового алгоритма поиска оптимальна: она имеет скорость Е(~/Ф). История и дополнительная литература Квантовый алгоритм поиска и его дальнейшее развитие и уточнение обязаны своим происхождением Гроверу [170], [171]. Бойер, Брассар, Хойер и Тапи [28] написали сыгравшую важную роль работу, в которой развит квантовый алгоритм поиска для случаев, когда число решений М больше единицы. Они также предложили идею квантового алгоритма перечисления, который позже был описан более подробно Брассаром, Хойером и Таплом [64].
В дальнейшем Моска [293] усовершенствовал его, используя процелуру определения собственного числа. На тот факт, что итерация Гровера может рассматриваться как произведение двух отражений, впервые было указано в обзоре Аароновой [9[. Гамильтониан (6.18) с непрерывным временем впервые исследовали Фари н Гутманн [160] (с точки зрения, отличающейся от нашей, — см. равд. 6.2). То, что алгоритм Гровера является наилучшим возможным алгоритмом поиска, основанным на использовании оракулов, было доказано Беннеттом, Бернштей- 6.7.
Ограничение алгоритмов в модели черного ящика 345 ном, Брассаром и Вазирани [22[. Приведенный здесь вариант этого доказательства базируется на результатах, полученных Бойером, Брассером, Хойером и Таином [28]. Залка [430] переработал эти доказательства, чтобы показать, что квантовый алгоритм поиска асимптотически является точно оптимальным. Метод многочленов для оценок быстродействия квантовых алгоритмов ввели в теорию квантовых вычислений Билс, Вурман, Клин и др.
[25]. Превосходное обсуждение также имеется в диссертации Моски [294]; на нем построена значительная часть рассуждений разд. 6.7. Некоторое количество результатов дано в этом разделе без доказательств, приведем более точные указания, относящиеся к ним: неравенство (6.55) в [25] приписывается Нисану и Смоленскому, однако его вывод до сих пор остается неопубликованным; утверждение (6.56) получено из теоремы, доказанной Патури [313]; неравенство (6.57) приведено в [25]. В работе [25] дана лучшая оценка, чем (6.65), но она требует использования понятия блоковой чуестеишааьиости„которое выходит за пределы тематики, рассматриваемой в нашей книге. Совершенно другой подход к оценкам квантовых алгоритмов, использующих черный ящик, с доказательствами, основанными на запутывании, провел Амбайнис [15].
Задача 6.1 восходит к Дюрру и Хойеру [121]. Задача 6.3 представлена в работе ван Дама [398]. Глава 7 КВАНТОВЫЕ КОМПЪЮТЕРЫ: ФИЗИЧЕСКАЯ РЕАЛИЗАЦИЯ Возможно, что в будущем компъютеры будут весить не больше 1,5 тонн. Популярная Механика, прогнозируя' стремительный марш науки, 1949 Я полагаю, что на всем мировом рынке мы не сможем продать больше пяти компьютеров. Томас Ватсон, президент 1ВМ, 1943 Большой интерес к теории квантовых вычислений и квантовой информации связан с надеждой на то, что устройства, обрабатывающие квантовую информацию, действительно могут быть реализованы в Природе. Иначе эта теория была бы просто математическим курьезом.
Однако, экспериментальная реализация квантовых схем, алгоритмов и каналов связи оказалась чрезвычайно сложной задачей. В этой главе мы рассмотрим основные принципы, которыми следует руководствоваться при разработке устройств, обрабатывающих квантовую информацию, и изучим несколько моделей таких устройств. В рэзд. 7.1 мы начнем с обзора компромиссов, на которые приходится идти при выборе физической системы для реализации квантового компьютера. Их обсуждение позволит нам в равд. 7.2 сформулировать условия, достаточные для реализации квантовых вычислений. Эти условия иллюстрируются примерами в равд. 7.3-7.7, где рассматриваются пять различных физических систем: простой гармонический осциллятор, фотоны и нелинейные оптические среды, квантовая электродинамика в резонаторах, ионы в ловушке, ядерный магнитный резонанс в молекулах.
Для каждой системы кратко обсуждаются соответствующая физическая аппаратура, гамильтониан, описывающий ее динамику, способы управления системой, позволяющие выполнять квантовые вычисления, и, наконец, ее принципиальные недостатки. Физика каждой из этих систем сама по себе является отдельной наукой и ее детальное изложение не является целью данной книги. Вместо этого мы приведем лишь тот круг понятий, который является существенным для теории квантовых вычислений и информации, чтобы можно было оценить и сложности экспериментальной реализации и потенциальные возможности каждого метода. Мы также надеемся, что анализ этих систем с точки зрения квантовой теории информации будет полезным и поучительным, поскольку он позволяет чрезвычайно просто выве- 7.1.
Основные принципы 347 сти некоторые важные физические законы. В заключительном равд. 7.8 кратко рассматривается ряд других физических систем, которые могут использоваться для реализации квантовых компьютеров: квантовые точки, сверхпроводящие гранулы и спины в полупроводниках. Для удобства читателя, желающего понять лишь основную идею того илн иного метода, в конце каждого раздела приводится его краткое содержание. 7.1 Основные принципы Каким требованиям необходимо удовлетворять при реализации квантового компьютера? В рэзд.
1.5 мы уже упоминали, что элементарный объект нашей теории — квантовый бит, или кубит (двухуровневая квантовая система), в принципе существует в Природе. Мы также кратко обсудили его возможные физические воплощения. Для того, чтобы реализовать квантовый компьютер, мы должны не просто выбрать «хорошее» физическое представление для кубита (в котором воплощены его квантовые свойства), но и найти систему, в которой динамика кубитов управляема. Более того, мы должны уметь приготовить некоторый набор начальных состояний н измерять конечный результат. Трудности при экспериментальной реализации связаны с тем, что, как правило, можно удовлетворить лишь какой-то части этих требований.
Например, монета может находиться в двух состояниях и является хорошим представлением бита. В то же время это плохое представление кубита, поскольку суперпозиции двух состояний живут очень короткое время. Отдельный ядерный спин во внешнем магнитном поле является очень хорошим представлением кубнта, поскольку суперпозиции состояний «спин вдоль поляь и «спин против поляь могут сохраняться вплоть до нескольких дней. Но создать квантовый компьютер на основе ядерных спинов очень сложно, поскольку связь отдельного спина с внешним миром слабая и измерить его ориентацию чрезвычайно трудно.
Тот факт, что мы сталкиваемся с несколькими почти не совместимыми требованиями, является достаточно общим: чтобы сохранять квантовые состояния, квантовый компьютер должен быть хорошо изолирован от окружающей среды. Но в то же время его кубиты должны быть достаточно доступны, чтобы можно было выполнять вычисления и считывать результаты. При реализации квантового компьютера нужно балансировать между этими почти несовместимыми требованиями. Поэтому правильный вопрос не в том, как построить квантовый компьютер, а в том, насяо«ько хороший квантовый компьютер возможно построить.
Какие физические системы являются перспективными с точки зрения обработки квантовой информации? При оценке перспективности той или иной системы ключевую роль итрает понятие хеаишоеого п«ума, или поп«ери когереитиости (гл. 8), т. е. процессов, нарушающих желаемую эволюцию системы. Действительно, наибольшая длина квантового вычисления может быть грубо представлена как отношение тн к т, . гк это время, в течение которого в системе сохраняется квантовая когерентность, а т„„это длительность выполнения элементарного унитарного преобразования (действующего на небольшое 348 Глава 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
