М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 77
Текст из файла (страница 77)
С учетом этого соглашения запишем действие оракула таким образом: (6.3) Будем говорить, что оракул помечаегв решения задачи поиска, если он сдвигает фазу этих решений. Оказывается, для получения ответа в задаче поиска из Ж элементов с М решениями на квантовом койпьюгере необходимо применить оракул 0(~/М/ММ) раз.
Это обсуждение оракула без объяснения принципа его действия достаточно абстрактно и даже, возможно, загадочно. Создается впечатление, что оракул заранее знает ответ в задаче поиска; тогда непонятно, какой смысл в квантовом алгоритме поиска, основанном на сведениях, полученных от такого оракула. Ответ прост: существует разница между нахождением решения задачи 6.1. Квантовый алгоритм поиска 313 поиска и способностью распознать его; ключевой момент заключается в том, что бывают ситуации, в которых для распознавания решения не обязательно уметь его находить. Простым примером, иллюстрирующим сказанное выше, является задача факторизации. Представьте себе, что имеется большое число т, о котором известно, что оно является произведением двух простых чисел р и д — схожая ситуация возникает при попытке взломать ВЯА-криптосистему с открытым ключом (см.
Приложение 5). Очевидный путь для вычисления р и д на классическом компьютере заключается в поиске среди всех чисел от 2 до т'~Я наименьшего из двух делителей числа т. Другими словами, мы должны попробовать последовательно разделить т на все числа в диапазоне от 2 до т'~Я, пока не найдем меньший из двух простых делителей числа т. Другой простой делитель после этого может быть получен делением числа т на найденный меньший делитель. Очевидно, что в алгоритме, основанном на поиске, для нахождения делителя на классическом компьютере требуется порядка тгУ операций деления.
С помощью квантового алгоритма поиска данный процесс можно ускорить. По определению, действие оракула на входном состоянии ~х) заключается в делении с остатком числа т на х, проверке, равен ли остаток нулю, и изменении значения кубита оракула в этом случае. Применение квантового алгоритма поиска вместе с оракулом приводит к нахождению меньшего из двух простых делителей с большой вероятностью. Однако чтобы заставить указанный алгоритм работать, необходимо создать эффективную схему, реализуюшую этот оракул. Решение задачи представляет собой упражнение из области обратимых вычислений. Начнем с определения такой функции 1(х), что Г"(х) ы 1, когда х делит т, и )'(х) ы 0 в противном случае; зяачение 1(х) показывает, удалось ли выполнить деление без остатка. Используя методы обратимых вычислений, обсуждавшиеся в подразд.
3.2.5, построим следующую классическую обратимую схему. Она переводит (Х, у) (во входном регистре установлено значение Х, в однокубитовом выходном регистре — у) в (х, д йя 1(х)). Эта схема представляет собой простую модификацию обычной (необратимой) классической схемы для проверки делимости. Размер такой же (с точностью до умножения на двойку), как у классической необратимой схемы, поэтому упомянутые обе эти симы примерно равноценны. Кроме того, из классической обратимой схемы можно легко получить квантовую: она будет переводить состояние )х) ~д) в ~х) ~д Ю з'(х)), как и требуетая для оракула. Ключевой момент состоит в том, что даже без нахождения просгпых делителей числа т можно построить е ленам виде оракул, который распознает решение задачи поиска, когда оно ему предзлелено. С помощью этого оракула и квантового алгоритма поиска можно провести поиск в диапазоне от 2 до тг1Я, используя Я(т'14) обращений к оракулу.
Таким образом, необходимо выполнить пробное деление порядка т1~4 рзз вместо т'~~ рзз, как в случае использования классического алгоритма. Разложение на простые множители — интересный умозрительный, но отнюдь не практический пример: существуют классические алгоритмы, которые работают гораздо быстрее, чем простой перебор всех возможных чисел с про- 314 Глава 6. Квантовые алгоритмы поиска 6.1.2 Процедура Схема действия алгоритма поиска показана на рис. 6.1.
Алгоритм надлежа шдм образом использует одиночный и-кубитовый регистр. Детали внутреннего устройства оракула, включая возможную потребность в дополнительных рабочих кубитах, не являются важными для описания самого алгоритма. Цель алгоритма — найти решение задачи поиска с минимально возможным числом обращений к оракулу. п кубитов Ю) изиерение рабочее пространство оракула Рис. 6.1. Схема квантового алгоритма поиска Оракул может использовать рабочие кубиты для своих целей, однако для анализа квантового алгоритма поиска рассматривается толью я- кубитовый регистр В начале алгоритма компьютер находится в состоянии )0)е". С помощью преобразования Адамара компьютер переводится в состояние лг-1 )г)г) = —, ~ь )х).
(6.4) Дальше в квантовом алгоритме поиска последовательно применяется квантовая подпрограмма, называемая пизерацисй (пап оператором) Гроеера (будем обозначать ее буквой «с«а). Итерация Гровера, квантовая схема которой изображена на рис. 6.2, может быть разбита на четыре шага: 1. применение оракула О, 2. применение преобразования Адамара НЕ", 3.
применение к регистру условного сдвига фазы — каждое состояние вычислительного базиса, за исключением )О), приобретает фазовый сдвиг -1: )х) — -(-1)а")х), (6.5) 4. применение преобразования Адамара Не". веркой, являются ли они делителями числа т. Тем не менее он иллюстрирует общую идею применения квантового алгоритма поиска: классический алгоритм, использующий метод поиска, можно ускорить с помощью квантового поиска.
Далее в этой главе мы исслепуем сценарии, в которых квантовый алгоритм поиска является действенным инструментом для ускорения решения МР-полных задач. 6.1. Квантовый алгоритм поиска 315 Упражнение 6.1. Покажите, что унитарный оператор, соответствующий фа зовому сдвигу в итерации Гровера, имеет вид 2[0) (О[ — 1. Каждая операция в итерации Гровера может быть эффективно реализована на квантовом компьютере. Шаги 2 и 4 (преобразования Адамара) требуют по и = 1ок И операций кыкдый.
Шаг 3 (условный фазовый сдвиг) может быть реализован с использованием методов, описанных в равд. 4.3, для этого необходимо 0(п) элементов. Затраты на обращение к оракулу зависят от конкретного приложения, а пока просто заметим, что при итерации Гровера требуется лишь одно обращение к оракулу. Заметим, что объединение шагов 2, 3 и 4 записывается следующим образом: Нее(2[0) (0[ — 1) Нее = 2[ф) (ф[ — 1, (6.6) где [ф) — суперпозиция взятых с равными весами состояний (формула (6.4)). Таким образом, итерация Гровера сх может быть записана в виде П =(2Ю(Ф[-1)О. о к увитое Рабочее лростракстао оракула Рис.
6.2. Схема итерации Гравера тх. Упражненяе 6.2. Покажите, что применение операции (2[1й) (гр[ — 1) к состоЯнию 2,'ь аь[й) Дает РезУльтат [ — аа + 2(а)][к), (6.7) где (а) ы 2 ь ав/Ф вЂ” среднее значение а.поэтому операцию 2[ф)(ф[ — 1 иногда называют инверсией относитпсльно среднего.
6,1.3 Геометрическая интерпретация Что делает итерация Гровера? Выше было указано, что С = (2[ф)(ф[ — 1)О. Покажем, что итерацию Гровера можно рассматривать как поворош в двумерном пространстве, порождаемом начальным вектором [ф) и состоянием, являющимся суперпозицией решений задачи поиска с равными весами. Убедимся 316 Глава 6. Квантовые алгоритмы поиска в этом. Введем обозначения 2" ,для суммы по всем х, которые представляют а собой решения задачи поиска, и ~ для суммы по всем х, которые не являются решениями задачи поиска. Определим нормированные состояния следующим образом: (6.8) (6.9) Простые алгебраические вычисления показывают, что начальное состояние ф) можно переписать в виде (6.10) С)ф) = соз — (а) +зал — ф), 36 .
36 2 2 (6.11) так что угол поворота действительно равен 6. Ясно, что после Ь-кратного при- менения оператора С состояние ф) переходит в следующее: С"ф) =сов ~ — д) (а)+зш ~ 6) )р). /2Й+ 1 1 . /2Й+ 1 1 2 ) (6.12) Таким образом, можно сказать, что С представляет собой поворот на угол д в двумерном пространстве, натянутом на векторы ~а) и ~33). Повторное приме- нение итерации Гравера поворачивает вектор состояния еще ближе к векто- ру ф. Когда вектор С")Ф) будет достаточно близок к вектору Щ, измерение в вычислительном базисе даст с высокой вероятностью одно из слагаемых, об- разующих вектор ф), т. е.
решение задачи поиска! Пример, иллюстрирующий алгоритм поиска при М = 4, показан на вставке 6.1. сГпражнение 6.3. Покажите, что в базисе, состоящем из векторов ~а) и ф), итерацию Гравера можно записать следующим образом: ~соз д — в3п д~ '(вшд совд ) ' (6.13) т.
е. начальное состояние квантового компьютера лежит в пространстве, порожденном векторами ~а) и ф). Действие оператора С можно представить себе следующим образом. Оракул О производит отражение относительно вектора ~п) в плоскости, задаваемой векторами !а) и 03).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
