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

Таким образом, рассеяв только один фотон, мыуже приобретаем некоторую полезную информапию о периоде. При по­строении эффективных квантовых алгоритмов следует и дальше пою.:зо­ваться смыс.1овым подтекстом зтой метафоры.Итак, представим квантовый оракуп, вычисляющий функциюJ:{0, J}"~{0, l}m,которая имеет неизвестный период т, гдеудометворяющее1« r«То естьf(x) = f(xгдетп--произвольносJ\елоечислоr --(6 192)ноложите.'IЬнос целое число,(6.193)2".+ rnr),такое)(6. 194)чтохих+mrлежатв {0, 1, 2, ..

, 2"- 1}. Мы должны найти период r. Рассматриваемая клас­сически, эта проблема труд,тя. Если r, скажем, норядка 2n/'2, нам необ­ходимо обратиться к оракулу порядка 2n!'J раз, прежде чем мы, возможно,найдем дна значения х, оrображаемых на одно и то же значение J(х ). и,с.1едовательно, что-нибудь узнаем о периоде r. Но, как мы уиидим, суще­ствует квашовый алгорИ'Iм, определяющийrза время ро!у(н).Даже если нам известно, как зффективiЮ вычислять функциюf(x ),О1_rрсде.:гiение ее периода может оказаться трудной задачей. Наш квантовыйалгоритм может быть применен для отыскания за роlу(п) время периодалюбой функции, которую мы умеем вычислять заpoly( n)время.

Эффектив­ное отьtскание периода позводяет эффективно решюъ множество (по-види­мому) трудных задач, таких как фаiСТоризация целого числа или вычислениедискретного логарифма'.1Дискретный ."'оr-арифм. оnределяется как минимальный пшюж:иrе.'Тhl-fЫЙ корень х уразне-352ГЛАВА 6Кшочевая И/J;СЯ, п:ежащая в основе квантового поиска периода, заклю­чается в том, что иреобразование Фурье может бытъ. вычис;тено с помощьюэффективной квантовой схемы (что было обнаружено Питером Шаром).Квантовое преобра.зование Фурье(QFT)использует мощь квантового па­раллелизма, чтобы ТJ;Остичь экспоненпиа.ньноrо ускорения хорошо извест­ного (к.тассическоrо) быстрого иреобразования ФурьеFFT имеет такое широкое поле применений,(FF'T).Посколькуто, возможно, однажды иQt"Tстанет столь же широко распространенным.6.9.1.Отыскание перводаQFTявляется унитарным нреобразованием, действующим в вычисли­тельном базисе согласноQf'T :гдеN ___:_ 2n./х)(6.195)Будем но ка предполагюъ, чго мы эффективно выполняеми посмо1рим, как это позволяет извлекать период функцииЭмунируяашоритмСаймона,мысначалаобратимсяс }и~ !х) (:югю.> приготавливаемым применениемH(n)QF'T,f(x).коракулук /0)) и, такимобразом, приrотовим состояние.'V-1Jл ~ lx)/f(г)).Затем и.змерим выходной регистр, получая результатром О(х0< r.(6.196)IJ(x0 ))при иското­Это измерение готовит во входном регистре когерентнуюсут1ерпозицию А значений х, которые отображаются наf(x 0 ):А-!)л~ lxa + jr),(6 197)цеN- r ( х 0+ (А -1)r < N(6.198)ния ах= Ь(modp), где все переменвые нвШIЮТСЯ: це.'Iыми ЧНСJ~ами.

Пычисление дискр~ногологарифма янпяется с:южной вы<rnслитtшьной проб.;Jемой, что находит применсине н крипто­графии. Кнантовый а.-тrоритм решения зтой :щцачи см. в юшrе М. Нильсен, И. Чаш; Кватпо­вые вычш:.ленuн и кеантовал информация, М., \-fир(2006).- Прим. ред.6.9. l!ЕРИОДИЧНОСТh353NA-I<y<A+J.(6.199)илиНа самом деле и3~ерение выходного регистра не обязателыю. Если его про­пустить, те состоянием вхолноrо регистра будет некогерентная суперпози­ция (nrосуммированная по х 0 Е{0, l, 2, ...

, r-1}) состсяний вида (6.197).Оста.-r1ыrая часть алгоритма также хороню работает, действуя на зто началь­ное состояние.Теперь наша задача СОL'ТОИТ в том, чтобы извлечь значение r из состо­яiшя(6.197).Если бы мы па этом этапе измерили входной регистр, проеци­руя его на вычислительный базис, то мы бы ничсп) не узнали относитеJIЬ­но г. Вместо этого (ер. с адгuритмом Саймона) следует сначала выпо.1литьареобразование Фурье, а уже затем проводить измерение.ПрименяяQFTк состоянию(6.197),получим(6.200)l'.сли мы теnерь выпо~шим измерение в вычисшпельном базисе, то верою·­ность получения результата у будет равна2Prob(y) =-~(6.201)Этс распределение резко выделяет такие значения у, при коюрых ут / Nблизко к целому чис;rу: Ilanpимep, еслиN/rоказывается целым (и, следо­вательно, равным А), тоРrоЬ(:ч) ~ ~1L e2~iJY!АА1j=ODу= А· (це.1ое),(6.202)в праrивном с:1учае.более общем случае мы можем просуммировать геометрическуюrrrогрессию(6.203)ГЛАВА 6354гдее~Существует точноr2nyr(mod N)N.значений у Е {О,(6.204)l, 2, ...

, N- 1}, удовлетворяющих-~ ";; yr(modN) ";; ~-(6.205)(Чтобы убедиться в этом, представим про"аркированные ~<ратные r и Nв ряду чисел, простирающемся от О до r N - 1. Для каждого кратного Nсуществует кратное r, удаленное от него не более чем на расстояние r/2)Для каждого из зmх значений соответствующее О удов..-·Iетворяет(6.206)Теперь, поскоJJьку А. -1 <ме поjв уравненииlj, то при этпх значениях 8 все слагаемые н сум­(6.203)лежат в одной полуллоскостн. следовательно,они интерферируют конструктивно и сумма становится зна[_штельной.Мы э.наем, что(6.207)поскольку расстояние по прямой от начала координат меньше, чем длинадуги вдоль окружности, а приAIBI ";; n(6.208)так как мы можем увидеть (графически или вычисmrв е10 произво!{­ную), что эrо расстояние является выпуклой функцией. На самом делеА < lj + J и, следовательно, АО < т.

( 1 + ;:, ) , но, приме!U!Я вышеуказан­ную границу кei(A -1)0 - 1--с;,---- +<i(A-1)0eifi - 11ei(A--1)0-1;? --.с;---[-1,е~е - 1(6.209)мы тем не менее можем прийти к зыводу, чтоlе•м-11ве"- 1;:,z(A-1JIBI_7r11е1=~л-(~)1 ~1f'1f(6.210)6.9. llЕРИОДИЧНОСТЬПренебрегая возможной поправкой порядка3552/А,мы находимProb(y)? (;,)}!1J1Я каждою изr(6.211)значений у, удовдетворяющих нсравенству(6.205).Следо­вате:rьно, с вероятностью, не ниже чем 4/к 2 измеренное значение у будетудовлетворять(6.212)или"- - _1_ ,-: }!_ ,-: "r 2:.\f -. . : :. IV -.

. : :. r+ _1_(6.213)2N'где k- целое число, выбранное из {0, 1, 2, ... , r-1 }. Резуш.тат вычисленияс разумной вероятностью находится не дальше чем на расстоянии 1/2 отцелого кратною числа N r.1Пусть нам известно, чтоr<«Мнальное число со зна.\1енателем, меньшеN. Таким образом, N lr- рацио­rn.Два различных рациональныхчис .1а, знамепатеJiь каждого из которых меньшедруг к другу чем на211М ,атак как Ьмерения у удовлетворяет перавеяствус- d1Vl,не могут бы1Ъ ближеad-bc~ -,;;г-. Если результат из-(6.212), тосуществует единственноезначение k/т (при r <М), определяемое yiN, при условии, что N? М 2Это значениеkjr можетбытьуспешно изв.чечено из измеренногоyjN спо­мощью метода цепных дробей.С вероятностью, превышающей 1/1Г 2 , мы нашли значениевыбирается (примерно равновероятно) измой вероятностьюkиr{0, 1, 2, ... ,r -1}.ЯВJJяются взаимно простыми (не имеющими обще­го множите~"IЯ), так что мы добились успеха в отысканииr.к оракупу, мы можем проверить, действительно лиf(xлиGCD(k, r) f 1,1 тоkfr, где kС приемле­f(x)=Обратившись+ r).

Но ес­мы наПDШ всеm лишь r 1 , множитель r.Если мы не досrnrли успеха,roмы могли бы проверить некоторыеблизкие значения у [измеренное значение моrло оказаться вбтtзи интер­вала -r /2 :( yr(modN) ( r /2, в действительности не находясь внутриem] ктн проверить несколько множитслей r [значение GCD(k, r), если ононе равно единице, по-вид11:мому, невелнко]. Если не удается и это, то мыприбегнем к повторению квантовой схемы, получая (с вероятностью не ни1GСD (Gr.•co•~CommoQ Diviaor)- каи&т.шай общий детrrелъ-~ Ilpuм. пере..356ГЛАВА 6же 4/7Т 2 ) на этот раз значение k'fr.Теперь k' также может иметr, общиймножитель с г, в таком случае наша процедура внОiи~ онрс;~:сляетr2,мно­житель r.

Но с достаточно высокой вероятносп.ю GCD(k, k') = 1, в такомслучае т :-:- I-'СМ(т 1 , r 2 ). 1 Действительно, мы можем вычисsmть вероят­t-IОсть того, чrо случайно выбранные k и k' являются взаимно простыми,сле)~ующим: образом. Так как вероятность того, 1:по простое число р делитс:Iучайно выбранное число, равна1/р,то вероятность того, что р делит безостатка оба k и k', равна 1/р 2 А k и k' являются взаимно нростыми тогдаи только тогда, когда не существует простого числа р, делящего их обоихбез остатка.

С."Jедовательно,Prob(k, k'взаимно простые)~п (1- _L) ~ -" 1Ор·проеше р[где((z)Г(2)~ jJ_' "'о '607(6.214)7rобозначает дзета-функцию Римана]. Таким образом, носле векото­рого постоянного (не зависящеJU отN)количества повторений алгоритмамы наверняка Jtобьсмся успеха в поиске периода т.6.9.2.От FFТ кQFTРассмотрим теперь реализацию квантового иреобразования Фурье.Преобразованис Фурье~ J(x)Jx) ~ ~ (~ ~ e2пi,yfN J(x))хуvfЛ7 хJy)(6.215)представляет собой перемножспие ~итарных !v~ х 1\Г -матриц, где матрич­ный (х, у )-элемент равен (e 27ri/N) У. С наинной точки зрения это 1Iреоб­разование требует О( N 2 ) э.тементарных онерщий. Существуе'l; Оitнако, хо­рошо известная и очень полезная (классическая) процедура, сокращающаякошrчество операций до О( Nlog N).llредполатая, чтоN~2",нрсдста­вим х и у в виде двоичных разложений2n-1+. 2n-lX=Xn-1'_У-Уп-1Xn-2+Уп-2·.2"-2+2л-2...

-j -х1·+ ...2+Хо 1+у1·2+Уо·1f.CM (l..cщ.t Common Multiple)- наименьmее общее краmое.Прим. переб.(6.216)6.9. ПЕРИОДИЧНОСТЬ357В нроизвс;{ении х и у можно отбросить дюбые слагаемые, содержащие n-юи более высокие степени двух, поско.;rьку они не н носят вклада в e21rixy/ 2"'.Следова1-ст.но,~~= Yn-l(.xo) +y"_,(.xlxo) +Yn-з(.x,xlxo) + ... +t Уi(.х"_,хп з ··.ха)+ Уо(.хп-lхп-2 · · · хо).(6.217)где множители в круглых скобках представляют собой значения соответ­ствующих двоичных разрядов, например:(6.218)Теперь мы можем вьrчислитьf(x)для каждого изпо yk~ О,порядка1,N1= - -I>'"JNY1 1"" N(6.219)f(y)значений х.

Но сумма по у факrоризуется наnсуммкоторые могут быть последонателыю выч:ис.Iены за времяn.С помощью квантово10 параллелизма можно ;щби1ъся горюдо ~rучmе­го результата. Из(6.217)QFT: lx)--+мы пшучим_!~L e'•ixyfNIY)v'NyJin(IO) + e2ni(x )ll))(IO)0j e2ni(x,x 0)11J)... (IO) + е'•'(.х"_,х,_, ... х,\11)).(6.220)преобразует каждое состояние вычис~1Jtте."IЬноrо бюиса в иезапутан.~ное сосrояние n кубитов; таким образом, мы ожидаем, что оно можетQfTбыть эффективно реализовано. Действительно, рассмотрим случайn~Нетрудно понять, что э1у рабо1)' выполняет схемаlx2)-Гн!-----{RJ-lx,)R,j ___ _lvo)3.ГЛАВА 6358(но обратим внимание на то. что пО[)Я;J.:ОК слеiЩRания би:тов на выходе ин­вертировался) Каждый вентиль Адамара действует какДругие вкла,1ы в относительную фазу векторов IO) и 11) в k-ом кубнтсобеспечиваются двухкубитовыми условными поворотами.

Г;::tеR" = (аd~(k- j)~ е''~'"),(6222)-«расстояние" >~ежду кубитами.В случаеn = :3 Qi'Tлей контро.шруемоеR.строится из трех вентилей Н и трех венти­В общемc..ciJЧacочевишюе обобщение этой схе-мы требует n вентилей Н и ( ~) ~ iп(n- 1) контрошtрусмых R. Вновr.двухкубитовый вентиль применяется к каждой паре кубнюn с контролиру­емой относительной фа~ой пj2d, Г/tС d - «расеmяние» '-'1еж,;~у rубитами.Таким образом, ce1teЙCTIIO схем, осуществляющееQPT,имеет размер но­рядка (Jog N) 2Мы можем сократип. сложность схемы до линейной поlog 1\1,если 1·0-товы ограничиться реа.1и3ацией фиксированной точности, поскош~ку двух­кубитовые вентюпт.

действуя на значительно раЗ,1С.lевные кубиты, вносятлишь экспоненциально малые фазы. Если ~fЫ опусти'-1: венти.1н, действую­щие на пары, разделенные более чем на тп, тогда каждое c;Jar-aeмoc в(6.217)заменяется приближением с nt-битовой точностhю; полная ошибка и ху /21-,наверняка не хуже, чем п2- т, сле,J~он.атсльно, мы можем достичь точно­сти Е: вxyj2nпри т~Iogn/c.·.Если мы сохраним вентили, действующиетолько на пары кубитоu с расстоянием т или !\.fенее, торюмер схемы бу.tетравенmn ,. .