Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 61

Одна возможностьпредставляет собой исnользование rой же нормы, что и в предыдущем об­суж,1ении точности. Тогда расстоянием между матрица"иетсяIIU - Wll.UнWявля­Еще одна естественная топалогня связана с внутреннимпроизведением(WIU)=tr wtu(6.104)·0.2. КВАНТОВЫF. СХЕМЫ319(еслиU и W являi-отся N х N -матриuами. то это в точности обычное внуr­2рею-Jее произведение И CN , В КОТОром U рассматривается как ~7V 2 -компо­НСНТПЫЙ вектор). Тогда мы можем опредеJПiть квадрат расстояния междуматрицами какIIU- Wll'=(U- W/U- W).(6.

105).д;ля анализа сложности подходит нрактически любая разумная топология.Решающим моментом является то, что, имея любой универсальныйнабор венпшей, мы можем подойти на расстояние Е к любому же..чаемомупреобразованию, действующему на фиксированное количество кубитов, ис­пользуя квантовую схему, размер которой ограничен сверху полиномиаль­но по t- 1. Следовательно, один универсальный кванrовый компьютер мо­жет моделировать друтой с точностью Е и не хуже, ч-ем с полиномиальнымпоt:-1фактором замедления.

Теперь нам уже понятно: чтобы иметь высо­кую вероятность получения правильного ответа при выпо!шении квантовойсхемы размера Т, необходимо обеснеч:ить выполнение каждого кванrовоговен1ЮlЯ с точностью порядка т- 1 . Следовательно, если вы имеете семей­.ство квантовых схем полиномиашJноrо размера, которые выпо 1няет вашквантовый компьютер, 10 я. могу изобрести семейство схем поJUiномиаль­нот"О размера, коrорые выполняет моя машина и с приемлемой точностыоэмупирует вашу.Почему схема poly(c 1 )-рюмера цожет досшчь данного k-кубитовогопреобразованняUв пределах расстояния Е? Мы знаем, например, что поло­жительные ценые степени типичного k-кубитовоrо eiA ШIО'IНЫ на 2k-mpe{ еiЛА}. Область тора в пределах расстояния Е до любой заданной rочкиимеет объем порядка 6 2 "'. Следоватет.но, с помощью (eiA)n rrpи нскотором целом n порядка Е-~"' мы можем асимптотичес:ки (при достаточно малом Е) достичь любого преобразования {ei>.A} с точностт,ю не хуже Е.

Намтакже известно! что, испо.1ьзуя схемы фиксированного размера (независи­мого от Е), мы можем получить преобразовання { е'А. }, ще Аа образуютлинейную оболочху полной алгебры Ли И(2•). Тогда тахже с полиноми­альной сходимостью мы можем аппроксимировать шобое ехр ( i Е о: а А а),акак в уравнении(6.87).В принциле мы способны добиться гораздо лучшего результа:rа, дости­гая желаемого k-кубитового унитарного преобразования с точностью не ху­же Е с помощью только poly ( Iog(' ··· 1 )) квантовых вентилей.

Так как коли­чество схем размера Т, которые мы можем построить, действуя наkкуби­тов, ')ксш.шенциал:ьно по 1'. а схемы заполняют[) (2k) примерно однородно,Г.1АВА 6320то до.-:тжна существовать схема размера Т, достигающая в t1peдeJ1ax расстоя­ния порядка е т любой точки в U(2k). Однако зrо можетоказаться труднойвычислите;1ьной задачейклассическим способом разработать схему, экс­-поненциально близко подходящую к унитарному преобра:юваиию, которогомы пытаемся достичь.

Поэmму бьmо бы нечестно опираться на зту болееэффективную конструкцию в асимптотическом анализе квантовой сложно­сти.6.3.Некоторые квантовые алгоритмыf BQ Р,Хотя мы по-прежнему не н состоянии показать, что ВР Рсуществует триразличиямеждуподхода,коrорымвозможностямиможнопоследовать, чюбыклассическихиквантовыхн.·'lучитькомпьюте­ров.(1)Неэкспоненциалъное ускорение. Мы можем найти кванmвые алго­ритмы, которые заметно быстрее лучших классических_ а.1горитмов,по не экспопенциально быстрее. Эrи аш'Оритмы не проливают свет наобщеприНЯJУЮ классификапию сложности. Ноorrnдемонстрируют ха­рактер разделения между задачами, которые могут выполнять клас­сические и квантовые компьютеры.

Ilримср: гроверовское квантовоеускорение поиска в неструктурированной базе данных.(2)«Релятивизированвое» эксповсвциальвое ускорение. Мы можемрассмотреть проблему анал~а содержимого «квантового черно!П ящи­ка>>. Ящик выпо;шяет аpn·onнеизвестное унитарное преобразованис.Мы можем приплuвить для него входные данные и измерить СП) ре­зультат; наша задача- определить,что /'Слает ящик. Оказывается воз­можным доказать, что существуют кванmвые ящики (специалисты потеории вычислений называют их оракуЛами 1), обладающие следую­щим свойством: за1ружая ящик квантовыми суперпозициями, мо:жноу:шать, что находится внутри него, с эк.споненцuаJtьным ускорением посравнению с тем, как много .времени приптось бы потратить,ccJrnбынам были разрешены только классические входные данные.

Специа­лист по теории вычислений ска:зал бы, чrо ВРР1- BQP«относи­тельно оракула>>. Пример: саймоновское экспоненциалыюе квантовоеускорение отыскания периода функции1<<2в1>>.Термин «Оракул» означает, чrо ящик отве•1ает на воnрос lieмf'iJишю; то есть время, за­трачивае"-юе па его рабо1)', не включается в анализ сложности.6.3. НЕКОТОРЫЕ КВАНТОВЫЕ АЛГОРИТМЫ(3)321ЭкспонепцnЗJJьпое ускорение д.тя «nо-видимому» трудных задач.Мы може;м продс:монС1рИJХ)Вать квантовый а.lПUритм, решающий в те­чение полиномиальною времени задачу, которая с Юlассической точкизрения выглядит сложной, то сстъ сер1.езно подозревается (хотя и не;~оказано), что 'та задача не нринадлежит ВРР. Пример: алгоритмфакгорюации Шара.1.Проблема Дойча.Мы обсудим "римеры из всех трех 1/ОДХО·дов. Но 1\ЛЯ нача.тrа разомнемся, вспомнив пример простого квантовогоалгоритма, который нреднарите.1ьно обсуждался в разделе1.5:алоритмДойча для различения между постоянной и сбалансированной фунщиямиf: {0, 1} __, {0, 1}.

Наи предоставлен квантовый черный ящик, вычисJIЯЮ·щийf (х); то есть приводящий в 11ействие 1\ВухкубитоJЮе унитарное прсоб-разование(6.106)которое инвертируетвторой кубит, если !(первый кубит) ~ 1. Наша:~адачасостоит в том, чтобы определить, выполняется ли f(O) = !(1). Если мыограничены <<классическими>> входными .~анными [О) и [1), то, чтобы полу­чиiъ ответ, нам необходимо обратип~ся к ящику l(важ)\ы (х___;О их- 1).По если нам позволено ввести коп~рснтную сунерпозицию этих щшассиче­ских» состояний,mдостаточно одного раза.Квантоnой схемой, решающей эту проблему (обсуждавшуюся в разде­ле1.5),является[О)1 н]-l{н} Н3мерсние[1)~~ ..~·-·Здес~о Н обошачает преобразова:ние Адамаран: [х)->_1.L:< -1)XYfy)J2y(6.1 07)ИJIИН[О) __, ~([О)f [1)),~([О)-[1));[1)->(6.108)ГЛАВА 6322то есть Н представляет собой2х 2-матрицу(6.!09)Схема иреобразует входIO)I1)-<JO)I1) в~(JO)+ 11))(10) -11))_.

H(-1)/(o)IO)_. Н [r-t)f(O)+ (-1)!(1)Jl)](Jo)-11))+ r-1)/(1)] Jo)+ [(-1)f(O)- (-1)f(l)] ll)} ~(JO)-11)).(6.110)Тогда при измерении первого кубита с вероятностью единица будет поду­чен результат JO), если f(O) =единнпа- резупътат 11), есJШf(1) (постоянная функция), и с вероятностьюf(O) т f(J) (сбалансированная функция).Квантовый компьюrер обпадает иреимуществом пере}{ классическимкомпьютером,посколькуонможет привлечьквантовый парамелизм.Так как мы вводим суперпозицию состояний IO) и J1), выход чувствите­лен к обоим значениям J(O) и !(1), даже сели мы обратилпсь к ящикутолько один раз.2. ПРQбJiема Дойча- Йожы.Рассмотрим теперь некоmрые обобще­ния проблемы Дойча.

По-прежнему будем предполагать, что нам нужноана,.;жзироватъ квантовый черный ящик («квантовый оракул»). Но в надеж­.~е улнать что-нибудь о сложности мы будем представлять, что имеем се­мейство черных ящиков с персменным размером входа. Нас интересует,как время, необходимое для определения того, что происходит внутри ящи­ка, зависит от размера входа (где «время» изм~ряется тем, сколько раз мыобращаемся к ящику с вопросом).В задаче Дойча- Йожы нам предоставлен квантовый черный ящик,коmрый вычиспяет функцию, преобразуяJ:{0,1}n-<nбитов в один:{0,] },причем у нас есть все основания полагать, что(6.ll\)f-постоянная[J(x)=сдля всех х] и:ш сбалансированная [f(x) ~О дпя ровно половины возмож­ных значений входа].

Мы должны решить проблему принятия решения:является лиfпостоянной иJШ сбалансированной?6.3. НI:::КОТОРЫЕ КВАНТОВЫЕ АЛГОРИТМЫ323Фактически, используя '!)' же схему, что и ддя решения проблемы Дой­ча (по с х, расширенным от одного до n битов), мы также можем решитьи Э'!)' проблему, обращаясь к ящику только один раз. Заметим, что если nвснпшей Адамара нараJшельно применяются кnкубитам(6.112)то п~кубитовое состояние преобразуется как(6.113)где х, у представляют п-битовые строки, ах· у обозначает побиттюеAND(или скалярное произведение по модуню два):(6.114)Действуя на вхо11(IO) )"11),схема преобразует его следующим образом:(6.115)Теперь вычислим сумму2n-11"2Есдиf-L (-J)f(x)(-l)xy.(6.116)х=Опостоянная функция, то эта сумма равна(6.117)ГЛАВА 6324она обращается в ну.~ь.

за искJrючепием случая, когда у: ____О. Следовательно,при измерении п-битового выходного регистра с вероятностью единица бу­дет нолучен результатто при уIY=О) ~(10) )".Но еслифункцияfсбалансирована,- О сумма ( 6.116) становится равной2"-12~L (-1)f(x) =О(6.118)х=О[поско,ты<у пOJIOIIинa слагаемых равны ( 1 1), а друтая половина - ( -1)].Следовательно, вероятностr, получения результата измерения IY = О) равнанулю.Мы приходим к выводу, что квантовому оракулу достаточно одно1'0 во­проса, чтобы соLOO%уверенностью раз.1нчить постоянную и сбалансиро­ванную функции. Результат измерения у =О означает, чтолюбой друr ой результатf -постоянi-шя,сбалансированная.Итак, квантовое вычисление изящно решает эту задачу, но действи­тельно ли это трудная проблема с К.lассической rочки зрения? Ограничи­ваясь вводом классических состоянийlx),"ы можем задаватr, вонрос ора­кулу неолнократно, всякий раз выбирая вrюд х случайным образом (безвозврата).

Как то:rыrо будут получены различные ответы на два ра1лнчныхвопроса, "ы определим, что функция сбалансирована (не постоянная). НоecJrи функция фактически является постоянной, мы не будем уверены в том,что это действите.::Iьно так, ло тех пор нока не предложим 2n-l+1 вопро­сов, получая всякий раз один и тот же ответ. В противоположв.ость этомуквантовое вычисление дает определенный ответ всего лишь в один при­ем. В этом смысле(ec;mмы требуем абсолютной определенности) класси­ческое вычисление требует экспоненциального потогда как квантовое вычисление- nет,nколичества вопросов,следовательно, можно говорить обэкспоненциальном усюорении.Но может быть неразумно требовать абсоиютной определенности отклассического вычисSiсния (в частности, так как любой реальный компью­тер подвержен ошибка..м, то и квантовый комнъютер также будет не спо­собен достигать абсолютной надежности).