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

_, n log n/ Е.Фактически, если мы собираемся измерять в вычис.lrпельном бюнсенепосредственно посне выпо.:шенияно дальнейшее упрощение-QtT(И.i!И его обращения), то возмож­двухкубитовые вснти.1и не нужны вообще!Заметим, во-первых, что венти.1ь кшпрошrруе'\1оеричным образом на два кубитаи-R 0•}(ействует сим~fет­он действует тривиально наJOO), [OJ)110) и изменяет фа:зу r1 I? на ~i()J.. Таким образом, без ~011Ификации вен­ПUIЯ можно менять местами «контро.1ьный>~ и «не.1евой)) биты. С учетомзтой замсны наша схе.,.ш дJIЯ трехкубитовоrо 01--·т мшкет бып.

п1ображена.6.10. (l)AKH>PlBAЦШI35933НОВО как--,J--1 (___c_J-~---....---·_, Н.?,т,, ) -1--·~ Н1LКоль скоро lvп) \ВМерено, нам известно значение бита. который унрав.Jя­R. 1• .Jtйствующ:и:ч на ilBa первых куб~па. CIC,'ЮlШl-c;rыro, :-.-tыет вентиле\1tю:тучи\t то же самое расrlрс_це:Jенис веrоятпостей рс3у.1ыатон измереt1ий,ССJШ 1шесто применснJ-нi кшпро:шруе~юю Н 1 и послс;~ующсrо И"i:мсрсния\fЫ снаlш:rа ИJМсрим у 1 ,, а затем 11рименим к спедующС\1)' кубнту пово­рот(R 1) у,,. обус:юв.1енный результатом измерения псрво1о куби га.

Ана.,ю­гично чожно замепи·1ъ вснтшш контролируемоеR1и контро.1ируемоеR-?оцнокубитовьr."-f IЮВорото:м(6.223)[то есть Новоротом с относитс.аыrоН фа·юй п(.у 1 у 0 )], Ж":йствующим натре­тий: кубнт после того, как бьши измерены значения у 1 и у 0 .R общемслучае. если мы собираt?мся и3мерять после выщ)Jшениято }1,.1Я его осущсств.1ения пеобхщщмо только тt пенти.1сй А.Qамара иоднокубитовых поворотов. Проi,едураQfiT.n -1QFT 3амсчатслъно нроста!6.10.Факторизация6.10.1.Ф31аорюация как отыскание периодаЧто связывает пpoбJie:\ty факторизации (поиск прuстых множите.'1ейбольшого составншо шыожитсльногu целого числа) с периодичностью?Существует хорошо известная (ратщ~fи·юванная) редуъ:ция факторизациик опреJ.еJ\ению периода функции.

Хотя ::па редукция непосредственно несвязана с квантовы~ш вычис.1ениями, \1:Ы обсудим ее 1_цесь J:ЛЯ по.1ноты,а также и по·1ому, что нерспектива исriО.JhЗования квантоно1·о комш.ютеракак инстру-мента факторизации вьпывает сто.1ь си.1ыюе нолнение.ДопусПI;\t, мы хотим найти ~но житель п-битового числапсевдослучайным образом а.<NN _Выбереми вычис.1им наибольший общий де.1и-Г;JARA 6360тель GCD(a, N), что можно 1ффективно [за время порядка (log N) 3 ] вы­нолнить с помощью алгоритма Lвклида. Если GCD(a, N)Nявляется пстривиальным множителем числаноложим, что~CCD(a, N)f1, тогда GCLJи задача решена. Но нред­1.Оrступмпие: алгоритм Евклида.

Ч'юбы вычислить GCD(N 1 , N 2 ) (приN1>N 2 ) разцелим сначала N 1 на N 2 , получая остаток R 1 . Затемра.щелимN2наполучая остатокR 1,R 2.Раздели,мR1наR2и такдалее до тех нор, пока не получим в остатке нуль. Пасдедпий иену­левой остаток и естьR ~ GCD(N1 , N 2 ). Чтобы убс;1итьсяв том, чтоашоритм работает, заметим лишь, что: (1) на R делятся все предыду­щие остатки и, следовательно, лт 1 идс.IЯтся1V1 и N 2,делитnccN 2 ; (2) любое чисJЮ, на котороеостатки, включая Н.

Общий делитель лт1и I'Г2 , который в свою очередь деmпся на все оста.Jrьныс общие дели­те.1и зтих чисе.1, есть не что иное какGCD(N11 N 2). Чтобы понять,сколько времени занимает алгоритм Евклида, заметим, ч1оRjгде q;?: 1, а RJ+2< nj 11;~ qRн 1+ Rн 2 ,следовательно, Rj+2(6.224)1< 2RJ.Два )(еJIСНИЯсокращают остюок как минимум в два раза, так что требуется не бо­лее чем 2log N 1 делений, каждое из которых испо:Iьзует О( (log N) 2 )элементарных операций; полное КОJmчество операций имеет поря­док О( (log N) 3 ).< N, взаимно простые с N (не имеющие общего множи­N), образуют конечную грунпу относительно умножения но мо­дулю N.

[!lочему? Нам нужно установить, что каждый злемент а име­ет обратный. Но для данного а <" IV, взаимно просmго с N, и каждогоЬ < ~N. пробегающего все в3аимно простые с ..:rv значения, все произведенияab(mod N) различны 1 • Следовательно, для пекотарого Ь мы должны иметьа.Ь"" l(modN); таким образом, число, обратное к а, существует.] КаждыйЧисла атеня сэлемент а этой конечной группы имеет конечный порядокr,нанменылееположительное целое чисJю такое, чтоа'"= l(modN).Порядок а по модулюNянляется периодом функцииfNа(х)- ax(rrюdN).--~--------------1Если(6.225)N - делитель числа аЬ - atl, то оно должно делителем и Ь - Ь'.(6.226)6.10.

ФАКТОРИЗАЦИЯ361МЬI знаем, что существует .эффе.ктиrшый кван1ояый а.:'Iгоритм, позволяю­щий найти период функции; следовательно, если мы можем эффективновычислитьfNа• то также эффективно можем найти и порядок а.На первь~й взгляд, вычис~IСЮiе f N ,а может по казаться трудным, по­ско.;IЬь._J' показателr, стснени х может быть очень большим. Но есJШ х< 2ши мы нре..uставляем х в виле дооич1юго разложениях =Xm -1 ·2m.-! +xm-2 · 2m-2+ ··· + Х1''+ Хо,(б·.:..227)то(6.228)Каждое a 2 j имеет бош.иrой показатель степени, тем не менее оно можетбыть эффективно вычислено классически.м компьютером путем повторноговозведения в ква,1ра:r:а 2'(mod N) - ( а•' ')' (mo<l N).То есть необходимо только т- 1 (КJJассических) умпоженийчтобы собрать таблицу всех а''.Вычисление ax(mod N) ВЫПО;JНЯСТ программа(6.229)но модулюN,11\iPt;T 1For j ~О to т- 1, if xJ = 1. MCLПPLY а 2 'Она 1ребует максимум т J"'НОжений по МОi()'ЛЮN,каждое из которых Iре­бует порядка (log N) 2 элементарных операций'.

Пocкo.ThkJ' т< N, у нас бу­,г~уr· нсrшохис шансы успешно выдетпь период, если выбрап.Следовательно, вычислениеfN11m"' 2Jog]'i.может быть выполнено семейством схемразмера O((log N) 3), имеющих' следующую стр)'К1)')1у:rlx·)[х1)[хо)~'[1)+---·-l~~~-{а:}1 ..----;-------1Исrюльзуиразные трюки д.'IЯ еыпо.ЩiеНИJI эффекrnвноrо псрсмножении очень боль­ших чисел, J(QЛИчество элементарных операций можно сократить дохlog log log N); таки'lt образом, асимптотически при больnшх NO(log 2 N log log N log log log Л') может вычисшпь fN ,а .O(IogNioglog!\'xсемейство схем ра1мераJ'ллвл3626Умножение на а 2 ) выпоJlНЯется, если контрольный кубит xj имеет значе­ние 1.Предположим, что мы нашлиr,период а по модулюN.Тогда, если тчетное, тоN является денителем числа (ar 12Очевидно, чw N не делит ( ar 12был бы~(а'/ 2+ 1)r/2.из а'/ 2N1).(6.230)1); если бы это бьшо так, то порядок аN не яв:тяется делитсJIСМТаким образом, если наряду с этимилиа'/ 2тогда-+ 1) (ar 12 -долженf-1(modN),(6.231)иметь нетривиа.ньный общий множитель с каждым± 1.

Следовательно, GCD(N, а'1 2 + 1) f 1 является множителем N(что можно эффективно определить с помощью кпассических вычис.1ений),то есть залача решена.Таким образом, коль скоро найдено r, мы успешно факторизова­N, за искшочением случаев, когда (1) r нечетвое или (2) r четноси а' 12 = -1 ( mod N). Насколько веJХ>ятеи этот успех?лиДонуспrм, что ]V является произведением двух простых множите­.·,ей Prf pz:(6.232)(это фактически самый неблаrоприятный случай). Для каждого асуществуют единственные а 1< р1и а2< Р2а= а 1 (mod р 1 ),а=(6.233)a,(modp2)-Следоватедьно, случайный выбор а< N< р 1 р2такие, чтоэквивалентен случайному выбо­руа1 <р 1 иа 2 <р 2 .Отступление: мы используем Китайскую теорему об остатках. Реше­ние а уравнений( 6.233)единственно, поскольку если а и Ь являютсярешениями, то р 1 и р 2 должны быть деJПiтелями аществует, поскольку каждое а<-Ь.

Решение су­р 1 р 2 решает уравнения(6.233)принекоторых а 1 и а 2 . А так как имеется ровно р 1 р 2 способов выбратьа 1 и а 2 и ровно р 1 р 2 способов выбрmъ а,roединственность означает,что для каждой nары а 1 , а 2 сушествует соответствующее ей а.6.10. ФАКТОРИЗАЦИЯ363Пусть теперь r 1 обозначает порядок а 1 по модуmо р 1 , а r - поря­2док а. 2 по моJJ:ушо р 2 . Китайская теорема об остатках уrвержJ(ает, что ar =:=l(modp,p,) эквивалентно тому, чтоajа2С1едовательно,яnлястся=l(modp,),=l(modpЕсJШr = LCM(r 1 , r 2 ).r1иr2оба нечешы, то таковым жеи мы проигрываем.r,Но если одно из двух чисел,ся(6.234)2 ).r, и мы продолжаем игру.r1илиr 2,четное, то таковым же являет­EcJDIа: 1 '=-l(modp1 ),(6.235)а.;!'= -l(modp 2 ),=-l(rn()(!pто а."/ 21p 2 ),и мы снова проигрываем. Но ес.ти илиа: 1 '=-l(modp/2= l(пюdр2 ),a~l'= l(nюdp 1 ),Т'а2или1 ),(6.236)(6.237)а;!'= -l(modp 2 ),то ar/ 2венство а~п.r/2и мы выигрываем. [Конечно, одновременнос ра­fc -l(modp 1p 2 ),12= I(modp1 ) и а; 1 ' =I(modp2 ) невозможно, что означало бы= I (modp 1p 2 ), то ес1ъ r не могло бы быть порядком а.]Допустим, чтоr1::-:- 2cl · ( НСЧСТН.QС ЧИСЛО),r 2 = 2cz · ( нечетное число),где с 1> с2 •(6.238)Тогда r ~ LCM(r 1 ,r2 ) = 2r2 · (цeJioe число), так что а"/ 2=l(шodp 2 ), а уравнения (6.236)удовлетворяюrся- мы победили! Аналоrич·но с 2> с1подразумевает уравнениепри с 1 = с 2 имеет местоИтак,1-мы снова в выигрыше! Но= r1- (нечетное число)=так что удовлетворяются уравненияа при с 1(6.237) · ·r 1 · (нечетное число').(6.235)- в таком едучае мы проиграли.все сводится к альтернативе: при с 1 ·- cz мы проигрываем,с 2 -· побеждаем.

Насколько Rероятно, что с 1 -1- с 2 ?rГЛАВА 6364Полешо знап>, что мультюшикативная группа по модулю р являет­ся цикличес:кuй-она имеет такой образующий элемент порядка р -1,что все элементы яв.пяются его степенями. [Почему? Множество целых чи­сел по модулю р образуют конечное поле. Есни бы груnпа не была цик­лической, то максИМа.JlЫIЫЙ порядок ее элемеН'ТОв бьтл бытак что xq=1(modp)имело бы р-1q <р- 1,решений. Но зто невозможно: наконечном поле существуст не более чем q корней q-ой степени из едини­цы.]Допустим~ что р- 1 __:___ 2k · s, где s -- нечетное, и рассмотрим норядки- 1. Для IqJаткости мы об­судим только самый неблагоприятный д..'IЯ пас случай k = 1.