Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 66
Текст из файла (страница 66)
так и неправы.Мы можем также показать, демонстрируя явный алгоритм (см. упражнение), что для онределеllияминированного) достаточноPARITY (илиN /2 вопросоввероятностного, или детер(при условии, чтоNчетное). В ·уюм смысле мы достигаем двукратного ускорения по сравнениюс Юiассическнми вопроса.'-!и. Но это лучшее из того, чего мы можем добиться.6.8. ПОИСК В РАСПРЕДЕЛRНIЮЙ БАЗЕ ДАННЫХ6.8.347Поиск в распределенной базе данныхПоучительно вз1лянуть на квавто.вый а.пгоритм поиска в базе данныхс новой точки зрения. Представим, что двум участникам, Алисе и Бобу,необходимо договориться о встрече в удобный для обоих день.
У Алисыесть календарь, в который внесеноN _ _ :_: 2nдней, каждый из которых отмечен нулем, если в этот день она занwrа, или единицей, если она свободна.Аналогичный календарь имеется у Боба. Их задача найти день, в которыйони оба будуТ свободны.Алиса и Боб имеют квантовые компьютеры, но они находятся оченьдалеко друг от друга.
(Алиса на .Зем:Jе, а Боб путешествует по туманности Андромеды.) Следощнельно, для них слишком дорого связываться другс другом. Им нужно срочно определить дату, но они должны экономить наобъеме посылаемой туда и обратно информаоин.Даже если существует день, когда они оба свободны, может оказаться, что найти его нелегко. Если Алиса и Боб связываются, посылая тудан обратно классические биты, тогда в ХУJ(шем случае им будет необходимообменяться порядкаN = 2nзаписями календаря, чтобы иметь разумныйшанс уснешно договориться о встрече. Мы спросим: может быть, вместозтоп' им лучше обмениваться кубитами? 1 (Or .земли до Андромеды тшателыю спроектирован и построен кRантопый информационный хайвей, такчто посылать кубиты вместо битов не намного дороже.)ДJТя знакомого с основами теории квантовой информации этот водросвыглядит странным.
Теорема Холе во раз и навсегда сказала, что один кубитможет нереносить не более одного бита классической информации. Хотя,немного подумав, мы увидим, что теорема Ходево факrнчески не решает проблему. Хотя она ограничивает взаимную информаоию приготовлениясостояния и результата измсрення, она не гарантирует (по крайней мере непрямо), что Ал11ее и Бобу необходимо обменяться таким же количеством1В ранней версии этих лекций я пред:шшл другой сценарий, в котором Алиса и Боби-мелk почти идентичные таблицы, по с одной песовпадающей записью; их задачей былонайти ноложение несовnадающеrо бита.
Однахо этот пример был нсу;щчен, посJСольку задачамогла быть решена с nомощью всего лиniЬlog N битов i(..13ССИЧеской связи. (Я благодаренA..Im:ca узнала адрес (двоичнуюРичарду Клину, УКil-~авшему на Э1)' ошибку.) Мы: хотели, чтобыстроку длинойn)одной '3а!Jиси, 1rоторой ее таб..'Шца отличается от таблицы боба. Дл.а этогоБоб вычисляет четносtъN /2записей сноей таблишк с метюJЙ, принимающей значение Ов ее сам.ом младшем зllачащем бите, и nосылает А'IНсе только бит чеmости. Аш1са сравниваетчеrnость ~х же записей ее таблицы и находит один бит (самый младший значащlil:й бит) адресапесовпадающей записи.
Затем они повторяют то же самое ДJll каждого из ocтaвiiiiO[CJIбитов до тех пор, пока А.Jиса не узнает полный адрес «ошибкИ>).битов (к все от Боба к А.тшсе).Bcerun - 1nпослано только348ГЛАВА 6кубитов, что и битов, чтобы сравнить их календари. Тем не менее ~по приятный сюрпиз- узнать, что АJшса и Боб могут выпошпrrь задание, обменявшись О( VNlog N) кубитами по сравнению с O(N) классическимибитами'.Чтобы добиться этото, Адиса и Боб должны действовать сообща, осуществляя распределенную версию поиска в базе данных.
А:шса имеет доступ к оракулу (ее календарь), вычисляющему функцию fл(х), а Боб имеетораку:I (его календарь), вычисляющийf в (х). 13местс они мoryt· предложитьоракулуfАв(х) се fл(х) А fв(х).Один из них может осуществить отражение(б187)U :;• так что они могут выnолнить полную итерацию Гровера и произвести исчерпывающий поиск подходящего днях такого, чюfA 8 (x) = 1 (котаАлиса и Боб оба свободны).Если взаимоприемлемый день действительно существует, они достигнутце:m в его поиске после порядка..(N вопросов.Но как Алисе и Бобу задать вопрос !А 8 (х)? Опишем, как им это сделать, действуя на любое одно и:з состояний вычислительного ба:шсаjx).Сначала Алиса выполняетJx)JO)а затем посылаетn-> Jx)Jfл(x)),(6.188)+ 1 кубиюв Бобу.
Боб яьmолняетJx)JfA(x)) ~ (-1)fл(х)Лfв(х)[х)lfл(х)).(6.189)Эrо преобразонание, очевюtно, унитарно, и вы можете легко проверить,что Боб может осуществить его, обраmвшись к своему оракулу. Тенерь, каки требовалось, фазовый множитеш, передJx)равен ( -1 )fлв(х), по в другомрегистре нродолжает храниться [!А (х )), что будет портить коt·ерентностьсуперпозиции значений х. Боб не может удалить этот регистр, но это можетсделать Алиса. Тогда Боб посъmастn+ 1 кубитов обратно Алисе, а она ещераэ консультируется со своим оракулом, чтобы выполн11ть(6.190)Обменявшись2(n + 1)кубитами, они завершmш один вопрос 113 !Ав оракулу и, таким образом, могут выполнить одну итерацию Гравера.1-I. Burhman, et.
ai., Quantum vs. Classica/ Communicatiotr and Cotnputatюn, ln Pror:eeding.roftlle 30lh Annual АСМ Symposium ofTneory oj Computing, АСМ Pre:o~s, 1998; quant-ph/9802040.16.8. ПОИСК В РАСПРЬДЕЛFННОЙ БАЗЕ ДАННЫХ349Допустим, например, что Алиса и Боб знают, что имеется только однавзаимоприемлемая 11:ата, но у них пет априорной информации о том, что это:\а ;:(ень. После вримерно ~ .JN итераций, требующих обменяться всегоQ"' ~/N · 2(log N+ 1)(6 191)кубитами, Алиса выполняет измерение, нолучая удобную i\Юу с вероятностью, близкой к единице.Таким обра1ом, по крайней мере в этом частном с;Iучае, обмен0(/NlogN) кубитами так же хорош, как и обмен O(N) классическимибитами.
По-видимому, нужно бьiТIJ осторожнее в интерпретации гранип;ыХоле во, которая явно утверждает, что кубит имеет не большую способностьпереносить информацию, чем бит!Если Алисе и .Dобу 1аранее неизвестно, ско:Iько имеется подходящихдат,ro они тем не менее могут вьшолнип. поиск Гранера (как мы отмечалив § 6.4.5) и с разумной вероятностью найти решение. С помощью 2 · log Nбиrов классического сообщения они могут проверить, действительно линайденная цата устраивает их обоих.6.8.1.C.lOЖIIOCTЬ КВаНТОВОЙ СВЯ1ИВ более общем виде можно nре,IJ.ставить, что каждый из несколькихучастников обладает п-биrовым входом; им необходимо вычислить функцию, зависящую от всех входов, с тем, чтобы се значение в конце концовста.1о известно одному из них.
Какой минимальный объем сообщений необходим для вычисления функции (детерминировапноrо или вероятностного)? Хорошо изученный раздел классической теории сложности, которомуа.цресуется этот вопрос, наэывается сложJюстью связи. То, что :мы установ~mи выше, является кnадратичной границей между квантовой и к.;шсси{Iеской СJЮЖНОСТЯМИ СВЯЗИ ДЛЯ ЧRС11ЮГО К.Л3СС3 функций двух участНИКОВ.!!омимо перехода от обмена классическими битами к обмену кубитами сущсствуюr другие интересные пуrи обобщения классической сложности связи.
Например, предположим, что участники делят некоторое заранееподготовленнос запутанное состояние (пары Белла ИlПf многокомпонентное .запутыван:ие) и могут использовать е1'0 паряду с классической свя1ью,чтобы выполнить вычисление функции. Вновь непосредствеюю не очевидно, что разделенное запутывание упростит задачу, так как само по себеоно еще не nозволяет участникам об~t:енивап.ся классическими сообщепи-ГЛАВА 6350ям:и. По оказывается, что запутЬJвание оказывает nомощь, по крайней меренебольшую 1 .В последнее время анализ сложности связи ПOIIy.'IЯpeH среди теоретиков в области сложности, но эта диcциrL'lliHa пока еще не представляетсязанимающей важное положение в практической технике связи.
Возможно,зто удивите.'IЬНО, принимая во внимание важность зффективного распределения вычисmпельной нагрузки в параллельных вычислениях, которыестали обычным делом. Более тоrо, похоже, что в реальной жизни практически вся связь может рассматриваться как форма дистанционных вычислений. На са.чом деле мне не нужно получать llCC биты, дошедшие до меняпо телефонной mшии, особеила потому, что я скорее всего запомню тольконесколько битов информации~ имеющих отношение к звонку в ближайшембудущем (фи..1ьм, на который мырешюш сходить).
Как менее прозанчсскнйпрнмер, нам на ЗеШJе может быть необходимо связа•ъся с роботом в глубоком космосе, чтобы проинструюировать, выходиТ!. лн ему на орбиту вокругудаленной звездной системы. Так как ширина полосы предельно оrраничена, то мы хотели бы вычИС..'IИТЬ правильный ответ на ДА/НЕТ -вопрос«Выходить ли на орбиту?>) с помощью минимального обмена информациеймежду Землей и роботом.Возможно, будущая цивилизация будет использовать известное квадратичное разде;~енис между классической и квантовой сложностью связи,обмениваясь, скорее, кубитами, чем битами, со своей фJiотилней космических сил. А возможно, будет найдено экспоненциальное разделение, покрайней мере в определенных ситуациях, чrо существенно повысило быстимуи для развития необходимой технологии квантовой связи.6.9.ПериодичностьПроблема Саймона до сих пор является единственным примером, в котором мы нашли зкспоненциадьное разделение между скоростью квантового алторитма и скоростью соответствующего классического алгоритма.
Ал~горитм Саймона использует квантовый параJШелизм~ чтобы ускорить поискпериода функции. Его успех вдохновляет нас искать друтие кваlffОвые алгоритмы, предназначенные для отыскания друrих разновидностей периода.1R. Cleve, et. а!., Quantum Entanglement and the Communication Complexity oi the InnerProduct J<unction, Lect.
Notes Comput. Sci.., 1509, 61-74 (1998), quant:-ph/9708019; Н. Buhrman,et al, ... Complexity, Phy•. Rev., А60, 2737-2741 (1998), quant-ph/9710054.6.9. IIЕРИОДИЧIЮСТЬСаймонизучал"(Z2 )n Для этойпериодические351функции,примимающиезначенияцели мощным инструментом служилоп-битовое преобразопание Адамара Н(~<).
Если вместо этого мы хотим изучать периодическиефункции, примимающие значения вZ2 ",то инструментом сопоставимойсилы будет (дискретное) иреобразование Фурье.Урок задачи Саймона в том. что, хотя поиск иrолок в стоге сена можетбыть 1рудным, отыскание периодически распределенных иголок в стоге сена может ока.1аться rораздо проще.
Например, если мы рассеиваем фотонна периодическом массиве иголок, он нероятнее всего рассеется вO!I:HOMизиреимущественных направлений, в котором удовлетворяется условие брэгговского отражения. Эти иреимущественные направления зависят от расстояния между иголками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
