Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 64

Каждая итерация Гровера по­ворачивает квантовое состояние в плоскости, определяемой векторамиs)1и lw); после Т итераций состояние оказыnается наклоненным к оси 1"'~)подуголом е+ 2Те. Чrобы оптимизировать вероятность обнаружения мар­кированного состояния при выполнении закmочител.ьного измерения, ите­рироватъ следует до угла, бпизкого к90°,или(2Т + l)e с:е 2':' =;- 2Т -1 1 с:е _zr:_;22е(6.148)вспомним, что sin е ~ Jи· или, при больших N.е"' -~-.vN(6.149)6.4. КВАНТОВЫЙ ПОИСК R БАЗЕ ДАННЫХECJrn335выбратьт= ~vN[1 + o(lv-' 1')],то вероятность получения/w)(6.150)в качестве результата измерения будет равнаProb(w) = sin2((2Т + 1)0) =1-О(~).(6.151)Таким образом, необходимо лишь око~•о ~ vN вопросов, чтобы с высокойвероятностью определитьw,квадратичное усКDрение по сравнению с Юiас­сическим результатом.6.4.5.МножестВQ решенийЕсли существует>rlмаркированных состояний иrизвесnю,·roколичество итераций можно модифицировать так, чrобы вероятность отыс­кания одного из них оставалась очень близкой к единице.

Анализ такой же,как и выше, за искточением rого, что теперь оракул индупирует отражениев rиперплоскостн, ортогональной вектору,.lw)=~L /w,)(6.152)yr i'--1-равновзвешенной суперпозиции маркированных состояний вычислитель­ного базиса/w,).Теперь(s/w)={j;""sin 8,(6.153)а итерация Гровера поворачивает вектор на угол 20 в плоскости, натянутойна векторы /s) имы снова приходим к выводу, что после количества/w);итераций(6.154)состояние fuшзко к/w).Тогда если мы выполним измерение, нроецируя нас верояnюстью, близкой к единице, найдем одноиз маркпрованных (равновероятных) состояний.

(С ростом количества ре­вычис.rmтельный базис,wшений время, необходи~ое для отыскания одного из них, падает как r-· 1/ 2•в противоположность к.,.- 1в классическом случае.)336Гллвл6Обратим внимание на то, чтu ес;ш продо~Jжить ныпо.'1нение итерацийГравера, то вектор продолжит поворачиваться, и, таiШм образом, вероят­ность отыскания маркированного состояния (в результате зак..110чительногоизмерееия) начнет падать. Алоритм Гровера подобен выпечке суфле-СIО­ит персдержать его н духовке, как оно начлет опадать.

Следовательно. еслинам ничего неизвестно о количестве маркированных состояний, то поискfодно10 из них может оказаться безуспешным. Например, Т ~ VN ите­раций оптимально при r = 1. но при r --=- 1 вероятность отыскания мар­кированного состояния посде :этого количества итераций довольно б.аизкак нулю.Но ,цаже еслиrаprioriнеизвестно, мы вес же можем найrn решениес квадратичным, по сравнению с к.1ассическими ашоритмами (при r<< 1'n.ускорением.

Наnример, мы можем выбрать количество итераций С.JУЧай­ным в интервале от нуля до ~JN. Тогда ).J,Jiя каждого r, ожидаемая веро-ятность отыскания маркирuванноrо сосmяния близка к ~- О1едоватеJ1ьно,маловероятно, что нам не ул;астся найти маркированное состояние посленескольких по~rrорсний. А nри каждом измерении мы можем предлагатьоракулу найденное нами состояние в качестве классического вопроса, чrо­бы получить подтверждение того, яnляется ли оно действительно маркиро­ванным.В частности, если решение не бы.ю най.п;сно после неско.-;-Jьких попы­ток, то вполне возможно, что оно не существует.

Таким образом, с высокойвероятностыо можно даn~ корректный ответ ~Л!НRТ на вопрос ((Есть Шfздесь маркированные состояния?». С.Jiедовательно, мы можем нриняп~ ал­горитм Гровера, в коrором оракул проверяет пред,1оженное решение, чrобырешить любуюN Р-пробпемус-ква~ратичным ускорением по сравнениюс классическим MCТOil,OM исчерпывающего поиска.6.4.6.Оеуществле11ие отраженияЧтобы вылолить итерацию Гровера, нсобхо;щмо (кроме вопроса ора­куну) унитарное иреобразованисU,=2ls)(sl-1,(6.155)коrорое отражает векrор относительно оси, опреде;ыемой векrором is).113 квантовых вентилей? Таккак is) = H(n)IO), ще H(n) -побитовое иреобразование Адамара, то можноКак эффективно построить это нреобразованиезаnисап.(6.156)6.5.

ОПТИМА:IЬНОСТh А.JГОРИТМ:А ГРОВЕРА337то есть для зrого достаточно построить отражение относительно оси[0) ..Мы легко можем построить это отражение из п-битового вентиля Тоффо­лиеСпJ.Вспомним, чтоН<ТхН = lТz;(6.!57)инвертирование бита с а,тщмаровским поворотом базиса эквиnалент:но об­ращению относительной фа:ш векторов--+IO)и11)..СJСI\ОВа:rелъно:----=-1~~-=i--{ п]---1 -[НI--!-@-ПОС.'IС СОПряжения ПOC::ICJ{НCJ·o бита ареобразованием Н веНТИ.:JЬB(n)СТа­НОВИТСЯ(n- 1)-кратно контро.1нруемым <Т z• который обращает фазу векто­ра 111 ... ) ll) и действуст тривиально на вес другие состояния вычислитель­ного базиса. Сопрягая с помощью NОТ(н), мы получаем U 5 с точностью1{0 несущсственноi"О общего знака минус.В упражнении вы покажете, что п-битовьrй вентиль ТоффоiШ (J(n) мож­но построить из (2п- 5)-ти трехбитоных вептн~•ей Тоффоли о(З) (еслидос·tуппо достаточное вспомогательное пространство). Следовательно, об­разующаяUsсхема имеет лииейн.ый по n =log Nразмер.

Гроверовскийпоиск в бюе данных (при условии, чrо оракул мr,повснно отнечает на во­прос) требует времени порядкаJN log N.Если мы рассмюриваем оракулкак подпрограмму, которая вычисляет функцию за полилогарифмическоевремя, тогда поиск требует времени порядка VNpoly(JogN).6.5.Оптимальность алгоритма ГровераГроверовское квадратичное квантовое ускорение поиска н базе данныхуже интересно н потенциально важно, но конечно же, дейс rвуя более ис­кусно, мы можем добиться лучшего резуш.тата, не так JШ? Нет, оказываетсяне можем. Алгоритм Гровера обеспечивает максиманьно быстрый кванто~ный поиск в неструюурированной базе данных, если <{время» измеряетсяв соответствии с ко;шчеством задаваемых оракулу вопросов.ГЛАВА б338Рассмо1рим случай одного маркированного сосmянияlш), пустьU(w, Т) обозначает квантовую схему, Т раз обращающуюся к оракулу.Мы не наюшдьmаем на эту схему никаких ограничений, за исключениемколичества задаваемых ей вопросов; в частности, мы не ограничиваем ко­личество кпантовых вентиJIСй.

Эта схема применяется к начальному состо­янию IФ(О)), производя конечное состояниеIФw(T)) = U(w, Т)IФ(О)).(6.158)Теперь мы должны выполнить измерение, предназначенное выделитьсредиNlw)его возможных значений . .Цля того чтобы мы бьши в состоянииидеапьно различать возможные состояния IФ'"(t)), они до,lжны быть взаим­но орrогональными, а чтобы их можно бы."'IО корректно различать с высокойвероятностью, они должны быть почти ортогональны.Если сосmяния {!Фw)} образуют ортанормированный базис, то длялюбого фиксированного нормированного вектора !'Р)N-1I; IIIФ"') -11")11 2 )2N- 2ГN.(6.159)w=O(Сумма минимнзнрустся, если !'Р) является равновзвещенной суперпозици­ей всех злементов базиса !'Р) = }н~ IФw), как вы можете показ:rrь, nри­мекая метод неопределенных множителей ЛаfJ)анжа нахождения условныхэкстремумоп.] Наша с1ратеrия состоит в подходящем выборе состоянияпозволяющем с помощьюнеравенства(6.159)!'f'),что-пибу;\ь узнать о количе­стве обращений к оракулу Т.Наща схема с Т вопросами образует унитарное преобраеование(6.160)гдеUw-nреобраювание оракула, аНС"Оракуnа.

Выберем в качествеU, - nроизвольные иреобразования11"(1')) результат применения к состояниюIФ(О)) иреобразования U(ш, Т), в котором каждоеU"' заменено на 1; тосеть результат при:менения той же схемы, но со всеми вопросами, задавае­мыми «пустому оракулу>>. Следовательно,(6.161)в то время как(6.162)6.5. 011ТИМАЛЬНОСТЬ АЛГОРИТМА ГРОВЕРАЧтобы сравнитьI'P(T)}339с I,P~(T)}, воспользуемся нашим предыдущим ана­лизом влияния ошибок на точность схемы1 рассматривая r.v-оракул как оши­бочное применсние пустого оракула. Норма вектора ошибки после t-го ша­га [ер. уравнение(6.63)]равнаIIIE("',t)JIIпосколькуниеUw= 1-= II(U~-l)I'P(t)}ll=2111"-'I'P(tJ}II,(6.163)Посде Т вопросов мы имеем [ер. уравне­21"'}\wl.(6.66)]тlll1'w(T)} -l:p(T)}II (: 2L l(wl<p(t))l.(6.164)t=1Из тождества(6.165)следует нсравснство(6.166)применение которого к(6.164)дает(6.167)Суммируя поw,мы находимL 111·</Jw(T)) -l<p(T)}IIт2(:4Tl:(<p(t)l:p(t)) = 4Т 2(6.168)t= 1Привпекая неравенс·mо(6.159),мы приходим к выводу, чrо4Т~ ~ 2N- 2VN,(6,169)340]'clARA 6если состояния IФw(T)) взаимно ортоншальны.

С1словательно, мы ноказа­ни, что любой квантоный а..-rтгоритм, способный разШIЧ:ить нее возможныезначения маркиронашю1u состояния, до.;пкен обратиться к оракулу Т рю,rJ:e1'?fl(6.170)(без учета малых приN ---> оо поправок). Ат-оритм Гровера находит "-'с помощью ~ ,fN вопросов, что нрсвышает эту гранит()' всего пример­но на 11%. В действите~ъности можно усовершенствовать дока:зательство,чтобы улучшить границу до ~VN(l- с), что асимптотически насыщаетсяалгоритмом Гровера 1 . Более того, можно показать, что схема Гровера до­стигает оптимальной вероятности успеха с помощью Т ~ ~ yfN вонросоn.Испытываешь прис·1ун разочарования (и одновременно волну восхи­щения перед Гравером) от осознания того, что аJirоритм поиска в ба_1еданных не ~южет быть улучшен.

Какое отношение это имеет к квантовойсложности?Ддя многих пробле" оптимизации вN ?-классене и.звестно дучшегометода, чем исчерпывающий поиск всех возможных решений. Ис1 юлъ:зуя~mаптовый нapa.r1JICJШЗM, можно достичь квадратичного ускорения исчер­пьшающего поиска. Теперь мы :шаем, чrо квадратичное ускорение яв.:lЯетсянаилучшим, ссJш мы полагасмея на силу явного кванrооового пара.·пеШIЗ­·м:а и не разрабатываем наш квантовый а."IJ'Оритм, исподьзуя специфическуюструктуру решаемой задачи.

Тем не менее nри достаmчной изобретатель­ности можно добиться и лучшеп) резу.ш.тата.Онтималыюсть а.-вuритма Гровера может быть исто.-жована как сви­детельство того, чточто N Р ~ BQP, а Рглубокая внутренняяBQP ":f_ N Р. По крайпей мере, если окажется,i N Р, то тогда N ?-проблемы должна обьединятьструктура (свидетсJiьств которой в настоящее времянет), хорошо подходящая к возможностям квантрвых схем.Даже квадратичное ускорение может оказаться полезным д.,"IЯ различ­ныхN Р-IЮшtыхпроблем оптимизации. Однако квадратичное ускорение,в отличие от экспоненциальноm, реально не перемещает гранипу междуразрешимостью и сложностью. В один прекрасный день кван1uиыс ком­ш.ютеры смогут превзойти к:1ассические компьютеры в выполнении исчер1С.

Zalka, Grover's Quantum Searching Algorithm is Optinш/, Phys. Rev., А60, 2746--2751( 1999); quant-ph/9711 070. [Впервые оптимальность алгоритма Гровера была доказана в рабо­те: С. Н. Вennet, Е. Bemstein, G. Brassard, U. Vazirani, Strengths and ~Veaknesses of QuantumComputing, SlЛМ J. CompuL, 26(5), 1510-1523 (1997); quant-phys/9701 001 - Прим. рео.6.6. ОБОБЩЕННЫЙ ПОИСК И СТРУКТУРИРОRЛННЫЙ НОИСКпывающен) поиска, но то:Iько в том сдучае,ecJm341часы кванrовых приборовне будут слишком сильно отставатт~ от их к..1ассических прототипов.6.6.Обобщенный поиск н структурированный поискВ итерации Гровера мы выполняем преобразованиеотражение относитеJJЬНО оси, определяемой векторомU,is)2ls) (sl- 1,=l/'iCivN=Почему именно относительно нее? Преимущества состояния]s)N-1Llx).:J;=Oсостоитв том, чrо оно имеет одинаковые перскрытия с каждым состоянием вы­числительного базиса.