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

Более формально{С} ЕNP: С(х) ~ 1, если С(х, у)= 1 JlJlЯ{C}Eco-NP:C(x)=l, если C(x,y)=lОчевидно, что между классамисматриваем Jlli мы проблему извекоторого у;(6.28)(6.29)ллявсеху.N Р и со- N Р существует симметрия - рас­N Р или из со- N Р зависит от того. как былсформулирован вопрос. (Проблема <<Существует ·'" гамильтопов обход?»принадлежит классу N Р. llpofuleмa <<Действительно ли, что гамильтоно­ва обхода не существует?» принадлежит классу со- N Р.) Однако интересенвопрос: существует ли проблема (1/с Р), одновременно принадлежащая обо­им классам: NP и co-NP. ECJrn да, то мы можем легко проверить ответ(коль скоро имеем подходящий пример) независимо от того является имДА шш НЕТ.

Считается (хотя и не доказано), чтоNP cf co-NP.(При­ведя пример, мы можем показать, что граф имеет гамильтонов обход, номы не знаем, как подобным образом показатъ, что он не имеет гамюiЬтоно­вых обходов') При условии, чтоNPf co-NP,существует теорема, кото­рая утверЖдает, что ни одна со-NР-проблема не принадлежитдовательно, проблемы, принадлежащие пересечениюNРNPC.Сле­и со- N Р и приэтом не входящие в Р, являются хорошими кандидатами для вюооченияих вNPI.6.1. КЛА(СЙЧFСКИЕ (ВЫЧИ.СJИТЕЛЬНЫF.) СХJ::МЫФактически такой проблемой. принадлежащейN Рпсо-N Р,289относи­тельно которой считается, что она не входит в Г, яв~IЯется .fАСТОRING­проблсма. Как уже отмечалось, FACTORING-npoблeмa принаДJJежит клас­суNP,посколы<у мы :можем легко проверит1~ правилыюсп. нрелостав.-уен­НОI'О множи·tеля чисда х. Но она ·гакже принадлежит и co-.~.V Р, IIOCКOJIЫ<Yизвестно, что есди нам 1\ШЮ простое число, то (по крайней мере в прин­пиве) мы можем эффективно uроверить его просто1у.

Таким образом,ccJmнекто сообшает нам простые множители числа х, то мы можс~ эффектив­но nровери1ь, что раз.1южение на nростые множИ'l'еJШ прави.пьно, и можемисключить, что любое целое, меньDiее у, является делителем числа х. Сле­довате:rьно, похоже на то, -.::по FACTORING-пpoблcмa принадлежит клас­су NPI 1 •мы nришли к грубой (гипотетической) картине структуры N Р nКлассы NP и co-NP не совпадают, но имеют нетривиа.;!ънос не­ресечение. Класс Р принад:тсжит пересечению N Р n со- N Р (поскош.куР ~· оо-Р), по кроме этого оно содержит проблемы, не входящие в Г (по­добные ~АСТОRING-проблеме). Ни N РС ни co-N РС не пересекаютсяco-N f'.cNPnco-NP.~ожно было бы гораздо больше рассказать о теории с.пожности, но мыограничимся здесь упоминанием еще одного :1лемента.

свя1.апншп с оfiсуж­;~епием квантовой сложности. Ин01да полс:Jно рассматривать вероятност­ные схемы, которые имеют доступ к генератору случайных чисел. Напри­мер, венти.1:ь я вероятностной схеме может действоват1. одним из л;пух спо­собов и «подбрасывает монеrу)), чiобы рсшип., :какое действие въто:шитъ.!Iри одно" фиксированном IIXOдe такая схема может избрать один из мно­жества вычислительных путей. Об аш'Оритме, выполняемом вероя11юстнойсхемой, говорят как о ((рапдомизирОJ~анном».Если "ы пристуnаем к проблеме припятня решения, испш•ь.зуя веро­ятностньrй компьютер, то получаем распределение верояпюстсй результа­тов.

Таки" образом, мы не будем веста получать обязательно правиль­ный ответ. Но если д;тя любого возможного входа вероятность полученияправи:~ьного ответа больше, чем ~+б(б > 0), то такая машина Jюдез­на. Фактически мы :можс\1 многократно лои·юрипу вычисление и, учитынам1В 2002 r.1руппой индийских математиков 11редложен подиномиальный ,1етерм.и­нированный а.1rоритм проверки це.IЫх чиселность O((logn)k). щс n -на простоту._ Его асимптотич.::скаипроверяемос чи~ю, k -слож­це:юе ЧИС.ilО "' 10.

Таким обра­зом, проб.;н:м~t распо.."Jнаванюr простоты целщu чис:Iа принадлежит классу СЖJЖНоСПI Р.AgJawa], Х Кауа1, N. Saxcna, Primes is inhtlp:/lwww.matll.pnnccton.edu/"-'anoal:J . См. такжеМ.Р,Annals ot' Math., 160, 781--793 (2004),Л. К). Бараш, Алгоритu А.К5; проверки 'lиre'lна простотуи поиск k"VUCmaнm геие.раторvв псевдослу'lайных чисел, Безоnасность информа­ционпr.rх технологий, 2, 27-38 (2005). - Прим. ред.ГЛАВА 6290<<IO]IOC большинства», достичь вероятности ошибки, меньшей Е. Более то­го, количество необходимых для этого повторений вычисления всего лишьпо;шло[·арифмически зависит от Е -lt.Если пробнема допускает решение с помощью семейства вероятност­ных схем полиномиального размера, которые всегда дакл правШIЬный от-пет с вероятностью, большей ~ + б (дпя любого входа и при фиксирован­J > О), то мы говорим, чw она принадлежит ](J]accy ВРР («вероят­номностное поJШномиальное время с ограниченной ошибкuй» ).

Очевидно, чтоРе ВРР,но соотношение междучто ВРР содержится в6.1.3.NP иNP.(6.30)ВРР не известно. В частности, не доказано,Обратимые вычисленияРазрабатывая модель :КQЗН1ОВОГО компьютера, мы обобщим модельклассических вычислительных схем. Но нашими кванrовыми логически­ми вентилями будут унитарные и, следовательно, обратимые ''рсобразова­ния, тогда как классические логические вентили типа NЛND необратимы.Прежде чем обсуждат• квантовые схемы, полезно рассмотреть некоторыеособенности классических обратимых вы:чис:.~ений.Помимо их связи с квантовыми вычислениями, другие побудительныепричины для изучения обратимых К..'Iассичсских вычислений обсуждаяисьв первой главе. как заметил Ландауэр, поскольку необратимые логическиезлементы стирают информацmо, они с необходимостью диссипативны и,сле)l,овате:~ьно, требуют постоянного расхода энергии. Но ес.1и компьютероперирует обратимо, то в принципе не должно быть никакой потребностив :шергии.

Мы можем вычислять даром!Обратимый компьютер пычисляет обратимую функцию, иреобразуябитов в другиеnnбитов:f: {0, 1}" ..... {0, 1}";(6.31)функция должна быть обратимой, то есть ддя каждого выхода существуетединственный вход; тогда мы в принциле в состоянии пройти вычислениев обратном порядке и, зная выход, воспроизвести вход. Поско.тьку это вза­имно-однозначная функция, ее можно рассматривать как перестаноокустрок изnбитов-- псеrо таких функций1То есп. КОJП(Чество необходимыхpoly(log(<- 1 )). - Прим. рео2"(2n)'.повторенийограниченосверхупоJШномом6.1. КЛАССИЧЕСКИЕ (RЫЧlfСЛИТЕЛЬНЫЕ) СХЕМЫ291Конечно, любое необратимое вычисление можно «оформить» как вы­f: {0, l}n-+ {0, 1}"'{0, l}мm-+ {0, l}n+m такую, чточисление обратимой функции. Наиример, д.1Я тобоймы можем сконструироватьj:](x;o(m)) = (x;J(x))(6.32)(где o(m) обозначает m битов, первонач!LlЬНО положенных раnными нулю).Поскольку j иреобразует каждое (х; о( т)) к своему, отличному от других,результату, она может быть расширена до обратимой функции от n /-т би­тов.

Следова-rельно, для любой f, преобразуюшей n битов в m, существуетобратимая функция ], иреобразующая n + т битов в n + m битов, котораявwшсляет f(x), действуя на (х; Q(m))_Как теперь построить сложные обратимые вычисления из элементар­ных компонентов-то есть ч·тu образуст набор универсальных вентилей?Мы увидим, что одно- и двухбиmвых обратимых нентилей не достаточно;для универсальных обратимых вычислений нам понадобятся трехбитовыевентили.И1 четырех 1-бит-+1-бит вентилей обратимы два-Iривиальныйи NОТ. Из (2 4 ) 2 - 256 возможных 2-бит-+ 2-бит вентилей обратимы 41 =;:. . :.

24. Одним из особенно интересных является :вентиль контролируемоеNOTилиXOR,с которым мы уже сталкивались в четвертой главе:XOR: (х,у)-+ (x,xEJJy),х-r--у ~-(6.33)хxE!Jy.Этот вентиль инвертирует второй бит, если первый равен единице, и ничегоне де.rше·r, сени нервый бит равен нyJJIO (отсюда его название: контролиру­емоеNOT).Ьm квадрат является тривиальным, то есть он обратен по от­ношению к самому себе. Конечно, зтот венnшь выполняет операциюNOTна втором бите, ес.r.ш первый бит положить равным единице, и иыполняетоперацию копирования, если начальным значением у является нуль:XOR: (х,О) _, (х,х),С помощью схемыхуI ' r- у---4J'±J----<~>-- -4- х(6.34)ГЛАВА 6292построенной из 'IJ)eX ХОR-ов, мы \1Ожем поменять местами два бита 1 :(х,у)---> (х,хЕ!!у)---> (у,х®у)---> (у,х).(6.35)С помощью этих обменов можно тасовать биты внутри схемы, собираяих вместе,ec.;mмы хотим подействовать на них конкретным: компонентомв фиксированном положении.Чтобы увидеть, что одно- и двухбитовые вентиди неуниверсальны, за­метим, что все они линейl-lы.

Каждый обраiимый двухбитовый вентиль дей­ствует по правилу(6.36)где константа ( ~) принимает о;що из четырех возможных значений, а М о;_ща из шести обратимых матриц(10) (01)10' (11)ot' (10)11' (01)IJ' (11)1о·м~ о1·(6.37)[Все суммирования в (6.36) вьmолняются по МОJ(улю 2.] Комбинируя шестьвариантов М с четырьмя возможньпdи константами, мы получаем 24 рю­личных вентиля, которыми исчернывется набор всех обратимых2--+2вен­тилей.Поскольку линейные нрсобразования замкнуты относительно компо­зиции, любая схема, скомбинированная из обрати,.ыхвентилей, будет вычислять линейную функцию2--->2 (и 1n ;;3 31)(638)x~Mx-t-a.Однако при--->существуют нелинейпые обратимые функцииnбитов.Важным примером служит вептиль Тоффоли е(З) (или нважды контроли­руемоеNOT)e<'J: (x,y,z)---> (x,y,zex у);хуz-~t--ct--хуz~x.

у,1В двоиqной арифмеmке С.'Iожение по модулю 2 опреде.tяется как х фу ~ .r + у- 2х ·у.(xEEJy)®z -со x$(y6z) ----:х$ y$z.- Прим. ред.Эта опера.дИJI:, очевидно, коммутативна х$у---= уфх н ассоциаnшва-=::(639)6.1 . КЛАССИЧЕСКИЕ (ВЫЧИС1ИТF:ЛЬНЫЕ) СХЕМЫ293он инвертирует третий бит, сели два первых равны единице. и ничего неделает в противном с.-тучае. По;:юбно ХОR-вентилю он обратен по отноше·нию к самому себе.il от.lИЧие от обратимых двухбиrовых вентилей, оС 3 ) является универ­са.Iьным вентилем булевой логики~ec.;rnмы можем фиксировать некоторыевходящие битъ1 и игнорировать некоторые выходящие биты.ное значение-х·у -zEcmiравно единице, то на третьем выходе возникает хмы можем выполнитьNAND.Если же мы фиксируемначаль­1у ='"~1~l, товенти;1ь Тоффоли функнионирует подобно ХОR-венТШJю и может исполь­зоваться для копирования.Вентиль ТоффоJш О( 3 ) универсален в том смысле, что, используя толь­ко его, можно построить схему, вычисляющую любую обратимую функцию(при ус.1овии, что можно фиксировать входящие биты и игнорировать выхо·дящие).

Полезно наказать это непосредственно, не онираясr~ на наше болеераннее доказательство того, чтояаляется универсальным дляNAND/NOTвычисления любой булевой функнии. Фактически можно наказать следую­щее: из вентилей NOT и Тоффоли g(З) мы можем построить универсальнуюфункцию n бптов при условии, что мы имеем доступ к одно:му дОПОJIНИ­тельпому би1У в памяти.В качестве нервого шага покажем, LIТO из трехбитоных вентилей Тоф­фтш о(з) можно построить п-битовый вентиль Тоффо.шg(n),действующийпопранилу(6.40)Эта конструкция требует донотштельноr"О бита из вспомогательного про­странства.