М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 14
Текст из файла (страница 14)
Заметим, что в каждом письме Алиса посылает Бобу ц битов информации. Кроме того, в двн- 1.4. Квантовые алгоритмы 59 !0) !т) !чу2) !Фз) Т ! ФО) ! Ф1) рис. 1.20. Квантовая оома, реализующая обобщенный алгоритм дойче-Йыка. Провод с на- клонной чертой представляет набор из и кубитов по аналогии с общепринятыми техническими обозначениями.
Отдельные шаги алгоритма показалы иа рис. 1.20. Давайте проследим за состояииями по этой схеме. Входное состояние !Фс) =!0)э"!1) (1.46) похоже иа то, которое представлено формулой (1.41), ио здесь регистр запроса описывает состояиие и кубитов, каждый из которых приготовлен в состоянии ~0). После преобразования Адамара иад регистром запроса и примеиеиия эле- мента Адамара к регистру ответа мы имеем ее!О,Ц' (1.47) иом примере физическое расстояние используется для искусственного увеличевия затрат иа вычисление 7'(х), ио это ие обязательно в задаче общего вида, где 7"(х) сама по себе может быть сложной для вычисления.
Ебли бы Боб и Алиса могли обмениваться кубвчами, а ие только классическими битами, и если бы Боб согласился вычислять 7" (х) с помощью увитарного преобрэзоваиия Уу, то Алиса смогла бы достичь своей цели всего за один запрос к Бобу, используя описанный ниже алгоритм. Как и в алгоритме Дойча, Алиса имеет а-кубитовый регистр для храиеввя своего запроса и одиокубитовый регистр, который оиа предоставит Бобу для хранения ответа. Оиа начинает с приготовления своих регистров запроса и ответа в состоянии суперпозиции. Боб вычислит 7'(х), используя квантовый параллелизм, и оставит результат в регистре ответа. Затем Алиса создаст иитерфереицию состояний суперпозиции, используя преобразование Адамара иад регистром запроса, и закончит выполнением подходящего измереиия, чтобы определить, была ли функция постоянной или сбалансированной.
60 Глава 1. Введение и общий обзор Регистр запроса теперь содержит суперпозицию всех значений, а регистр ответа находится в равновзвешенной суперпозиции 0 и 1. Затем Боб вычисляет функцию У с помощью Уу: )х, у) -+ )х, у Е У(х)), что дает (1.48) 'Теперь у Алисы есть набор кубитов, в котором результат вычисления функции Боба сохранен в амплитуде суперпозиции. Далее она создает интерференцию членов суперпозиции, используя преобразование Адамара над регистром запроса. Чтобы определить результат преобразования Адамара, полезно сначала вычислить результат действия этого преобразования на состояние )х).
Рассматривая отдельно случаи х = 0 и х = 1, мы видим, что для одного кубита Н~х) = ~',,( — 1)*'~в)/~/2. Таким образом, 2„( — 1)*'"+ +*"*" ~ " ..) Более компактно это можно записать следующим образом: (1.50) где х. х представляет собой побитовое скалярное произведение х и х по модулю 2. Используя это выражение совместно с (1.48), можно вычислить фэ): (1.51) Теперь Алиса наблюдает регистр запроса.
Заметим, что амплитудой для состояния ~0)х" является 2 (-1)УОО/2". Рассмотрим два возможных случая— постоянная / и сбалансированная / — чтобы выяснить, что происходит. В случае, когда /(х) постоянна, амплитуда для ~0) э" равна +1 или -1 в зависимости от того, какое постоянное значение принимает функция. Поскольку рУз) имеет единичную длину, все остальные амплитуды должны быть нулевыми, и наблюдение даст нули для всех кубитов в регистре запроса.
Если / сбалансирована, то положительный и отрицательный вклады в амплитуду для ~0) х" взаимоуничтожаются, оставляя амплитуду нулевой, и измерение должно дать отличный от нуля результат хотя бы для одного кубнта в регистре запроса. Итак, если Алиса получит при измерении все нули, то функция постоянна; в противном случае функция сбалансирована. Ниже приведено краткое изложение алгоритма Дойча-йожа. Алгоритм Дойча-Йожа Вход. Черный ящик Уу выполняет преобразование )хну) -+ )х))у Э /(х)) для х Е О,...,2" — 1 и /(х) Е 0,1. Предполагается, что /(х) либо постоянна для всех значений х, либо сбалансирована, т.
е. равна 1 строго для половины всех возможных х и 0 для другой половины. 1.4. Квантовые алгоритмы 61 Выход. 0 тогда и только тогда, когда у постоянна. Время исполнения. Одно вычисление Уу. Всегда завершается успехом. Процедура. 1. !0)в"~1) инициализация состояния 2 *Йе,й" ~4 ~ )72 ] создание суперпозиции с использованием элементов Адамара 1.4.5 Классификация квантовых алгоритмов Алгоритм Дойча-Йожа демонстрируют, что квантовые компьютеры могут решать некоторые вычислительные задачи намного эффективнее классических компьютеров.
Однако, решаемая этим алгоритмом задача не имеет большого практического интереса. Существуют лн более интересные задачи, решение которых может быть получено с большей эффективностью при использованни квантовых алгоритмов? Каковы принципы, лежащие в основе таких алгоритмов? Каковы предельные ограничения на производительность квантового компьютера? вычисление функции у с использованием Уу 4.
-Е,п,ь-'с-;:-'-ьы~эф~~ ...., Э .. Адамара 5. — >г измерение для получения конечного результата з Мы показали, что квантовый компьютер может решать задачу Дойча путем однократного вычисления функции у в отличие от классического требования 2"/2+ 1 вычислений. Это выглядит впечатляюще, но нужно сделать несколько существенных оговорок. Во-первых, задача Дойча не особенно важна; у нее нет интересных приложений. Во-вторых, сравнение классических и квантовых алгоритмов в чем-то похоже на сравнение яблок с апельсинами, поскольку методы вычисления функции в обоих случаях очень разные. В-третьих, если Алисе разрешено использрвать вероятностный классический компьютер, то попросив Боба вычислить |(х) для нескольких случайно выбранных х, она может очень быстро определить с большой вероятностью, является ли У постоянной или сбалансированной.
Возможно, этот вероятностный сценарий более реалистичен, чем рассмотренный нами детерминированный сценарий. Однако, несмотря на эти оговорки, алгоритм Дойча-Йожа содержит в себе зачатки еще более впечатляющих квантовых алгоритмов, н это обьясняет попытку понять принципы, лежащие в основе его работы. Упражнение 1.1 (вероятностный классический алгоритм). Пусть задача состоит не в том, чтобы достоверно отличить постоянную функцию от сбэ лалсировэлной, а в том, чтобы сделать это с некоторой вероятностью ошибки е ( 1/2. Какова эффективность наилучшего классического алгоритма, решающе о такую з д чу? 62 Глава 1. Введение и общий обзор Говори в самых общих чертах, есть три класса квантовых алгоритмов, имеющих преимущество над известными классическими алгоритмами.
Во-первых, это класс алгоритмов, основанных на квантовой версии преобразования Фурье — инструменте, который широко используется и в классических алгоритмах. Примерами алгоритмов этого типа служат алгоритм Дойча-йожа, а также алгоритмы Шара для задач факторизации и вычисления дискретного логарифма. Второй класс алгоритмов — это квантовые авгорнтмы поиска.
Третий класс алгоритмов — квантовое моделирование, при котором квантовый компьютер используется для моделирования квантовой системы. Сейчас мы коротко опишем каждый кз этих классов алгоритмов, а затем суммируем то, что известно нли предполагается относительно производительности квантовых компьютеров. Квантповмв алгоритмы, основанные на преобразовании Фурье Дискретное преобразование Фурье обычно описывается как преобразование на- бора хо,...,хн 1 из Ф комплексных чисел в набор комплексных чисел ро,..., рл и определяемый следующим образом: г."ь и л-1 рь ьз — ~ ~ег О"~~х .
~/У,, (1.52) г -1 (я — ~~~ е~ йьуз )й). '~ го (1.53) Конечно, это преобразование широко применяется во многих отраслях знаний; задача, подвергнутая преобразованию Фурье, часто оказывается проще своего исходного варианта, что позволяет ее решить. Польза преобразования Фурье оказалась настолько велика, что была разработана замечательная обобщенная теория преобразований Фурье, выходящая далеко за рамки определения (1.52). Эта теория содержит некоторые технические идеи из теории представлений конечных групп, и мы не будем пытаться ее здесь описывать.
Важно то, что преобразование Адамара, используемое в алгоритме ДойчаЙожа, является примером этого обобщенного класса преобразований Фурье. Более того, во многих других важных квантовых алгоритмах также используется преобразование Фурье того или иного типа. Самые известные квантовые алгоритмы — быстрые алгоритмы Шара для задач факторизации и вычисления дискретного логарифма. Это два примера алгоритмов, которые основаны на преобразовании Фурье, определяемом в (1.52).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
