О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Всегда-ли квантовый компьютер лучше классического?
Loading...
Do curso por Saint Petersburg State University
Квантовые вычисления (Quantum computing)
20 classificações
Na lição
Алгоритм Гровера и границы квантовых вычислений
Conheça os instrutores
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] До
настоящего момента, мы с вами рассматривали задачи,
на которых квантовый компьютер показывает себя лучше, чем классический.
У вас может создаться впечатление, что это всегда так.
К сожалению, нет.
Давайте рассмотрим функцию такого вида,
которая отображает n-битное число в один бит.
Это предикаты.
И для каждой из таких функций мы определим строку,
длиной 2ⁿ,
[БЕЗ_СЛОВ] в которой
каждый бит равен значению функции от номера этого бита.
[БЕЗ_СЛОВ] [БЕЗ_СЛОВ]
Оракул Uf для функции такого вида
мы определяли с вами так.
[БЕЗ_СЛОВ] Или
мы можем записать,
используя наше новое обозначение,
[БЕЗ_СЛОВ]
[БЕЗ_СЛОВ] [БЕЗ_СЛОВ]
когда xi у нас = 1,
этот член обращается в 0, и у нас получается i > | y + 1.
Когда xi = 0, этот член обращается в 0,
а здесь у нас получается 1, и i > | y >.
То есть эта запись эквивалентна предыдущей.
Получается, что после T вызовов оракула
мы имеем при каждом из исходов полином степени
T от xi, определенных нами здесь.
Введем обозначение x̃i = 1 − 2xi.
И рассмотрим функцию Parity (по-русски
— четность), принимающую на вход строки (x̃) и
берущую Πx̃i по всем i.
Функция равна либо 1, либо −1.
1 — если функция четная, и −1 — если нет.
Четная функция в том случае, если она выдает значение 1 ровно для
половины своих входных параметров.
И вопрос, задача, которую мы будем решать.
У нас на входе есть квантовый оракул для какой-то функции f,
черный ящик, квантовый черный ящик, и нам нужно,
используя этот квантовый оракул, определить четность функции f.
Классическая сложность этой задачи 2ⁿ.
Если у нас функция реализована в виде черного ящика, нам надо запустить ее для
всех значений параметров, посмотреть, что она выдает, и посчитать четность.
Ну, допустим, мы для квантовых вычислений придумали алгоритм,
количество итераций которого, допустим, меньше, чем N / 2.
Тогда, после запуска нашего алгоритма при каждом из исходов,
при каждом векторе, базисном векторе нашего пространства,
будет полином в степени T от x̃i.
И, соответственно, вероятность каждого из исходов
— это будет этот полином в квадрате, то есть P²ᵀ.
2T у нас меньше, чем N.
И давайте мы пометим как-то исходы,
которые мы будем интерпретировать как признак четности функции,
мы назовем эти исходы even,
и при них будет P²ᵀ, который мы будем называть P even.
Давайте рассмотрим сумму такого вида.
сумму по всем возможным функциям,
четность функции, выданная нашим устройством,
умноженная на реальную четность функции.
[БЕЗ_СЛОВ] И
эту сумму мы можем разложить по индексу i,
то есть мы можем выделить какой-то конкретный индекс j.
[БЕЗ_СЛОВ] В
первую часть суммы мы вынесем все слагаемые,
для которых xⱼ = 1, и, соответственно,
у нас будет эта часть суммы с плюсом,
[БЕЗ_СЛОВ] и
вторая часть суммы,
на которых xⱼ = −1, она будет с минусом.
[БЕЗ_СЛОВ]
[БЕЗ_СЛОВ] [БЕЗ_СЛОВ]
[БЕЗ_СЛОВ] Поскольку у нас
сумма по всем функциям, то есть функции, в которых для индекса j они дают 1,
есть функции, для которых для индекса j они дают −1.
Многочлен P even состоит из одночленов.
Степень каждого из этих одночленов не больше, чем 2T,
а 2T, мы помним, что это меньше, чем N.
Соответственно, для каждого из одночленов мы можем подобрать индекс j таким образом,
чтобы он не присутствовал в этом одночлене.
И тогда для этого одночлена вот это разбиение суммы (разность
этих сумм) будет равна нулю.
Поскольку мы можем сделать такое разбиение для любого из одночленов,
то получается, что вся эта сумма равна нулю.
Таким образом, предпосылка, что T у нас меньше, чем N / 2,
количество итераций меньше, чем классическая сложность пополам,
приводит к тому, что вот такая вот Σ = 0.
Эта Σ = 0, и мы можем ее расписать,
разбить на две суммы следующим образом: Σ по x̃ таким,
что x̃ — четное, для них это Π = 1,
и получится, что эта вероятность,
выданная нашим устройством,
просто умноженная на 1,
− Σ по x̃ таким, что x̃ — нечетное.
Для них Π = −1, поэтому здесь минус, и вероятность,
выданная нашим устройством, что функция — четная.
Это равно нулю, соответственно, эти две суммы равны,
и получается, что вероятность, получить ответ «четное»,
выданное нашим устройством, равна для четной и нечетной функции.
Таким образом, мы имеем полную неопределенность относительно четности
функций, если количество итераций у нас меньше, чем N / 2.
Таким образом, мы показали, что квантовые вычисления для вот
этой задачи не дают ускорения даже хотя бы в два раза.
На этом оптимистичном результате, мы заканчиваем курс «Квантовые вычисления».
Спасибо вам, что добрались со мной до этого момента.
Путь, я знаю, был тяжелым.
Мы будем рады видеть вас на других курсах Санкт-Петербургского государственного
университета.
Спасибо за внимание.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
