О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Вступление
Loading...
來自 Saint Petersburg State University 的課程
Квантовые вычисления (Quantum computing)
26 個評分
與講師見面
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] Здравствуйте.
Добро пожаловать на пятую неделю курса «Квантовые вычисления».
В этом модуле мы разберем очень важный и общий результат,
полученный в 1996 году Ловом Гровером.
[БЕЗ_ЗВУКА] Алгоритм Гровера
предназначен для поиска записи, в не отсортированной базе данных.
Это как если бы вам нужно было бы найти в телефонном справочнике
фамилию по номеру телефона.
Телефонные справочники отсортированы по фамилиям, а не по телефонам,
поэтому поиск фамилии, когда вы знаете только номер телефона,
может оказаться очень трудоемкой задачей.
В наихудшем случае вам придется просмотреть весь справочник,
прежде чем вы найдете интересующую вас запись.
«Поиск, не отсортированный в базе данных» — это просто
одна из формулировок задачи поиска прообраза некоторой функции.
Вам известно значение функции
f(x) = y,
и нужно найти x,
который дает это значение y при применении функции.
Умение решать задачи такого рода естественным образом
ведет к умению решать любые задачи из класса NP, в которых,
как вы помните, у нас есть эффективная процедура проверки решения.
Когда нам дали какое-то решение, мы можем вычислить функцию и
сверить полученный результат с требуемым результатом,
но если решения у нас нет, и у нас есть только требуемый результат, то
нам надо вычислить обратную функцию, что в некоторых задачах оказывается сложным.
Например, в известной всем задаче коммивояжера,
нам нужно в некотором графе найти гамильтонов путь,
имеющий длину меньше какого-то заданного значения B.
Имея какой-то конкретный путь для проверки, мы можем легко посчитать его
длину, и сравнить ее со значением B — меньше она или нет.
Если же нам известно только вот это значение B,
а путь неизвестен, то поиск такого пути становится сложной задачей.
Это как вычисление обратной функции от значения B на графе.
Существование эффективного решения задачи коммивояжера — вопрос открытый,
в том числе для квантового компьютера.
Но если мы представим функцию f в виде «черного ящика»,
анализировать устройство которого мы не можем,
то и для классического, и для квантового случаев мы можем предъявить
оптимальный алгоритм решения задачи и проанализировать его сложность.
В классическом случае нам подходит любая стратегия перебора.
Если, например,
мы ищем запись в телефонном справочнике, мы можем просто просматривать подряд,
или по какой-то стратегии фамилии в телефонном справочнике,
и сравнивать телефонные номера напротив этой фамилии с эталоном.
При емкости телефонного справочника N записей,
в среднем нам потребуется O(N) операций сравнения телефонных номеров.
Удивительно, но для квантового компьютера существует более эффективный алгоритм.
И это — алгоритм Гровера.
