Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 54
Описание файла
PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 54 страницы из PDF
ред.2Схемы должны быть апериодическими, н том смысле, •rm полностью .замккуrые цик:IЬIв них недопустимы.Г.IIADA 6284Часто оказывается, что вопрос, который не хотелось бы формулировать С.JIОвесно как вопрос, имеющий ответ ДА/НЕТ, может быть <<переформу.;шроваю> f<ЗК npofi>eмa припятня решения. Например, фувкция, определяющаяFACTOR!NG-пpoб;~eмy (задача факторюации):(х1 )1 'Узнаниесеf(x,{1' если целое х имеет делитель, меньший чем у'(6.21)О в противном случае;<у) ;~_;1я всех ух зк.вивалентно знанию наименьшего нетривиалыюго множите.nя х.
Друтим важным примером проблемы припятнярешения служит НАМILТОN!АN-проблема (задача нахождения гамильтонова обхода): рассмотрим !-вершинный граф, предстаменныйf х €-матрицей смежности (равенство единице ее ij-э:~емента означает. что существуетребро, связывающее верпшныiиj);функциях ~ { 1, ec.m граф х имеет гамiLТhтонов обход,f( ) -О в пропшном с:rучае.(6.22)(Обход называется гамильтоновым, если он прохол.ит через каждую вершину графа ТО,JЬКО ОДИН раз.)Мы хотим оценивать трудность проблемы, количественпо определяянеобходимые ;щя се решения ресурсы.
Сложность проблемы принятия решения разумно измерять размеро~ч мипима.1ьной схемы, вычисляющей соответствующую фувКIJиюf: {0, 1}»-->{0, 1}. Под размером мы понимаемкшшчество элементарных операций или компонентов, которые нужно обьединить в cxe~ty, чwбы вычис.1итьf.Также можно интересоваться те~.какого вре.меии требует вычисление, если многие операции могут н.ыпонняться параллельно. Глубина схемы нре)Jставляет собой необходимое количество шагов при условии, что онерации, Jtейстпующие на раз.ТJичные биты,могут выпотrяться одновременно (то есть 1:...1убиной Я:В..i1ЯСТСЯ максима.1ьнаяд.·шна нрямого пути от входа схемы до ее выхода).
Ширина схемы--это\.fаксимальнuе количество операций, выrюлняемых на любом из ее этапов.Мы хотели бы разделить проблемы принятия решения на дваIOiacca:легкие и трудные. Но где следуст провести границу? Расс'\ютрим с ·пойцелью бесконечные семейства проблем припятня решения с персменнымразмером входа~ то есть ко.1ичес'tВО биrов на входе может быть любымцелымn.Тогда можно проверить, как соиз.\fерястся сnразмер схс\1ы, решающей проблему.Однако в испою~зоваtши масruтабноru поведения семейства схем в качестве характеристики с.;южности задачи имеетсяo.wa.тонкость.
Бwю бы2856.1. КЛАССИtLRСКИЕ (ВЫЧИС1ИТЕЛЪНЫЕ) СХЕМЫобманом скрывать сдожность нроблемы в конструкции схемы. СледователL.но, мы дОJlЖНЫ ограничиться семействами, обладающими приемлемыми свойствами «однородности»сn-должно быть «просw» построить схему+ 1-битовы:м: входом, коль скоро схема с п-битовым входом уже построена.Пусть с данным семейством функций {fn} (где fn имеет п-битовыйвход) сопоставлены вычнСJIЯющие их схемы {Cn}. Мы говорим, что {Сп}является семейством схем «подиномиального размера)), есJШ размер Cnрастет сnне быстрее некоторой степениn:(6.23)size(Cn),;; poly(n),г;~еpoly обозначает по:шном.Тогда определим:?={проблема принятия решения, решаемаясемействамисхем}полиномиального размера(Р означает разрешимость за «nолиномиальное время»).
Проблемы nрннятия решения, принадлежащие Р, яв"'!Яются <шросrЬIМИ», остальные<<сложнымю>. Заметим, что Сn вычисляетf n (х)-для любого оозможноrо п-битового вхот(а и, следоJJатслыю, сели проблема принятия решенияпринадлежит Р, ro даже «в худшем случае)) мы можси найти ответ, используя схему, размер которой не nревышает poly( n).
(Как отмечалось выше, мынеявно предполагаем, что семейство схем «о;щородпоп, так что проблемаразработки схемы сама может быть решена с помощью алrоритма, требующего полиномиального времени. В этом предположении разрешимостьза полиномиа.Тiьное время с помощью семейства схем эквивалентна разрешимости за nолиномиальное время с помощью универсальной машиныТьюриша.)Конечно, чтобы определить размер схемы, вычисляющейf n' мы должны знать, что представ.;lЯют собой ее злементарные компоненты.
К счастью, принадлежиость проблемы к Р не зависит от выбора набора вентилей, до тех пор пока они универсальны, их множество конечно, а каждыйвенти.IЬ действует на ограниченное множество битов. Один универса...'IЬныйнабор вентилей может ,uоделuроваться другим.Огромное большинство семейств функцийf:{0, l}n-->{0, 1}неnринадлежит Р. Для большей части функций выход существенно случаен, и нет лучшего способа «вычислить>>значений.
Но поскольку имеется2nf(x ),чем обратиться к таб;,пще ееп-битовых входов, то эта таблица имеетэкr:пинепциальпый размер, такой же размер должна иметь и схема, кодирующая эту таблипу. Проблемы из Р nринадлежат очень частному юхассу-286гллвл6они имеют такую структуру, что функцияfможет быть эффектно но оычислеl!а.Особый интерес представляют проблемы принятия решения, на которые можно отоетить, приведя легко проверяемый при\lер.
ПуС1ъ, например, д,lЯ данных х н у<х трудно (в худше"' случае) опрспелиТJ,, имеетли х множите.'lь. меньше чем у. Нотакоеz <ecmt:кто-нибудь любезно предоставиту, на которое делится х, то нам просто проверить, чтоz.а:сйсrвительно яшmется множителем х. Ана.;югично трудно опрсде~шть, имеетли граф 1·амильтонов обход, но ес!IИ кто-нибудь нам его нока3З.:I, то легкоубедиться н ·rом, что он и в самом ;щле гамильтовон.Эту щtею, что проблема может бьГJъ трудно разрешимой, по ее решение, ко.'IЬ скоро оно найдено, легко про11еряе:мо, можно форма.низовать с помощью понятия «не;(етсрминиронанной» схемы.
Ассоцииронанная с С" (x(n)) кедстерминированная схема <'\,m (x<n), у< т)) обладает свойством1:СС:IИ(где x<n) представляетСп,тпr>.\'x(n)'y<"'))=l :Ддя пекоторога у\ т) (6.24)битоu, а y(m) - т битов). Таки"' обра:юм, ссJ1и у( т) оказа.rюсr:. удачно подобранным д.1я некотор010 x(n), ·ю мы можем исtюш;юватr:- дn,m дпя прове,рки того, что Cl'l(x(н)) = 1.
ОпределимN Р={ 11роблемы припятня решения, лопускающ. и е семейство kеде-}терминировттых схем попиномиа.пъншо размера(N Розначает ра1рсшимосrь за <<Недетерминированное по:rиномиальноевремя>>). !:'.ели проблема нрнна;щежит N 1', то нет гарантии, что она нростая. Это о:шачает лишь то, что ее реnrсние легко нровсрить, есди мыраснолагаем nравильной информ8дией.
Очев11дно, что 1' <::; N Р. Подоб·но Р, N Р-проблсмы образуют малый подкласс всех проблем J[ринятия решения.1Согласно одному из оnределений проблема прuнадпеЖJtт хлассу слож1юсти N Р, еслиcxe'll!a nuлиномиа..r.tьноrо по n. размера, проверяющая nредлuженнос решение :~аnолиномиальное RpeМJI. Проверяющаа схема [в дашюм случае зто д(х(п), y(m))] яаляетсясушествуетдетермшшрованной.
Термин недетерминированный происходит от того, что COI~'Iacнo друrо~му определению (см. следуюшее чуть ниже определение в основном тck~:rc)1\' Р-пробJJемадопусхаеr pt:lU~JLИe за полиномиапьuое время на таk щr~ываемой недетерминирtианный !~ашине Тьюрннта, способпой в некоторых состояниях выбирать раз..Jw!ПЪiе варианты вычнсJJени.и.. См. А. Кнтаев, А. Шеuъ, М. BJJ.;""IЬIЙ, Классичесkие и ЮlаJгrовьrе вы<~ис.'Iекия, М., МЦНМО,ЧеРо( 1999). -Прим. ред.6.1. КЛАССИЧЕСКИЕ (ВЫЧИСЛИТRЛЬН:ЫF:) СХЕМЫ287Многое в теории с.:южносm опирается на фундаментаныюе предположениеПредположение:РfN Р;(6.25)существуют сложные проблемы принятия решения, ретепия которых легко проверяемы. К сожалению, эта важная rипотеза все еще ждет своегодоказательства.
Однако после 30-ти ;~ет попыток nоказать обратное- большинство специалистов в теории слОЖJюсти твердо унерепы в ее справедливости1.Важным нримером NР-проблемы является CIRCUIТ-SAT 2 В этомслучае вход нредставпяет собой состоящая изnвентилей схема С с m-битовым входом и Однобитовым выходом. Проблема состоит в том, чтобынайти, существует ли какой-нибудь m-битовый вход, для которого выходравен единице. Функция, которую необходимо вычиСJШ'IЪ, представляет собойf С)~(Это{ 1, если существует x(m) такое, что C(xCml) с- 1,О в противном с;,учае.N Г-проблема,(6.26)поскольку данную схему легко смоделироватh и вьrчислить ее выход для тобого частного входа.Я персхожу к формулировке некоторых важных результатов теориисложности, которые будут il)IЯ нас важliЫ. Здесь не будет времени ,'\Ш! доказательств.
Вы можете почерnнуть больше, обратившись к одному из многихучебникон но этому предмету. 3Многие идеи, nорожденныс теорией сложности. вытекают из теоремыКука(1971 ). Она утверждает, что любаяводима кCIRCUIT-SAT.N Г-проблемаЭто означает, что для nюбойполиномиально приPROBLEMЕNPсуществует семейство схем полиномиа.;Jьного размера, которое отображает «ситуацию>> xCnl для PROBLRM на <<сюуацию>> уСт) для CIRCUIТ-SAT,то еСlъCIRCUIТ-SЛT(yCml) = !, если PROBLEM(x(n)) = !.(6.27)Оrсюда следуе1~ что если бы в нашем распоряжении имелось мrо,ическое устройство, которое мото бы эффективно решатьCIRCUIT-SAT1Проб.1ема оо0111ошени"!.
к.'Iассов слоJЮюстн Р н N Р uстается нс.реruенной 11. в настоящее11ремя (нач<JЛо 2007r.). Более roru она входиг R сииоок вюкнейших .'laдaq математики XXI в.При.м. ред.2CIRCUIT-SAT (circuit-satisfyaЬility) proЬiem- ЩЮ6JJема выполнимоств схемы. (нерев.)3Одной из лучших является книга M.R. Garey, D.S. Johnson, Computers and lntractabllity:А Guide to the Theory of N P-Competeness, русский персвод М. Г~ри, Д. Джонсон, Вычислительные машины и труdн.орешае.мые заdачи, М.: Мир (1982). [Краткий, но достiПОчно полный, обзор к.:1ассо1:1 сложности и их иерархии можно найпr в первой части kНИI'И: А.
Китаев, А. Шснь,М. Вя:лый, КлассичесюJ.е и квантовые вычисления, М.: МЦНМО, ЧсРо(1999).-Прим. ред.]288ГЛАВА 6(CIRCUIТ-SAT <<Оракул>>), то с помощью полиномиальной редукции мымогли бы связаться с ним, чтобы эффективно решить PROBLEM. Из теоремы Кука следует, что если вдруг О!Qlжется, что CIRCUIТ-SЛTтоР=ЕР,NP.Проблема, которая, подобно CIRCUIТ -SAT, обладает тем свойством,что к ней nолиномиально приводится любая проблема изется NР-поmюй(NPC).примеров NРС-проблем. Чтобы показать, чтоетсяN Р -полной,N Р,называПосле Кука было найдено множество друтихPROBLEMЕNPявлядостаточно найти: другую, полиномиально приводимуюк ней проблему~ о которой уже известно, что онаN Р-полная.Например,можно продемонстрировать пшшномиальную приводимость CIRCUIТ -SATк НAМILTONIAN.Toma из теоремы Кукаследует, что НAМILTONJ~"' тоже NР-полна.Если мы nредположим, что Рf NP,то отсюда следует, что всуществуют проблемы промежуточной трудности (классниN Р I).NPЭто ни Р,NPC.Друrой важный класс сложности называетсяN Р -проблемамиco-N Р.Эвристическиразрешимости являются те, на ко·юрые мы можем ответить, приведя пример, если ответом является ДА, в то врС!V!я как наco-N Р-проблемуможно ответить кoнmpnp'U..J\iepoм, сели ответом являетсяНЕ Т.