Задача Саймона

Loading...

From the course by Saint Petersburg State University

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

20 оценки

Saint Petersburg State University

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

20 оценки

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

From the lesson

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

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

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

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

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

Meet the Instructors

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

[МУЗЫКА]

[МУЗЫКА] Задача Саймона.

Как обычно в этом модуле у нас есть функция f, спрятанная в черном ящике.

На этот раз она отображает n бит в n бит.

И нам известно про функцию f,

что существует единственное такое число a, такое,

что f(x) = f(y) только в том случае,

в том и только в том случае, когда x

= y ⊕ a.

И, как и водится в такого рода задачах, надо узнать число a.

В классическом случае это задача сложная.

Нам может потребоваться O от 2 в

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

В квантовом случае задача проще.

Алгоритм выглядит следующим образом.

У нас есть два регистра.

Мы подаем на них n кубитные нули.

К верхнему регистру,

регистру аргументов, применяем n кубитное преобразование Адамара.

После этого осуществляем вызов нашего оракула.

После этого мы меряем

второй регистр.

И применяем n кубитное преобразование Адамара к первому регистру.

После чего меряем его.

Давайте посмотрим, что нам даст выполнение этой схемы.

Итак, два регистра с n нулями |0⟩n |0⟩n.

Преобразование Адамара к старшему регистру, к регистру аргументов,

даст нам по нашей формуле для преобразования Адамара такую сумму.

[БЕЗ_ЗВУКА] Второй

регистр мы не трогали,

после чего мы применяем оператор qf, который поместит значение f(x)

в каждом члене этой суммы в зависимости от параметра x.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Ну, а таких иксов,

для которых мы имеем одинаковые f(x), на самом деле два: x и x ⊕ a.

Поэтому я могу объединить эти два икса в скобки, вынеся f(x).

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] И

по схеме у нас сейчас идет измерение второго регистра.

После того как мы померяем второй регистр, мы получим какое-то значение,

конкретное значение f(x) от какого-то конкретного x, назовем его x'.

То есть здесь у нас останется f(x').

А во входном регистре у нас останется x' + x' + a.

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

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

[БЕЗ_ЗВУКА] К

этому нам надо применить преобразование Адамара.

Давайте по очереди к первому, ко второму.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Так,

и надо аккуратно выписать коэффициенты.

Тут будет 1 / 2 в степени n + 1 / 2

везде.

Давайте объединим эти суммы,

поскольку счетчики у них одинаковые.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Давайте

посмотрим на степень этой (−1).

Просто раскроем скобки.

Это (−1) в степени x' •

y ⊕ a • y.

Пусть у нас

a • y ≠ 0.

Тогда степени этих (−1) в этой сумме будут разные,

и коэффициент при таком |y> будет равен нулю.

Соответственно, в этой нашей сумме после преобразования Адамара

и до измерения останутся только игреки, такие

что a • y = 0.

Это, конечно,

не дает нам за одно измерение получение числа a.

Нам нужно n линейно независимых игреков,

чтобы получить число a, решив систему уравнений.

Но тем не менее вместо сложности экспоненциальной от числа

n мы получаем O (n) вызовов

оракула для получения n разных линейно

независимых уравнений такого вида.

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

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

познакомились с общей структурой квантового алгоритма,

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

применить интересующую нас функцию и после этого каким-то образом

подготовить наше состояние к такому виду,

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

В принципе, для базового знакомства с материалом курса этого достаточно.

Тех же, кому интересно решение реальных практических задач с помощью квантового

компьютера, я жду на следующей неделе.

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

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

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

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

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

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