Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 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изиреимущественных направлений, в котором удовлетворяется условие брэг­говского отражения. Эти иреимущественные направления зависят от рас­стояния между иголками.