Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 62
Текст из файла (страница 62)
!{опустим, что нас Уi\ОВЛетворяет предпо,;:южение о сбалансированности или постоянстве с вероятностьюуспехаP(success)Еслифункция>1-Е.(6.119)действите:Jьно сбалансирована~ния всякий раз одного и того же ответа наkто верояпюсть получезаданных вопросов равна р- z-{k-l). Если пuслс получения одного и того же ответа k раз nод-3256.3. НЕКОТОРЫЕ КВАНТОВЫЕ АЛГОРИТМЫряд мы сделаем предnоложение, что функция постоянна, быстрый бейесовский анализ показывает, что верояnюсть тоm, чrо наша догадка ошибочна.равна21k-l-1 1(в предположении, что сбанансиронанность и постоянствоа priori равноВероятны).
Итак, если мы высказываем догадку после k вопросов, то вероятность ее ошибочности(6.120)Следовательно, мы можем досПfЧь нсрояпюсти успеха= 2k 1(2k-J] - е при t.:- 1 =+ 1) юи при k ~ ~ log ~·А так как экспоненциально высокаявероятность успеха досrnгается с помощью пошшомиадьного количестваповыток, то на самом деле незаконно говорить, что проблема является трудной.3.Задача Бернштейна- Вазирави.Точно такая же схема можетбыть использована ,д.'IЯ решения другого варанта задачи Дойча- Йожы.Предположим.
что наш квантоный черный ящик вычисляет одну из функцийfa,1ДСfa(x)=а-х,а а представляет собой n-биrовую строку. Наше задача(6.121)-опредеJШть а.Квантовый алгоритм может с определенностью решить зrу задачу, нолучив только один (п-кубитовый) квантовый вопрос. Для этой конкреnюйфункции квантовое состояние в уравнении(6.115) имеетвид2n.~12"-12~I: I: (-l)"x(-l)"Yiy).х==О(6.122)у=ОНо фактически2n~l_!_"(~!)"'"--оа,у'2n "'(~1)"L(6.123)х=Ото есть этим сосrоянием ЯRЛЯется )а). Мы можем выполнить схему один рази измерить а-кубитовый регистр, обнаружив с вероятностью единшщ n-биrовую строку а.Если разрешены то:n.:ко к.rасснческие вопросы, то на;каждый из нихмы no::ryчae" rолько один бит информации и для определения значения атребуетсяn вопросов.
Следовательно, мы имеем четкую границу между квантовой и классической сложностью задачи. Правда, этот пример не326вскрывает соотношения vtCЖ/~YRP РнHQ Р,носкшrr.ку классическая '~адачане является трудной. Количссrnо вопросов, необходимых с к.гшссическойточки зрения, всего лишь линейно, а не экспtтенциа.;н,но но рю.меру входа.4.Задача Саймона.Бернштейну и Ба:;ирани упалось сфор,."риро·вать вариант nре,цыдущей 3адачи. который является классически труJ.ным, и, таким образом, впервые установить «релятиюпированную» границу между квантоной и классической СJЮжностr~ю .
.М:ы найдем более rюучительны~ рассмотреть более простой пример, нескоJrько rю·щвсс прС!'(.Юженный Даниэлем Саймоном.Снова нам предоставлен квантовый черный ящик, и на этот раз ~ы уверены в том, что он вычис:IЯСТ функцию «2 в 1»f {0.1}" __, {0, 1}".(6 124)Бо:rсс того, функrщя имеет период. определяемый п-битовой строкой а~ тоестьJ(.c) = f(y),еслиу=";+ а,(б125)где tD- побитовая ХОR-операuия. [То се rь а является нсрио.::J.ом, если мырассматрнвас'Vf ::с принимающи.м значения из (Z:2 )77 • а пс и.з Z:". 1 ] ')то вес.что нам и.1вестпо об .Г.
Наша за,:.(ача·- опре.:з;е:тить1начсние а.Эта задача ютассически тр_\,дн.ая. Нам необходи:мо обратиться к оракулу :1кспонсiщиально бо;1ьшос количество раз. чтобы иметь какую-нибудьразумную вероятность онрсде .1епия а. Мы ничего не узнаем, пока ню. f неповезет выбрать два вопроса х и у, кторые случайно окажутся удовлетворяющими х·Г:а =у.
Допустим, напрю.fер, что мы ныбираем 2n/.J вопросов.,,Количество пар вопросов меныrrс ЧС~f (2n/-l)~, и д.ая каждой иары {:г, у}вероятность тон>, что х Е& а. =у, равна2п. С1едтштслыю. вероятносл,успешного отыскания а меньше, чем(6.126)даже нри ')кспонснциалт,нобольшом:количестве вопросовверонгностьуспеха :жспоненциально мала.Если угодно, эту зцачу можно сформулировать как про6,1ему приня·тия решения: функция f является и;Iн о,цно-одно1начной (1 в 1), н.ш оrображает два в од.ю (2 в 1) с некоторым случайно выбранным периол.ом а:1(Z )n -группа, з.:Jе.\1СН"Пt.\Ш которой являются дB,)П'JHr.r<:: строки ,l.щны п.
ГpytJIJOJJilЯ2анерация предстакntет собой nо6нто~mе сложение n1.1 моду.1ю 2. Z .• - 1pymra оста.тков ol2сложения па моду:1ю 2п.-Прю1 рi!д6.3. HF·кororьrr 1\RAHTOBЬIE л_'IНН'ИТ.\1ЬI327обе 'Ни l3lУ~:vюжнос 1·и И>v1t:IOT аnриорные нерояпюсш,....(е,тип., являсi'СЯ :ти функтн-тяJ /'2. llaч ну:;кно опрс1 в 1 и.ти '!в 1. ТОI>щ нос.1с :2';'· 1 классическихвоrтросов не рою ность коррсК1rюй доrа.'lки Уоlонле гворяет нсравенстн.у(6.127)и не у;шляется отl/2 при бо.1ьших значсшн1х n.Но д,1я квантовых вопросов пробнс~tа 5Ш.lястся щюс·rой! Исно:.Jиуе'\13Я паыи схе:\13~ по существу) та же.
что и выше, но rеперт. оба репrстрарасншрены доnкубитов. :у{ы готовим равновзвешенную сунер1ю·нщиювсех п-fiнтовых строк (i~Сйствуя на IO) преобrа:н_1вание).\ Н'~ 11 .!), а за1·ем обращаежя к оракулу:и1 :'"-1(~ l:r)'] .-. -- l)IO)Llг)lf(:т))(6.128)J=IJТеперь мы Н.1Л-tерясм второй рсп-rстр. (Этот '1ТШI на са:vю_\1 деле не об}пате.сrен, но Jдя }!С н ости И1!JОжепия я вк.1ючаю его сюда.) Ре·3уJ1ы а·10_\1 И1-мсрения ЯВJтяе·Iся ·зю1чснис, с.лучайно выбраннос из 21 ' 1 раннонсроя1ныхлычсний .f'(.c). ДОllуt:·нш, pL":iy.Jьн:tтo\1 нв.IЯСТОI /(гr,)- Топ~а, поско.1r.ку оба·шачетrия.:r( 1 и.г,, :_1 а, н то;-ll,к:о они отображаются функциейIна f(:г,_)).
мыириготонили состояние-1,().с,,) + lт, 1 'Р а))/')(6.129)v-ВIICpB0'\1perИC"IJ)C.Тенсрь мы хотиr.-t изв.1счь некоторунJ информаr{ию относитеш~но а,Очевилно, что на :)ТОм этане было бы беспо;rезно и·змерять репrс·1р (в вычислительпо.\1 ба'3исе). Мы получJПИ бы результат ::r 0 идиносты-оНо1/2;· 0 '}:1а с верояткаждый. но ни тот. ни .J.PYI'OЙ ничего не сказал бы о зн:ачении а.нредставим теперь,что нспосреJ{Ствснно перед измерением мыпримени.·ш к рсгнс1ру преобразонанис А;щ:мара н Сп):Hl"i1v.:L(IJ.·,,; + IJ·п s а)!~'2''-L1j1?(n-l)/2-1[(-IJ''· (-1)''•+"''11v 1Г),~(-l'"''lv'.11L-п у=С1(6.130)ГЛАВА 6328Если а. у = 1, то слагаемые в коэффициенте перед IY) интсрфериру:qют деструктивно.
Следовательно, о сумме пония с авыживают rолько состоя·у =О. Тогда результатом измерения является случайным образом выбранное WJ всех возможных значений у, поЯВ.:lЯЮщихся с вероятностью 2- (n--l), таких, что а· у= О.Мы многокраТFIО повторяем этот алгоритм, получая всякий раз ещеодно значение у, удовлетворяющее а.у=О.
Кпк только мы найдемnтаких линейно независимых значений {у 1 , у2 , у 3 , ... Yn} [то есть линейнонезависимых над (Z 2 )n], мы можем решить уравненияYl.а= О,У?. ·а=О,(6.131)Yn.а=- О,чтобы определить единственное значение а, и, таки:.\f образом, решить ноСШIIЛСнную задачу. Нетрудно видеть, что с помошью О( n) повторениймы можем достичь верояmости успеха, зкспоненrщалъно бmвкой к единице.Итак, наконец-то мы нanurn nример задачи, которую можно решитьза полиномиальное время, используя кванrовые суnернозиции д.ая данного частного типа оракула, тогда как если ограничиn~ся :к.,--шссичсскими вопросами, то для этого потребуется .экспоненциальное время. Специа.,"'Iистпо теории вычислений мог бы сказать:Сушсствует оракул, относительно кoroporoBQP1- НР РЗаметим, что всякий раз, когда мы сравниваем юJассическую и квантовую сложность относительно оракула, мы рассматриваем юJЗiповый оракул(вопросами и ответами являютсЯ состояния в rильберовом nространстве),но с выделенным: ортонормированным базисом.
Если мы предлагаем классический вонрос (элемент выделенного базиса), то всегда подучаем классический ответ (друrой элемент базиса). Проблема в том, можем ли мыдостичь сушсственноrо ускорения, выбирая более общие, квантовые, вопросы.6,4.Квантовый поиск в базе данныхСледующий алгоритм, который мы изучим, подобно алгоритму Саймона, также демонстрирует ускорение по отношению к тому, чcru мы мо-6.4. КRАJПUВЫЙ ПОИСК Н БАЗЕ ДАННЫХ329жем достичь с помощью классических. вычислений.
Однако в противоположность зкспопенциальному ускорению рещения задачи Саймона в этомс:~учас ускорение юлько квадрати<пю (кванmвое время растет как квадратный кореш~ классического времени). Несмотря на зто, результат (открытыйЛ. J ровером) чрезвычайно интересен ввиду большой поj]езности этото алrоритма1.Рассматриваемая эвристически, проблема, к которой мы обратимся,выглядит так: мы столкнутt:сь с очень большой неструктурированной базой данных, содержащейN>>1 отдельных обье:ктоR, а нам необходимолокЗJШЗовать один конкретный объект, одним словом, найти иголку в стогесена.
С математической mчки зрения база данных представпена таблицейили функцией f (х) с х Е {О, 1, 2, ... N -1}. У!ы уиерены в том, что отдельная заnись а пояюяется в таблице пJ.'IЬКО один раз, ю есл. чю f (х) = атопько при одном значении х. Проблема состоит в том, чтобы по данному аотыскать эm значение х.Ес:~и база данных подходящим образом структурирована, то поиск хпрост. Возможно, кто-то бьш настолько любезен, что записал значения ав возрастающем порядке. Тогда мы можем найти х, просмотрев толькоlog 2 Nотде:.~ьных затшсей в тaбJmue. Предпо.аожим, чтося степенью двойки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
