О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Задача Дойча
Loading...
From the course by Санкт-Петербургский государственный университет
Квантовые вычисления (Quantum computing)
14 ratings
From the lesson
Квантовый компьютер и квантовые алгоритмы
В этом модуле мы рассмотрим прототип квантового компьютера на двух фотонах и несколько простых квантовых алгоритмов.
Meet the Instructors
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] Здравствуйте!
Добро пожаловать на третью неделю курса «Квантовые вычисления».
В этом модуле мы разберем несколько простых квантовых алгоритмов,
которые показывают преимущество квантовых вычислений над классическими.
Кроме того, мы рассмотрим простейший прототип квантового компьютера на двух
кубитах, реализующий алгоритм Дэвида Дойча,
первый квантовый алгоритм, разработанный для модели квантовых вычислений.
Итак, задача Дойча.
Предположим, у нас есть функция f,
отображающая один бит в один бит.
Функция f реализована в виде черного ящика.
Черный ящик — это метафора, говорящая о том,
что механизм действия функции f нам неизвестен.
Мы не можем залезть внутрь черного ящика и посмотреть, как она устроена.
Мы можем только получать значения функции f от разных параметров,
обращаясь к черному ящику как к оракулу.
Всего функций такого типа четыре штуки — две константы 0 и 1,
и две сбалансированных — это тождественная операция и NOT.
Вопрос задачи Дойча звучит следующим образом: является ли функция f константой?
При этом черный ящик почему-то работает очень медленно.
Один вызов функции f он осуществляет 24 часа.
Сколько нам нужно времени, для того чтобы ответить на вопрос в задаче Дойча?
Ясно, что для
классических вычислений одного вызова функции f нам будет недостаточно.
Нам нужно попробовать функцию f от обоих возможных значений ее параметров.
Посмотрим, помогут ли квантовые вычисления справиться нам с этой задачей быстрее.
Мы помним, что эволюция квантовой системы унитарна, и следовательно,
вместо функции f в черном ящике должен быть спрятан какой-то унитарный оператор.
Назовем его Uf, который в отличие от функции f должен быть обратимым,
иначе он не будет унитарным.
Пользуясь функцией f, мы можем определить оператор Uf, например, следующим образом.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] Плюсик
в кружочке, здесь операция XOR.
Он принимает на вход два кубита,
x — входной кубит, в котором будет храниться параметр функции f,
и y — регистр, куда мы будем складывать наши значения,
причем складывать не просто так, а через операцию XOR.
Видно, что этот оператор переставляет базисные вектора,
не склеивает никакие два разных базисных вектора, и следовательно, он унитарен.
Кроме того, оператор Uf несет всю информацию о функции f.
Если мы положим во второй регистр 0,
то для любых значений
x мы будем получать значение f(x) во втором регистре.
Определив оператор Uf таким образом, мы получаем еще одно полезное свойство.
Давайте посмотрим, как он будет действовать на состояние такого вида.
[БЕЗ_ЗВУКА] Это
у нас равно,
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] что
в свою очередь равно,
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] потому
что когда f(x) = 1,
здесь будет 1 − 0, когда f(x) = 0, здесь будет 0 − 1.
Таким образом, для такого состояния оператор Uf не меняет значение регистра
y и поворачивает регистр x в пространстве аргумента, если f(x) = 1.
Давайте посмотрим, как будут выглядеть матрицы и
схемы наших квантовых оракулов для разных значений функции f(x).
Вообще говоря, функций f(x) у нас четыре разных вида,
а унитарных однокубитных операторов их,
разумеется, гораздо больше, их бесконечное количество.
Но давайте посмотрим, как выглядят те операторы, которые реализуют функцию f.
Итак, четыре вида функции f.
f(x) = 0, f(x) =
1, [БЕЗ_ЗВУКА]
f(x) = x,
f(x) = не x.
Когда f(x) = 0,
здесь у нас всегда будет y складываться с нулем,
и любой вектор xy будет отображаться просто вектор xy,
то есть это у нас тождественный оператор, матрица 4 x 4 тождественного оператора.
И на схеме это просто отсутствие применения каких-либо операторов.
Когда f(x) = 1, давайте посмотрим.
Четыре разных возможных входа.
[БЕЗ_ЗВУКА] |
00 > отображается в | 01 >,
| 01 > отображается в | 00 >,
| 10 > отображается в | 11 >,
и | 11 > отображается в | 10 >.
Матрица выглядит вот так.
Здесь и
оператор NOT и нули — это подматрицы 2 x 2.
И на схеме это будет выглядеть как применение гейта NOT к
каждому из кубитов.
Так, теперь более интересная ситуация.
f(x) = x, тождественное отображение.
Давайте опять выпишем.
[БЕЗ_ЗВУКА] Итак,
| 00 > отображается
в | 00 >, поскольку f(x) = 0.
| 01 > отображается в | 01 >,
потому что f(0) опять же равно нулю.
А уже | 10 > отображается в | 11 >,
и | 11 > соответственно в | 10 >.
И это уже знакомый нам оператор CNOT, который мы
договорились на схеме изображать
вот таким образом.
И функция f(x) = не x.
Опять мы выписываем четыре
возможных входа,
все наши базисные вектора, и смотрим, во что они отображаются.
f(0) уже равно 1, и поэтому | 00 > отображается в | 01 >.
| 01 > соответственно в | 00 >.
А уже f(1) = 0, и эти два вектора
не меняются.
Матрица похожа на CNOT,
но такой перевернутый CNOT.
Гейт NOT включается в том случае, если контрольный кубит у нас равен нулю.
Как это изобразить на схеме?
Очень просто.
Мы сначала поворачиваем контрольный кубит,
чтобы из нуля он стал единичкой.
Вызываем обычный CNOT.
И потом обратно поворачиваем контрольный кубит,
чтобы он не менялся.
Итак, вот все возможные операторы и все возможные схемы,
закрытые от нас в чёрном ящике в квантовом случае.
Алгоритм, решающий задачу Дойча, выглядит следующим образом.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА]
Здесь у
нас производится измерение,
на вход в регистр x мы подаём нолик, в регистр y — единичку.
Здесь, в этом большом блоке,
оператор Uf — один из тех операторов, которые мы рисовали с вами на доске.
И как видите,
он в отличие от классического случая вызывается всего один раз.
Давайте посмотрим, к чему это приведёт.
Итак, у нас на вход подаётся состояние |0> |1>,
и мы применяем к нему
оператор Адамара.
[БЕЗ_ЗВУКА] После
чего мы применяем оператор Uf.
Давайте для начала раскроем первую скобку.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] И
мы с вами помним,
как наш оператор Uf, определённый в том виде,
в котором мы его определили, действует на такого рода состояния.
Он домножает
наше состояние на минус единицу в степени f(x).
[БЕЗ_ЗВУКА] Можем
сразу привести подобные слагаемые.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА]
Оператор Uf мы применили,
и остаётся нам оператор Адамара на вот этом первом кубике.
Прежде чем его применять, давайте посмотрим,
как выглядит это состояние в двух разных случаях.
Если f — константа и f
сбалансирована.
Если f равно константа, то коэффициенты при нуле и единице одинаковые,
и мы можем вынести их за скобки.
Это будет состояние плюсик,
которое под действием оператора
Адамара превращается в состояние ноль.
И, соответственно, если f сбалансировано, то f(0) не равно f(1),
и у нас после вынесения
−1 — если потребуется — будет состояние минусик.
То есть будет либо состояние минус, либо минус минус.
И под действием оператора Адамара мы получим единичку.
Таким образом, для разных типов функции f
мы получим разные значения во входном регистре.
И в результате измерения, если мы получаем нолик, то мы узнаём что f — константа,
если мы получаем единичку, то мы узнаём, что f сбалансирована.
При одном единственном вызове оракула.
[БЕЗ_ЗВУКА]
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
