М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 84
Текст из файла (страница 84)
Даже когда эта удивительная структура была выявлена, стало ясно,что ее нельзя использовать для построения эффективного классического алгоритма разложения на множители, хотя, конечно, с квантовомеханическими средствами эту структуру можно использовать для построения эффективного алгоритма! Возможно, аналогичная структура скрыта и в других задачах, которые предположительно относятся к классу ХР1, например, в задаче об изоморфизме графов, и даже, возможно, в самих МР-полных задачах.
б.?. Ограничение алгоритмов в модели черного ящика 339 Упражнение 6.1Т (оптимальность для иеединстненных решений). Пусть задача поиска имеет М решений. Покажите, что для нахождения решения требуется 0(~/Й/М) обращений к оракулу. 6.7 Ограничение алгоритмов в модели черного ящика В завершение рассмотрим обобщение квантового алгоритма поиска, которое позволяет увидеть ограничения эффективности квантовых вычислений. В начале главы мы описали задачу поиска как нахождение такого и-битового целогочислах,чтофункция/: (0,1)" - (0,1)даетзначение/(х) = 1.Сэтойзадачей связана задача разрешения: существует ли такое число х, что /(х) = 1? Сложность последней задачи совпадает со сложностью задачи поиска; сама задача разрешения может быть сформулирована как вычисление булевой функции Р(Х) = Хо У Х1 У ..
Ч Хн и где символ «Ч» указывает двоичную операцию ОН (или), Хь ш /(к), а буквой «Х» обозначается множество (Хэ, Хп..., Хн-1). В более общем случае возможно вычисление не ОН, а какой-нибудь другой функции. Например, Р(Х) может быть одной из следующих функций: АМП, РАН1ТЪ' (сумма по модулю 2), МАЗОВХТУ (Р(Х) = 1 тогда и только тогда, когда большинство чисел Х» равно единице). Вообще говоря, можно рассматривать в качестве Р любую булеву функцию. Насколько быстро (по количеству запросов) можно вычислить классическим или квантовым образом зти функции, если имеется оракул для,5? Может показаться, что ответить на такой вопрос трудно, если о функции / ничего неизвестно.
Однако на самом деле многое можно определить даже в этой модели черного ящика, где средства, с помощью которых оракул выполняет свою задачу, считаются данными, а сложность измеряется только необходимым количеством обращений к оракулу. Анализ алгоритма поиска в предыдущем разделе показал один из подходов к таким задачам, однако существуег более мощный подход для определения сложности, выраженной в количестве запросов, — метод многочленов, который кратко будет описан ниже. Начнем с некоторых полезных определений. Детерминированная оракульная сложность Ю(Р) — это минимальное количество обращений к оракулу на классическом компьютере, необходимое для достоверного вычисления Р. Квантовый аналог Ол(Р) — минимальное число обращений к оракулу, необходимое кванпювому компьютеру, для вычисления достоверного Р. Поскольку квантовый компьютер по своей природе выдает вероятностные результаты, более интересной величиной является сложность в оракульной модели с ограниченной ошибкой Яз(Р) — минимальное количество обращений к оракулу, которое необходимо квантовому компьютеру для выдачи ответа, который равен Р с вероятностью ие менее 2/3.
(Величина 2/3 выбрана достаточно произвольным образом — на самом деле требуется только, чтобы вероятность была на сколько-то больше 1/2, т. е. чтобы она приближалась к единице после достаточного числа повторов.) Близким понятием является сложность безошибочных вероятностных алгоритмов в оракульной модели Яс(Р) — минимальное число обращений 340 Глава 6. Квантовые алгоритмы поиска к оракулу, необходимое квантовому компьютеру, чтобы либо выдать результат, который достоверно равен Г, либо (с вероятностью меньше 1/2) сообщить, что требуемый результат не получен. Все зти оценки должны выполняться для любой функции оракула / (другимй словами, для любого входа Х функции Г).
Обратите внимание на тот факт, что Яз(Г) < Яс(Г) (~ Як(Г) < Р(Г) ~ (1У. Метод многочленов опирается на свойства мультилинейных функций (над множеством депсгпеитеяы«ых чисел), которые представляют булевы функции. Все многочлены, которые будут рассматриваться в дальнейшем — зто функции с аргументами Хь Е (О, Ц, вследствие чего они являются мульти- линейными (посколькУ Хьз — — Хь).
БУдем говоРить, что многочлен Р: мл — К представляет функцию Г, если р(Х) = Г(Х) для всех Х Е (О,Ц~ (здесь символ «й» обозначает множество действительных чисел). Такой многочлен р всегда существует, можно построить его явно: (6.54) Тот факт, что представляющий Г многочлен р минимальной степени определен однозначно, читателю предлагается доказать самостоятельно (см. упражнение 6.18). Минимальная степень мультилинейного представления функции Г (она обозначается бей(Г)) является полезной мерой сложности функции Г. Например, известно, что де8(ОН) = Ж, де8(А510) = Ф, бей(РАШТУ) = Ж. Известно, что степень большинства функций равна Ж. Более того, было дока вано, что Р(Г) < 26 (Г)4 (6.55) Это утверждение задает верхнюю границу для реализации детерминированного классического вычисления при нахождении большинства булевых функций, Расширим зту идею, вводя следующее определение.
Многочлен приближает Г, если ~р(Х) — Г(Х) ~ < 1/3 для всех Х Е (О, Ц~. Минимальную степень такого приближающего многочлена обозначим деяГ. Подробные оценки важны в вероятностных классических вычислениях и, как мы увидим позже, в описании квантового случая. Известно, что де8(гагату) = Ф, дея(ОВ.) б 9(~/У) и бек(АМР) Е 9(~/У); (6.56) кроме того, Р(Г) < 216бе8(Г)е. (6.57) Оценки из уравнений (6.55) и (6.57) — известные оценки на момент изложе. ния данной задачи; их доказательство выходит за рамки книги. Дальнейшую информацию о них можно получить, ознакомившись с равд. «История и дополнительная литератураь. По-видимому, возможны и более точные оценки, однако приведенные выше результаты вполне достаточны для наших целей.
'Упражнение 6.18. Докажите, что многочлен минимальной степени, представляющий булеву функцию Г(Х), определен однозначно. 6.7. Ограничение алгоритмов в модели черного ящика 341 Упражнение 6.19. Покажите, что многочлен Р(Х) = 1 — (1 — Хо)(1 — Хт)... (1 — Хдг т) представляет функцию ОВ.. Многочлены естественным образом возникают в описании результатов квантовых алгоритмов. Представим выход квантового алгоритма Я, который выполняет Т обращений к оракулу О, в виде (6.58) Покажем, что амплитуды са — многочлены от переменных Хо, Хд,..., Хлг 1 степени не выше Т. Любой алгоритм Я может быть представлен с использова- нием квантовой схемы, показанной на рис. 6.10.
Состояние (тбс) непосредствен- но перед первым обращением к оракулу может быть записано в виде !Фо) = ~~~ (а;еу!т)!О) + аоу!к)!1)) (Я, (6.59) где первый индекс соответствует и-кубнтовому результату обращения к ора- кулу, следующий — одному кубиту, в который оракул помещает результат об- ращения к нему, а последний — оставшемуся (т — п — 1) рабочему кубиту, ис- пользуемому алгоритмом Я. После обращения к оракулу получим состояние (6.60) но, поскольку Х; равняется либо О, либо 1, можно это выражение переписать следующим образом: 'таЧ) = ~ ~[((1 — Хт)аюу + Х;ану) )т0) + ((1 — Х;)ану + Х;а;о;) (к1)] (т).
(6.61) 0и-л-Цкубитов Рис. 6.10. Общая квантовая схема для квантового алгоритма, который выполняет Т обращений к оракулу О. В этой схеме сто, стм, 11т — произвольные унитарные преобразования системы из тп кубитов, а оракул действует на (та+ 1) кубитов Обратите внимание, что в состоянии ~тбо) амплитуды состояний вычислительного базиса имели степень 0 по переменным Х, в то время как для ~грт) эта степень амплитуд была равна 1 (т. е. они линейны по Х). Важное наблюдение состоит в том, что никакая унитарная операция, которая выполняется в и кубитов 1 кубит г"-1 са(й).
а=о (Фт) = ~ (аког(а))Хк) + актуЯ~Хк Ю1)) (т), 342 Глава 6. Квантовые алгоритмы поиска алгоритме Я до или после обращения к оракулу, не может изменить степень этих многочленов, но каждое обращение к оракулу может увеличить эту степень не более чем на единицу. Таким образом, после Т обращений амплитуды представляют собой многочлены степени не выше Т. Кроме того, измерение окончательного результата (6.58) в вычислительном базисе дает ответ й с вероятностью Рь(Х) = ~се~э, а это действительнозначные многочлены от переменных Х степени не выше 2Т.
Общая вероятность Р(Х) получения единицы на выходе алгоритма равна сумме по некоторому подмножеству многочленов Рь(Х), т. е. она тоже представляет собой многочлен степени не выше 2Т. В том случае, когда алгоритм Я с достоверностью выдает правильный ответ, должно выполняться равенство Р(Х) = Г(Х), отсюда бей(Г) < 2Т; отсюда можно сделать вывод, что с1е8(Г) (6.62) В случае, когда алгоритм Я дает ответ с ограниченной вероятностью ошибки, можно видеть, что Р(Х) приближает Г(Х), поэтому бе8(Г) ( 2Т; отсюда следует неравенство Яэ(Г) > (6.63) Из оценок (6.55) и (6.62~ находим соотношение Ял(Г) > (6.64) Аналогично из (6.57) и (6.63) заключаем, что, (6.65) 13824 Это означает следующее: при вычислении булевых функций с использованием черного ящика квантовые алгоритмы могут дать е лучшем случае только полиномиальное ускорение по сравнению с классическими — и даже это не всегда возможно (поскольку дея(Г) имеет порядок Й(1У) для большинства функций), В то же время известно, что .0(Г) = Ф, если Г = ОВ., а для вероятностной классической сложности верно утверждение Я(Г) е 9(Ф), поэтому из оценок (6.63) и (6.56), а также известной конструкции квантового алгоритма поиска можно вывести, что Оэ(Г) е 6(~/М).
Это сгепеннбе ускорение достигается за счет квантового алгоритма поиска, а метод многочленов показывает, что результат, по-видимому, может быть обобщен на более широкий класс задач, но без дополнительного знания о стрркшуре функции 1 находящегося в черном ящике оракула невозможно экспоненпиэльное ускорение по сравнению с классическим алгоритмом. Упражнение 6.20. Покажите, что Яс(ои) > Ж (для этого постройте многочлен, представляющий функцию ОВ от выхода квантовой схемы, которая вычисляет ОВ с нулевой ошибкой). 6.7.
Ограничение алгоритмов в модели черного ящика 343 Задача 6.1 (нахождеиие минимума). Пусть хы..., хм — база данных из хранимых в памяти чисел (аналогичная описанной в равд. 6.5). Покажите, что на квантовом компьютере требуется только 0(1ой(1«') ~/У) обращений к памяти для того, чтобы найти минимальный элемент из списка с вероятностью по крайней мере 1/2. Задача 6.2 (обобщенньгй квантовый поиск). Пусть рг) — квантовое состояние; введем определение У~,~~ ш 1 — 2~ф(ф~. Таким образом, оператор У~,ц меняет фазу состояния ~ф) на противоположную (умножает это состояние на — 1), а состояния, ортогональные состоянию рг), оставляет без изменений.
1. Пусть имеется квантовая схема, реализующая такой унитарный опера- тор У, что У)0)еэ = (ф). Объясните, как реализовать оператор Ущ. 2. Пусть!ф1) =- 1, (фз) = (~0) — )1))/Л, (фз) = ()О) — «(1))/~/2. Допустим, что неизвестный оракул О выбирается из набора У~,р,>, У~~„>, Уь»»р Приведите квантовый алгоритм, который за одно обращение к оракулу идентифицирует его. ( Указание: воспользуйтесь сверхплотным кодированием.) 3. Исследование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
