М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 83
Текст из файла (страница 83)
Простые базы данных (вспомните обсуждавшийся выше список цветов) могут быть упорядочены по алфавиту, так что можно использовать бинарный поиск, при котором зались будет найдена в базе, содержащей Ф записей, за время О(!оя И). Тем не менее в некоторых базах данных используется более сложная структура, и, хотя для оптимизации классического поиска применяются сложные методы, в случае, когда рассматриваются записи достаточно сложной и непредсказуемой природы, заранее организованная структура базы данных может оказаться бесполезной; в таком случае задачу следует рассматривать как поиск в фактически неструктурированной базе данных. Во-вторых, чтобы квантовый компьютер мог проводить поиск по классической базе данных, требуется квантовая схема адресации памяти.
Описанная выше схема требует 0(И!ояЖ) квантовых переключателей — т. е. примерно такой же объем (квантовой) памяти, какой требуется для хранения самой базы. Не исключено, что эти переключатели в какой-то момент станут столь же простыми и дешевыми, как и классическая память, однако пока этого не произойдет, построение квантового компьютера для выполнения квантового поиска не будет экономически выгодным по сравнению с классическими вычислительными устройствами.
Принимая во внимание приведенный выше анализ, мы можем заключить, что основным применением квантовых алгоритмов поиска вряд ли будет являться поиск в классических базах данных. Скорее, они будут использоваться в поиске решений сложных задач, таких, как задача о гамильтоновом цикле, задачи коммивояжера и выполнимости. 6.6 Оптимальность алгоритма поиска Мы показали, что с помощью квантового компьютера можно организовать поиск среди Ж записей с использованием только 0(ь~Ж) обращений к оракулу. Сейчас мы докажем, что никакой квантовый алгоритм не может решить эту задачу с менее чем Й(~/М) обращениями к оракулу, т. е.
что предложенный нами квантовый алгоритм является оптимальным. Предположим, что алгоритм начинается с состояния ф). Для простоты определим нижнюю оценку для случая, когда у задачи поиска имеется толь- 336 Глава 6. Квантовые алгоритмы поиска ко одно решение х. Чтобы найти последнее, нам разрешается обращаться к оракулу Оэ, который дает фазовый сдвиг на — 1 для решения |х) и оставляет все остальные состояния неизменными: О, = 1 — 2|х)(х|.
Пусть алгоритм начинается с состояния |ф), а оракул О вызывается ровно й раз; между обращениями к оракулу применяются унитарные преобразования Ум Уз,..., Уь Введем следующие определения: (6.38) (6.39) |ф„*) = и,о.и,,о.... П,О.|ф), |фь) ьз УьЬ/ь-ь ° Ыь!ф). Другими словами, |фь) — состояние, которое получается в результате последо- вательного применения операций Уы..., Уь без обращений к оракулу.
Пусть |фс) = |ф). Наша задача заключается в том, чтобы оценить величину Р = — ~ ,'Цфь — фьЦ', (6.40) Р„„=~ Цо.ф,*-ф,Ц' ЦО,(фь — ф ) + (О* — 1)фьЦ'. (6.41) (6.42) Принимая во внимание неравенство ЦЬ+ сЦз < ЦЬЦз + 2ЦЬЦЦсЦ + ЦсЦз при Ь га Оэ(фф — фь) и с = (Оэ — У)фь = — 2(х|фь|х) придем к неравенству Рьь~ < ~ (Цфь — фьЦ~+4Цфь — фьЦ|(х|фь)|+4|(фь!х)|з). (643) Применив неравенство Коши-Шварца ко второму члену в правой части и за- метив, что 2 ' |(х|фь)|з = 1, получим 1/э 1/з Ры.~ < Рь + 4 ~ Цфь — фьЦ~ ~~~ |(фь|х')|~ + 4 (6.44) < Рь + 4~ГРь + 4. (6.45) где использовано обозначение ф вместо |ф) для упрощения записи формул.
Интуитивно ясно, что Рь — мера вызванного оракулом отклоненил после Й шагов от эволюции, которая имела бы место без оракула. Если эта величина мала, то все состояния |фь) примерно одинаковы и значение х невозможно определить правильно с высокой вероятностью. Стратегия доказательства состоит: а) в оценке величины Рю которая показывает, что она не может расти быстрее, чем О(кз); б) в доказательстве того, что величина Рь должна иметь порядок й(Ь/), если можно различить Ф вариантов. Объединив эти два результата, получим требуемую нижнюю оценку. Вначале докажем по индукции, что Рь < 4кэ.
Для /с = 0 это утверждение очевидно (Так как Рс = О), Обратите внимание на тот факт, что 6.6. Оптимальность алгоритма поиска 337 С учетом предположения индукции (Юь < 4яз) получим Рк-~~ < 4йз+ 8й+4 = 4(й+ 1)~ (6.46) что завершает доказательство по индукции. Чтобы завершить доказательство, нужно показать, что вероятность успешного выполнения алгоритма может быть высокой только в том случае, когда Юь имеет порядок й(И). Предположим, что ~ (хрГь ) ~~ > 1/2 для всех х, т.
е. наблюдение дает решение задачи, поиска с вероятностью не менее 1/2. Замена ~х) на е'э~х) не изменяет вероятности успеха, поэтому без потери общности можно прсцположить, что (х)фь) = )(х(фь»)), следовательно, (фь — х9э = 2 — 2)(х)фь»)! < 2 — ~/2. (6.47) Введя определение Еь ш 2 (фь — х/!э, мы заметим, что Еь < (2 — ~/2)И. Теперь мы в состоянии доказать, что Рь имеет порядок й(Ж). Используя определение Рь ш ~ ()х — фД~, получим О ~~~(6,» )+( 6, )»2 > ~~~~$чД вЂ” х)( — 2 ~~ $ф~ь — х()()х — чфД+ ~ ~)(х — фь!) = Еь+ Рь — 2~~~ ЦР— х)(((х — фь)).
(6.48) (6.49) (6.50) Применив неравенство Коши-Шварца, придем к следующей формуле: ~$~4ь» — х)!)(х -чань~~ < /ЕьРы поэтому Пь > Еь + Рь — 2~/ЕьРь = (~/Рь — ъ/Еь) (6.51) В упражнении 6.15 вам предлагается показать, что Рь > 2И вЂ” 2с/Й. Этот факт совместно с неравенством Еь < (2 — ~/2) М дает неравенство Вь > сФ для достаточно больших 57, где с — произвольная константа, меньшая, чем (~/2— ~/2 — ~Г2)з ю 0,42. С учетом неравенства Пь < 4йз можно получить формулу й > ~/сЖ/4. (6.52) (6.53) упражнение 6.16.
Предположим, мы выдвигаем только требование, чтобы вероятность ошибки при усреднении по всем возможным значениям х (а не по 22 к» е в»»»» Таким образом, для получения вероятности успеха не ниже 1/2 в задаче поиска необходимо сделать Й(~/Ф) обращений к оракулу. 'Упражнение 6.15. Покажите (с использованием неравенства Коши-Шварца), что для любого нормированного вектора состояния ~ф) и базиса ~х) из 5/ орто- нормированных векторов выполняется неравенство 338 Глава 6.
Квантовые алгоритмы поиска всем значениям х) была менее 1/2. Покажите, что для решения такой задачи поиска по-прежнему необходимо 0(4Ж) обращений к оракулу. Приведенное выше утверждение о том, что квантовый алгоритм поиска по существу оптимален, является одновременно захватывающим и разочаровывающим. Захватывающим оно является постольку, поскольку оказывается, по крайней мере в данной задаче, что мы полностью проникли в глубины квантовой механики — дальнейшее улучшение невозможно. Разочаровывающим оно является потому, что можно было бы надеяться на существенно большее ускорение по сравнению со степенным, полученным в квантовом алгоритме поиска.
Можно помечтать о том, чтобы выполнять поиск в пространстве из И элементов, используя 0(1о8 Ж) обращений к оракулу. Если бы такой алгоритм существовал, он бы позволил эффективно решать ЫР-полные задачи на квантовом компьютере, поскольку с его помощью можно было бы перебирать 2 <"> возможных вариантов с использованием «с(п) обращений к оракулу, где много- член «э(п) представляет собой длину перебираемых объектов в битах.
К сожалению, такой алгоритм не существует. Это является полезной информацией для потенциальных создателей алгоритмов, так как из этого факта следует, что «наивный» алгоритм решения АР-полных задач с помощью поиска по базе данных заведомо не приведет к успеху. Осмеливаясь перейти в область догадок, отметим, что многие исследователи полагают, что основным источником сложности в решении ХР-полных задач является отсутствие какой бы то ни было структуры в пространстве поиска, а также что (с точностью до полиномиальных множителей) наилучший способ решения таких задач состоит в использовании метода перебора.
Если встать на эту точку зрения, то ситуация с квантовыми вычислениями не внушает оптимизма, поскольку тогда класс задач, эффективно решаемых с помощью квантового компьютера (ВЯР), не содержит ХР-полных задач. Конечно, это всего лишь точка зрения, и все-таки возможно, что ХР-полные задачи содержат некоторую неизвестную структуру, которая позволяет быстро решать их с помощью квантового компьютера (а возможно даже и с помощью классического).
Красивым примером, иллюстрирующим эту идею, является задача разложения на простые множители, которую принято считать относящейся к классу ХР1-задач (промежуточных по сложности между Р- и МР-полными задачами). Главной идеей для эффективного решения квантовомеханическими средствами задачи разложения на множители являлось использование «спрятанной» внутри задачи структуры †о была обнаружена при сведении этой задачи к нахождению порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
