Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2

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

PDF-файл Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 63 Квантовые вычисления (53151): Книга - 7 семестрДж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2: Квантовые вычисления - PDF, страница 63 (53151) - СтудИзба2019-09-18СтудИзба

Описание файла

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ьек­тов, среди которых ровно один маркирован.

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее