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

Таким образом, перскрытие :ообого маркированногосостояния lw) с is) •·араптированно равно l(wls)l ~ 1/Vf\i. Следователь­но, если нам известно количество маркированных состояний, то мы можемопрел.елить, ско;IЬко потребуется итераций~ чтобы с высокой вероя"ТНОС1ЪЮотыскать одно из них-количество необходимых итераций не зависит оттшо, какое состояние маркировано.Но! конечно, мы мorJПI бы выбрать отражение относительно другойоси. F:сли мы може.!-1 построить унитарное преобр33011аниеU{с разумпой:1ффективностыо), тог;щ мы можем образояап.U(2IO) (OI - l)UI=2UIO)(OIUt - 1прсобразование, отражающее относительно оси(6.171)UIO).Пре;l,ПОЛОЖИМ, ЧТОlkiUIO)I= siпB,(6.172)где lш) - маркированное состояние. Тогда. если мы заменим в итерацииГровера U, на отражение (6.171), то одна итерапия будет выполнять по­ворот на угол28в Iшоскости, опредеШiемой векторамиlw)иUIO)(в со­ответствии с теми же аргументами, что мы использовали для П.).

Таким+образом, после Т итераций с (2Т l)B со "/2 измерение в вычислительномбазисе с высокой вероятностью найдет lw). Слецовательно, есsш мы ::щ­меним в квантовой схеме Гровера H(n) па U, мы по-прежнему сможемвыпоJшять поиск н базе данных до тех пор, покаU ]О)остается не ортого­нальным маркированному сОС1{)ЯНию 1 • Но если мы не И:\!:еем никакой апри­ориой информации о rом, какое состояние ~аркировано, то нСn) яв:~яетсянаилучшим выбором не то.Тhко потому, ч-mis)имеет известное перскрытие1L. К. Grover, Qшmtum Computers Сап Search Rapid/_"t: Ву Using Almost Any n·ansfiJrmation,Phys.

Rev. Lett., 80,4329-4332 (199R); quant-ph/9712011.ГЛАВА 6342с каждым маркированным состоянием, но также и потому, что оно имеетмаксимальное среднее перекрытие со всеми возможными маркированнымисостояниями.Но иногда, выполняя поиск в базе данных, мы им:еем некоторую ин­формацию о том куда следует заглянуrь, а в этом С.:I)'ЧЗС может оказатьсяполезной описанная выше стратегия обобщенного поиска 1 •В качестве nримера проблемы с пекоторой вспомогательной струК1у­рой предположим, чтоf(x,у)-фунЮIЯЯ с однобитоным значением, зави­сящая от двух п-битовых с·rрок х и у, и нам нужно найти единственноерешениеf( х, у)~1.С nомощью алгоритма Гровера мы можем искатьсреди N 2 возможных значений (N ~ 2n) пар (х, у) и с высокой вероятно­стью найти решение (х 0 , у0 ) носпе ~N итерапий, квадратичное ускорениеПО сравнеНИЮ С КJiаССИЧССКИМ ПОИСКОМ.Но предположим дапее, что g( х) - функпил только от х, и известно,при ровно М значениях х, где 1МN.

Более того,известно, что g(x 0 ) = 1. Следовательно, мы можем восполыоваться функ­цией g, чтобы помочь в поиске решения (х 0 , у 0 ).чшg(x) = 1ниеf(x,««Теперь для консупьтаций у нас есть два оракула, один выдает значе­у), а лру1uйзначениеg(x).Наша задача~найти (х 0 , у0 ), задавминимальное количество вопросов.С классической точки зрения нам необходимо околод;IЯroro,числяемg( х)нияу) ~f(x,N .'vfвопросовчтобы с разумной вероятностью найти решение.

Снача.1а мы вы­ддя каждого х; затем мы ограничиваем наш поиск реше­tшлько такими М значениями х, при которыхg(x)~1.Естественно поинтерссоваться, существует ли способ выполнить кванто­вый поиск за время порядка квадратного корня от классического времени.Исчерпывающий поиск, который обращается только квремени N»f -оракулу,требуетЖМ и, следовательно, не решает проблемы. Нам необхо­димо пересмотреть наш метод квантового поиска.

чrобы воспользоватьсяиреимуществом струюуры, иредоставляемой функинейЛучший методмерно за ~-g.сначана применять алгоритм rровера кg( х).При-/% итераций мы приготовим сосшяние, близкое к равно­взвешенной суперпозиции из М решенийg( х) ~ J. В частпости, состо­1яние lx 0) возникает с амплитудой - -. Затем мы применяем алгоритм.,;М1 Е.Farhi and S, Gutmann, Quantum~Me<chanical Square Root Speedup in а Structured SearchL.К.Grover, Quantum Search Оп Structured Prohlems, quant-ProЬlem, quant-pЬ/97ll035;pЬ/9802035.6.7.НЕКОТОРЫЕ ЗАДАЧИ НЕ ДОПУСКАЮТ УСКОРЕНИЯ343Гровера к f(x, у) при фиксированном х. Приблизительно после ~JNитераций состояниениюlx 0 )(s)эволюционирует достаточно близко к состоя­lx0 )(y 0 ).

Следовательно, lx 0 , у0 ) появляется с амrшИ'Iудой ~1 -....;мОбразованнос из ~ JN вопросов унитармое преобразование, котороемы до сих пор строили. может рассматриваться как преобразованиеU,определяющее обобщенный поиск. Более того, нам известно, что(6.173)Следовательно, если мы итсрируем обобщенный поиск примерно ~у'Х1раз, то приготовим состояние, достаточно близкое к (х 0 , у 0 ).

В совокупности примерно после(6.174)вонросов мы ~ожем с высокой вероятностью найти решение. Это действи­тс.:rыю квадратичное ускорение по сравнению с кдассическим поиском.6.7.Некоторые задачи ие допускают ускоренияПример структурированного квантового поиска шшюстрирует,квадратичные квантовые ускорения по сравнению с классическимичтоалго­ритмами могут быть достигнуты для различных проблем, а не только дляисчерпывающего поиска в неструктурированной бюе данных. Можно да­же надеяться. чrо квантовый параJШелк1м nозволяет существенно уско­рить любой классический алгоритм.

Сейчас эта надежда будет рюбнта-для многих задач квантовое ускорение невозможно.Продолжим рассматривать задачи с кванrовым черным ящиком, ора­кулом, который вычисляет функниюf,отображающуюnНо мы немного модифицируем наши обозначения. Функниипредставлена строкой изN=2nбитов в один.fможет бытьбитов:(6.175)где Х, обозначаетf( i). Наша задача - вычислить неко·rорую зависящуюот Х функцию с Однобитовым значением, то есть ответить на ДАЛIЕТ-воп­рос о свойствах оракула.

То, что сейчас будет показано, означает, что неко­торые функции от Х не могут быть ВЪIЧислены с низкой вероятностью3446]'ЛАВАошибки, используя квантовый а;норитм, за иск.;почением а.1rоритма, об­ращающеrося к оракулу столько раз (или почти столько же раз), сколькотребуется классическому алгоритму 1 .Главная идея состоит в том, что булева фунщия от персменныхможет быть представлена полипомом отXixi. Более TOI'O, раснредсление ве­роятностей д.i1Я кванwвоrо измерения может быть выражено через полиномотXi,tде степень полипома равна 2Т, есJШ измерение слса:ует нослеТ во­нросов оракулу. Проблема в том, может ли нодином степени21' обеспечитьразумную аппроксимацию интересующей пас бупсвой функции.Действие оракула может быть прслставлено какUo: li,y;z) ___, li,yФXi;z),гдеiнринимаст значения из{0, 1, ...

, N -1}, уЕ(6.176){0, 1}, а zобозначает со­с юяние вспомогательного кубита, не изменяемого оракулом. Следоватеш,­но, в каждомсобой2х2х2-бдоке, натянутом на/i,O; z)и2-матрицу(1-XixiХ;1-xi/i, l;z), U 0) .представляет(6.177)Квантовые вентили, в отличие от вонросов к ораку~rу, не зависят от Х.СJ1словате.1ьно, после того как схема из Т нопросов подействует на любоенача.1ьное состояние, резулылрующес состояние IФ) бупет иметь амnлиту­цы, которые (по крайней мере) юшяются поJIИномами степени Т от Х. Rслимы выпоmшм ПОЗМ па IV,), то связанная с положительным оператором Fвероятность резупьтата (ФIFIФ) может быть выражена через поJIИном от Хстепени, не меньшей чем 2Т.Любая булева функция отXiможет быть выражена (единственнымобразом) через нолином степени~ Л' поцию OR от N персменных Xi; этоOR(X) = 1- (1поmшом степениXz.Например, рассмотрим функ­Х 0 )(1- Х 1 ) · · ·(!-Хн_ 1 ),(6.178)N.Допустим, мы хотим применить нашу квантовую схему для тоm, что­бы с полной определенностью вычислить функциюOR.Тогда мы должныН.

~'arbl, et al, А l.imit оп fhe Speed of Quantum Computation in Determining Parity, Phys.RcY. Lett, 81, 5442-5444 (1998); quant.-ph/9802045; R. Beals, et al, Quantum Lower Bmmds ЬуPolynomia/::.·. In Pmceeding~· ofthe 39th Annual Symposium оп Fvundamenials o[Computer Science(FOCS'98), 352· 361, IEEE, Lo-" Alamos, California, NovemЬer, 199В; quant-ph/9802049.16.7.

IIFKOTOPЫE ЗАДАЧИ НЕ Jl()ПYCKAIOT УСКОРЕНИЯ345бы1ъ в состоянии выполнить измерение с двумя результатами О и1де1,Prob(O) = 1 - OR(X),Prob(l) = OR(X).(6.179)Но эти выражения являются полиномами стене ни.._"v',которые могут бытьвычислены только nосле как минимум Т ~краТiюго обращения схемы кора­кулу, где(6.180)Мы прихоJщм к выводу, ч10 не существует юшнтовой схемы, которая менеечем за 1\1/2 обращений к оракулу может rочно вычислитьOR. Фактически!UIЯ тrой функции (или любой функции, принимающей значение О тош,­ко для от~;ноrо изNее возможных ар~ентов) существует более сильноезаключение (см.

упражнение): требуется Т;? ~V', чтобы с tютюй определен~ностью вычис.1итьOR.С другой стороны, вычисJIЯЯ функциюOR(отпсчая на ДА/НЕТ-вопрос«Имеется ШI маркированнос состояние?»), именно алгоритм Гровера можетлостичь количества вопросов порядкаvfN.чw для детермииированного вычисленияТаким образом, вывод о том,OR необхо;щмо 1\1 вопросов, хо­тя и корректен, но несколько обманчив. Мы можем вычисJштьORверо­ятиостным образо.н с Iюмощью гораздо меш.шсm КОJшчестRа вопросов.По-видимому, алгоритм l"ровера может Iюстрои1ъ полином от Х, который,имея степею~ то~IЬКО О( V}V), тем не менее обеспечивает весьма адекватнуюаппроксимацию полинома N-ой степениOR(X).OR, принимающая значение 1 для каждого значения Х, кро­ме Х = CJ, яв.тястся очень простой булевой функцией. Нам следует рассмот­Однакореть друтие функции, которые мо1ут предложить квантовому КО"~<пьютеруболее серьезные проблемы.Первое, •по приходит в голову- зrо функцияPARITY(X),принима­ющая значение О, если строка Х содержит четнос котrчество единиц, изначение1,-ес.тш строка Х сапержит нечетнос количество единиц.

Очевид­но, чтобы определить четность, классичес:кий а.'IГОритм должен обратитьсяк оракулуNраз. Насколько Jlучше тю можно сделать, предлагая кваюовыевопросы? Фактически мы вообще не можем цобИ1ъся лучшего рсзу;Iыата--необходимо по крайней мере лт;2 кванmвых вопросон, чтобы с вероятно-стью уснеха, бош,шей! +д, найти правильнос значение PAR1TY(X).При обсужденииPARI'I'Yудобно использовать новые неремснныеХ, = 1- 2Х,,(6_181)ГЛАВА 6346принимающис значения±1, так чтоN--lPARITY(X) ~ П Х,(6.182)i=Dтакже принимает значения± J.Теперь, после ТОJ'О как выполнена кванто­вая схема со всеми Т вонросами ораку,-уу, мы должны выполнить ПОЗМс двумя возможными исходамliF cvenи Fodd; результаrом будет наша опен­ка PARITY(X). Как мы уже отмечали, вероятность получения резуJП,­тата (к примеру)(2Т)-номPeven«everl)) («четный») может быть выражена через поли(Х) степени (самое большее) 2Т по Х,:(Fcven) = Р,~:;;}(Х).(6.183)Как часто nаша догадка будет верна? Рассмотрим суммуN-l"(2Т)L..' Peven-- · I'ARITY(X)- _ "(2Т) (Х)п Х,(Х)L..' Pe~n{Х){Х)Поскольку каждое слагаемое nолиномашее 2'Г из персменных(6.\84);~о(2Т)Peven-(Х) содержит самое боль-Xi, то можно воспользоваться тождеством(6.1 Х5)Х~ Е{О, 1}чтобы понять, что сумма в(6.184)должна обращаться в нуль nриN >2Т.Таким образом,р(2т)(Х) =р('т)(Х).eveneven;(6.186)par(.X)-....o-1то есть при Т < N/2 мы с одиirаковой вероятностью можем угадюъ«evem>, как в случае, ко1да на самом деле PARITY(X) является нечет­ной, так и в том случае, когда она действитеJП>но четная (в среднем).Hamквантовый алгоритм ничего не может сообщить о значении PARITY(X);то сеть в среднем по возможным (аprioriравновероятным) значениям Х,мы с равной вероятностью будем как правы.