Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 63
Описание файла
PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 63 страницы из PDF
Мы сначала найдем f(x) при х .~N = 2n являет2"-- 1 - 1 и нроf(x), чем а. Uсли да, то мы найдем следующее f при1 и так далее. С каждым RЗГ:Iядом на табJшцу мы вдвое совсрим, бош~ше лих . . . : 2n·· 2 -кращаем количество кандидатов среди значений х, так чm достаточновзг:IЯДов, чтобы нрошерстить все2nnрассортированных записей. Вы можете использовать этот а.'П'Оритм, чтобы отыскать номер в те. i1Сфонной книгеЛос Анжслеса, поскольку в ней имена записаны в алфавитном порядке.Но донустим, что вы знаете чей-то номер телефона, и вы хотите узнатьего имя. &ли у вас нет возможности заглянуть в обратный снравочник,roпроцедура поиска буl(ет утомитещ,на. Ваши шансы таковы: вам придетсяпроверить порядочное количество отдельных записей в телефонпой книге,прежде че:м вы наткнетесь на извесrnый вам номер.Фактически, есш1Nнеобходимо просмотреть=1/2номеров записаны в случайном порядке, то вамномерон, прежде чем с вероятностью Р =найти его номер (и, следовательно, его имя).
Об11аруженное ГравеN /2ром сосmит в том~ что если вы имеете квантовую телефонную книгу, то,обратившись к ней примерно то:IЬКОJN раз, вы можете с высокой вероятностыо узнать интересующее вас имя.Эта задача юже может быть сформулирована как проблема оракула1[ .. К. Grover, Quantum Mechanirд Help.f in Searching for а Needle in а Haysюck, Pbys.
Rev.Lett., 79, 325-328 (1997); quant~ph/9706033.ГЛАВА 6330или «черного ящика». В этом случае оракулом является телефонная кнИI·аили справочная табmща. Мы можем ввести имя (значение х), а оракулвыдать нуль, ес;шf(x)fа, шrи единицу, еслиf(x)-=а. Наша задачакак можно быстрее найПI значение х, при коrорома.f(x) -(6.132)Почему эта проблема важна? Возможно, вы никогда не пытаJШСJ~ найти в телефонной книге имя, коюрое соответствует данно~tу номеру, но еслибы это не бьmо так трудно, то вы, может быть, гораздо чаще пыта.1Ись быдела1'ь это. Более широко метод быстрого поиска в неструктурированнойбазе данных можно было бы привлечь к решению любой 1адачи изN Р.Наmи~ оракулом может быть нодпроч>амма, которая опрашивает каждого потенuиального «свидетеля» у, коwрый потенциш1ьно мог бы нол;твердить решение проблемы. Например, если мы сташсиваемся с графом и на.\1необходи~о узнать, существует ли на нем гамилы'Оноп обхо.~~.
мы можемпредставить обход норакУJIУ)>, а он-быстро ответить, яв.:rяется зтот обХОJ~ гамильтоновым и:ш нет. Если бы нам бьш JL1всстен быстрый способспросить оракул обо всех возможных обходах, то мы бы;IИ бы способныэффекrивно найти гамильтонов обход (сели он существует).6.4.1.ОракулИтак, «оракулом» кратко называюr подпрограмму, которая быстро вычисляет функцию, чтобы проверить пред.1агаемое решение пробдемы приIrятиsr решения, однако проJ~олжим рассматривать оракул абстрактно, как«черный ящию>. Оракул <<Знает», Ч1'0 из2nвозможных С1рОК длнныnодна(«помеченная» строка пли <<решение» w) особенная. ""'ы предлагаем оракулу вопрос х, а он сообщает нам или хсообщает значение функцнnfw(x)fw(x)=О,=1,= v..-•,ИJШ нет.
Другими словами, онх i "'·х=I.V.(6.133)Даже более того, это квантовый оракул, следовательно, он может отвечатьна вонрuсы, прсдставляющие собой суперпозиции строк. Оракулом явдяется квантовый черный ящик, выпо!IНЯющлй унитарное преобразование(6.134)гдеlx) -п-кубитовое состояние, аIY) -однокубиrовое состояние.6.4. КВАНТОВЫЙ ПОИСК В БАЗЕ ДАННЫХ331Как мы ВИZ{ели раньше в других контекстах, состояние одпокубитоВОIО реmстра может быть выбрано равнымfi<IO) - IJ) ),так что оракулдействует какv 1,:-->lx) }z<IO) -11))1 (IO)- Jl)).(-1)t_(x)lx)-"12(6.135)Тепер1.
мы можем иmорировать второй регистр и по:I)'ЧИТЬ(6.136)или(6.137)Оракул обращает знак состоянияlw), но на шобое другое состояние! ортогональное lш), действует тривиально. Зто иреобразование имеет простуюJеометрическую интерпретацию. Действуя на любой вектор вrп...-тьбертовом пространстве,U _.;2" -мерномотражает его в пшернпоскости, перпендикулярной 1«~) (он сохраняет кuмпонснты в rинерн.ооскuсти и обращаеткомпоненту вдонь lш)).Мы знаем, что оракул выпо.ill!Яет зrо отражение для нею)Торого частно~-о состояния нычис:::штсльного базиса lu..:), но а priori нам ничеJ'О не и.звсстно опюсите:rьно значения строки I.JJ.
Наша :mдача - обращаяс1. к оракулуминималыше кол11чество ра·1, опрс,1елить6.4.2.с :максима.1Ьной вероятносn.ю.wИтерация ГровераВ качестве первого шага при1отовим сосrояниеN-1is) = _ JL,fN '"~оlx).(6.138)Равновзвешенная сунсрнозиция всех состояний вычислительного базисаможет быть :rerкo nО~'I}'Чена при:менением преобразооания Адамара к каж-lx1\Ому кубиту начального состояния= О). Xon~ нам не и:Jвестпо значение l..tJ, мы знаем, что li.tJ) Яll!Яется состоянием из вычис.;штсльноrо базиса,так Ч1U незанисимо от значения u.Jl(«.•ls)l1= - -.,fN(6.139)332ГЛАВА 612сли бы мы измерили состояниеls),проецируя его иа вычислительный базис, то мы «нашлю> бы маркированное состояние lc,;), с вероятностью, равной всего лишь 1/N.
Однако, следуя алгоритму Гровера, мы можем многократно итерировать преобразование, повышая амплитуду вероятности неизвестного искомого состояния lw) и одновременllо подавляя амплитуды всехненужных состоянийoJ с,;). Сконструируем эту итерацию Гравера, комlxбинируя выполняемое оракулом неизвестное отражениеUwс известнымотражением, которое мы можем выполнить сами.
Этим известным отражением является преобразованиеU, = 2ls)(sl-l,(6.140)которое сохраняетls), ио обращает знак ;nобого векюра, ортопшального ls). Геометрически, действуя на произвольвый вектор, оно сохраняет егокомпоненту вдоль ls) н обрашает знаки компонент в шпсрплоскости, ортогональной 1s).Ниже мы вернемся к проблеме построения схемы, выполняющейа пока ШIШЬ прс;щоложим, что можем эффективно выполнятьU s;U8 •Одна итерация Гровера представляет собой унитарное иреобразование(6.141)Rgrov---,- UsUw,в котором наше отражениеследует за вопросом оракулу.как Rgcov действует в плоскости, натянутой на векторыlw)Рассмотрим,иls).Прощевсего понять это действие, представив его геометрически. Вспомним, чтоl(wls)lтак чтоls)лежит•=)и= siл В,(6.142)nлоскости, натЯнутой на ортогональные веnорыlw)и l:.>j_), и наклонен к последнему из них под утлом В.
В этой плоскости Uwотражает вектор относительно оси lwl), а U, - относительно оси ls). Совместно два этих отражения поворачивают вектор на уголU,oИw ~28:28.Тш·да итерация Гровера является ничем иным. как новоротам на уголв плоскости, определяемой векторами6.4.3.ls)и201"-').Поиск одного из четырехПредположим, например, что в базе данныхN~4объекта, среди:которых один маркированный.
С помощью классических вопросов маркированный объект может быть найден с 1-го, 2-го, 3-го шш 4-го раза; в среднем для достижения цели необходимо 2~ вопроса, а в худшем случае -6.4.КВАНТОllЫЙ ПОИСК В БА:~Е ДАННЫХчетыре 1 Но так как нiн е-Jп ~тельно, ПOCJIC итерации Гровераликулярном lw1),ls)!,то е ~ зоа, 2е333= 60°и, следовапонорачивается в направ.."Iении, перпенто есть вдоль оси lw). Теперь измерение, просцирующеена вычислитепьный базис, с полной определетюстью дает результатI(A)).Достаточно всего одн01u кван·mвоп) вопроса.
чтобы найти маркированноесосmяние, заметное у.rучшение по сравнению с классическим с.пуч:аем.Иногда полезно альтернативнос представление итерации Гровера как«инверсии относите~1ьно среднего». Ес.JШ ра.1:Iожи1ъ состояние)'tl-·)в вычисJ 1ительном базисе(6.143).тто его внуrреннее произведение с ls) ~ - 1-..;NL lx) можно представить в вихде(6.144)где(n)-J~ L>x(б.145):с-средняя амшюуда. Тогда применениеU, ~ 2ls}(sl- 1 к I·Ф) дает(6.146)хам1mитуды иреобразуются какU8то естт~ коэффициент перед:ах - (а} -> (а}-ах,(6.147)Jx) инвертируется относительно среднего значения амнлиrуf(ы.ls) кажл:аяа'Ап:rи·rуда равна ~.
Один rюпрос оракулу обращает знак амrшитуды марВозвращаясь :к случаюN=4,заметим, что в сосmяниикированного состояния и, таким образом, сокращает среднюю амплитуду1Конечно, если мы знае\оl., чm один маркированный объект :щссь обя:штельно нрисутствует, то Че'mертый вопрос на самом де;tе я:в.гurется изmtшним, так ч1о можно быть точнееи mнорить, что необходимо самое большее три вопроса, а в среднем1- 21.ГЛАВА 6334до14. Тогда инверсия относительносреднего значения переводит амшrиту-;tы всех немаркированных состояний от ~ в нуль и увеличивает амплиrудумаркированного состояния от-~ до+!.
Итак, мы воспроизвели наш выводо том, что достаточно одного вопроса, чrобы с попной определенностьюнайти маркированное состояние.Также легко понять, что одного вопроса достаточно д;тя того~ чтобынайти маркированное состояние, если в базе данных имеетсяи ровноNзаписейl из них маркирована. Тогда, как и выше, один вопрос сокращаетсреднюю ампдюуду от ]., доvN~' а инверсия относите.1ьно среднеrо2vNсокращает амп.1Итуды немаркированных состояний до нуия.(Сравнивая количество квантовых и классических вопросов, с которыми нужно обратиться к оракулу, возможно, не совсем справедливо говорить,что в квантовом случае необходим rоль:ко один вопрос.
Если оракул Rыпuлняет проrрамму, которая вычисляет фунщию, то в пролессе вычислениянекоторое вспомогательное пространство будет заполнено мусором. Намбудет необходимо удалить мусор, пройдя вычисление в обратном направлении для ТОIО, чтобы сохранить квантовую когерентность. Если классическое вычисление необратимо, то нет необходимости возвращать оракулв исхо;1ное состояние. В этом смысле, на языке теории сложности, одинвопрос клантоnому оракулу может быть примерно эквивалентным двум вопросам классическому оракулу.)6.4.4.Поиск одпоrо изNВернемся теперь к случаю, в коrором база данных содержитNоfiьектов, среди которых ровно один маркирован.