Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 61
Описание файла
PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 61 страницы из PDF
Одна возможностьпредставляет собой исnользование rой же нормы, что и в предыдущем обсуж,1ении точности. Тогда расстоянием между матрица"иетсяIIU - Wll.UнWявляЕще одна естественная топалогня связана с внутреннимпроизведением(WIU)=tr wtu(6.104)·0.2. КВАНТОВЫF. СХЕМЫ319(еслиU и W являi-отся N х N -матриuами. то это в точности обычное внуr2рею-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сния (в частности, так как любой реальный компьютер подвержен ошибка..м, то и квантовый комнъютер также будет не способен достигать абсолютной надежности).