О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Оптимальность алгоритма Гровера. Часть 1
Loading...
Del curso dictado por Saint Petersburg State University
Квантовые вычисления (Quantum computing)
20 calificaciones
De la lección
Алгоритм Гровера и границы квантовых вычислений
Conoce a los instructores
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] [МУЗЫКА] В случае,
если про функцию fω ничего не известно, кроме того,
что у нее существует единственная особая точка ω, на которой функция равна 1,
алгоритм Гровера является оптимальным для поиска этой особой точки,
существующей в настоящее время в модели квантовых вычислений.
Для того чтобы доказать это, введем некоторые обозначения.
Итак, ω — это искомый вектор, наша особая точка функции f.
Оператор U(ω,
t) — это некий альтернативный квантовый оператор,
который вызывает функцию оператор Uω t раз.
И мы предполагаем, что этот оператор лучше, чем итерация Гровера.
То есть нам потребуется меньшее количество итераций вот такого оператора,
для того чтобы получить нашу искомую точку.
При этом итерации не такие, как в Гровере.
Они не должны быть одинаковы на каждом шаге, при каждом вызове Uω.
[БЕЗ СЛОВ] ψ(0) — это начальный вектор,
с которого мы начинаем применение оператора.
И ψ(t) — это состояние системы после t вызовов оракула.
[БЕЗ СЛОВ] И
еще одно обозначение: T — это количество итераций, которое нам требуется,
то есть количество вызовов нашего оракула, для того чтобы мы пришли в искомую точку.
Тогда мы можем заметить, что множество векторов
ψ(T) (давайте
пометим: ψω(T)) формирует ортонормированный
базис в нашем пространстве, если мы берем разные значения ω.
То есть если ω у нас варьируется от 0
до N − 1,
то операторы ψω(T), полученные применением нашего алгоритма,
будут формировать ортонормированный базис в пространстве.
Мы с вами докажем, что существует некоторый единичный вектор φ,
[БЕЗ СЛОВ] такой,
что выполняется для этого вектора следующее двойное неравенство.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] Это
сумма по квадратам разностей всех наших базисных векторов,
полученных с помощью альтернативного Гроверу алгоритма, минус вектор φ.
И это ≥...
[БЕЗ СЛОВ] Мы найдем такой вектор,
для которого выполняется следующее двойное неравенство.
Поскольку крайние части неравенства не зависят от ω, то мы сможем заключить,
что 4T² ≥ 2N
− o (малое) от N,
и отсюда, что количество итераций, необходимых нашему алгоритму,
будет эквивалентно O (большое) от √N.
Так же, как и в алгоритме Гровера.
Начнем мы с вами с правой части неравенства.
Доказываем правую часть неравенства.
Посмотрим на вот эту сумму квадратов норм.
[БЕЗ СЛОВ] Каждая
из них — это квадрат разности.
Давайте его разложим.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] [БЕЗ
СЛОВ] Поскольку
скалярное произведение у нас несимметрично,
то получается вместо удвоенной такой суммы
скалярное произведение ψω на φ и скалярное произведение φ на ψω.
Это у нас единичные вектора.
Квадрат их норм равен 1.
Соответственно, тут сумма из N единиц, тут сумма из N единиц.
Здесь получается 2N.
Что это за скалярное произведение?
Давайте запишем разложение вектора φ по базису ψω.
Он имеет в этом базисе какие-то координаты.
Мы просто их обозначим: x0, ..., x(N − 1).
Тогда скалярное произведение
вектора φ на k-тый базисный вектор — это просто его k-тая координата.
Получается, что всё это у нас равно здесь,
как мы уже посчитали,
2N − ∑
[БЕЗ СЛОВ] по
всем i от 0 до N − 1
(xi* + xi)
И теперь
мы можем для каждого xi-того
записать его в таком виде,
то есть выделить вещественную и мнимую часть.
Получается, что это у нас сумма
[БЕЗ СЛОВ] [БЕЗ
СЛОВ] такого вида.
Мы с вами доказали вот это равенство,
и теперь нам нужно в этой формуле оценить
сумму ai-тых и сравнить ее с √N.
Для этого нам потребуется следующая лемма.
Итак, лемма.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
Мы докажем,
что вот это неравенство выполняется для любого набора значений Ct.
Как мы это сделаем?
Давайте мы возьмем левую часть неравенства
[БЕЗ СЛОВ]
и прибавим к нему некоторое положительное значение.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] Здесь суммирование
идет по набору индексов s и t, то есть такое двойное суммирование,
и каждый член суммы положителен, поскольку это квадрат, хоть и квадрат разности.
И теперь раскроем скобки.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] Здесь у нас получается попарное
произведение всех возможных C с разными индексами,
поэтому мы запишем вот так.
Тоже получается суммирование двойное, по двойному индексу.
[БЕЗ СЛОВ] Здесь
получатся две
такие суммы
квадратов.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] И
минус удвоенные
произведения Cs на Ct по всем [БЕЗ
СЛОВ] индексам s и t.
[БЕЗ СЛОВ] Оно удвоенное,
но здесь мы делим на 2, то есть домножаем на 1/2, поэтому получается 1.
Эти два члена уходят,
и остается у нас, поскольку мы можем взаимозаменять индексы s и t,
остается у нас просто T на ∑,
[БЕЗ СЛОВ]
остается у нас правая часть неравенства.
Таким образом, мы из левой части неравенства получили правую,
добавив какое-то положительное значение.
Вспомним, что наш вектор φ — единичный.
[БЕЗ СЛОВ] Мы
уже записывали обозначение для его координат,
поэтому мы можем это скалярное произведение расписать следующим образом.
[БЕЗ СЛОВ]
...что = ∑ по всем i
ai² + bi²
= 1.
Получается, что ∑ ai² ≤ 1.
Поскольку bi² — они тоже положительные числа.
Домножим обе части неравенства на N.
Получается: N больше либо равно N ∑ai²
по всем i.
Здесь мы применяем нашу лемму.
Это ≥ ∑ ai-тых по всем i в квадрате,
поскольку суммирование у нас от 0 до N − 1, то есть у нас N индексов.
Таким образом, получается, что ∑ ai-тых ≤ √N.
Мы можем подставить это сюда и получить правую часть нашего неравенства.
[БЕЗ_ЗВУКА]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
