Задача Дойча-Джозы

Loading...

Из курса от партнера Saint Petersburg State University

Квантовые вычисления (Quantum computing)

27 оценки

Saint Petersburg State University

Квантовые вычисления (Quantum computing)

27 оценки

О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.

Из урока

Квантовый компьютер и квантовые алгоритмы

В этом модуле мы рассмотрим прототип квантового компьютера на двух фотонах и несколько простых квантовых алгоритмов.

Задача Дойча-Джозы8:33

Задача Бернштейна-Вазирани3:18

Задача Саймона9:08

Познакомьтесь с преподавателями

Сысоев Сергей Сергеевич
кандидат физико-математических наук
Кафедра системного программирования

[МУЗЫКА]

[МУЗЫКА] Разберем еще несколько простых задач,

которые позволят нам сформировать представление о том,

что такое типичный квантовый алгоритм.

Итак, задача Дойча-Джозы.

В некоторых учебниках переводят как Дойча-Йожи.

[БЕЗ СЛОВ] У

нас есть функция f,

которая отображает

n-битную строку в 1 бит.

И нам известно, что функция f — либо константа,

либо количество x,

на которых f дает 0, равно количеству x,

[БЕЗ СЛОВ] на которых f дает 1.

То есть функция либо константа, либо в таком вот смысле сбалансирована.

В классическом случае наихудший вариант для нас это если f — константа.

Да, вопрос к задаче звучит: является ли f константой?

И если она действительно является константой,

то для того чтобы достоверно доказать это,

нам потребуется вот

столько вызовов оракула — обращений к черному ящику.

Ну, мы опять посмотрим, помогут ли нам квантовые вычисления сделать это лучше.

Квантовый алгоритм выглядит почти так же, как для задачи Дойча.

То есть, на самом деле, совершенно так же.

[БЕЗ СЛОВ]

[БЕЗ СЛОВ] Только

входной регистр у нас уже состоит из n кубит,

ну а здесь у нас по-прежнему 1 кубит.

Таким образом, преобразование Адамара здесь n-кубитное,

ну и здесь оно тоже n-кубитное.

И, как вы видите, оператор оракула опять вызывается один раз.

Давайте посмотрим.

Итак, у нас есть такое

состояние, которое

после действия оператора Адамара превращается по формуле,

которую мы доказывали в прошлый раз, в такую вот сумму.

[БЕЗ СЛОВ]

[БЕЗ СЛОВ]

[БЕЗ СЛОВ] И на эту

сумму мы должны подействовать

нашим оператором Uf.

[БЕЗ СЛОВ]

[БЕЗ СЛОВ]

[БЕЗ СЛОВ]

[БЕЗ СЛОВ] [БЕЗ

СЛОВ] [БЕЗ

СЛОВ] Мы помним,

как оператор Uf действует на слагаемые такого вида.

Он просто домножает их на −1 в степени f(x).

Теперь нас будет интересовать содержание первого вот этого регистра.

Давайте его выпишем.

Давайте его выпишем для двух случаев: пусть f равно константе.

Тогда −1 в степени f(x) мы можем вынести из под знака суммы.

Получится −1 в степени f(x).

2 в степени n/2.

∑ по x от 0 это

2 в степени (n − 1) x, что,

как мы помним,

равно преобразованию Адамара от такого вот вектора, состоящего полностью из 0.

И, соответственно, еще раз применив преобразование Адамара,

мы получим просто этот вектор.

Вектор, состоящий из n нулей, то есть кодируемый строкой из n нулей.

И второй случай, когда f сбалансирована,

[БЕЗ СЛОВ] −1 в степени f(x) мы уже вынести не можем,

но мы можем разбить эту сумму на две суммы.

∑ по x таким, что f(x) = 0.

Когда f(x) = 0, −1 в степени f(x) = 1,

и тут у нас просто будут x.

Еще у нас будет ∑ по x таким,

что f(x) = 1, и −1 в степени 1 = −1,

и поэтому здесь мы пишем «−».

Получается разность таких сумм,

причем количество членов в этих суммах равно.

И когда мы будем применять преобразование Адамара,

для любого х, когда мы применяем преобразование Адамара,

мы будем получать строку вида 0 в степени n.

То есть там будут какие-то еще строки,

будет 2 в степени (n −

1) строк такого вида плюс какие-то еще строки,

и здесь тоже будет 2 в степени (n − 1) строк,

и это 0 в степени n + что-то еще.

И вот эти вот строки 0 в степени n вычтутся друг из друга.

То есть в нашей окончательной сумме

после преобразования Адамара не останется строк

вида 0 в степени n, то есть строк, кодируемых n-нулями.

И таким образом, когда f сбалансирована,

мы не сможем в результате измерения получить строку такого вида.

Поэтому, когда мы применили эту схему и провели измерение,

если мы получаем строку вида n-нулей, то мы знаем, что f у нас — константа.

Если получаем какую-то любую другую строку, то мы понимаем,

что f — сбалансирована, опять же за одно применение

квантового оракула.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play