[МУЗЫКА]
[МУЗЫКА] Здравствуйте.
Добро пожаловать на пятую неделю курса «Квантовые вычисления».
В этом модуле мы разберем очень важный и общий результат,
полученный в 1996 году Ловом Гровером.
[БЕЗ_ЗВУКА] Алгоритм Гровера
предназначен для поиска записи, в не отсортированной базе данных.
Это как если бы вам нужно было бы найти в телефонном справочнике
фамилию по номеру телефона.
Телефонные справочники отсортированы по фамилиям, а не по телефонам,
поэтому поиск фамилии, когда вы знаете только номер телефона,
может оказаться очень трудоемкой задачей.
В наихудшем случае вам придется просмотреть весь справочник,
прежде чем вы найдете интересующую вас запись.
«Поиск, не отсортированный в базе данных» — это просто
одна из формулировок задачи поиска прообраза некоторой функции.
Вам известно значение функции
f(x) = y,
и нужно найти x,
который дает это значение y при применении функции.
Умение решать задачи такого рода естественным образом
ведет к умению решать любые задачи из класса NP, в которых,
как вы помните, у нас есть эффективная процедура проверки решения.
Когда нам дали какое-то решение, мы можем вычислить функцию и
сверить полученный результат с требуемым результатом,
но если решения у нас нет, и у нас есть только требуемый результат, то
нам надо вычислить обратную функцию, что в некоторых задачах оказывается сложным.
Например, в известной всем задаче коммивояжера,
нам нужно в некотором графе найти гамильтонов путь,
имеющий длину меньше какого-то заданного значения B.
Имея какой-то конкретный путь для проверки, мы можем легко посчитать его
длину, и сравнить ее со значением B — меньше она или нет.
Если же нам известно только вот это значение B,
а путь неизвестен, то поиск такого пути становится сложной задачей.
Это как вычисление обратной функции от значения B на графе.
Существование эффективного решения задачи коммивояжера — вопрос открытый,
в том числе для квантового компьютера.
Но если мы представим функцию f в виде «черного ящика»,
анализировать устройство которого мы не можем,
то и для классического, и для квантового случаев мы можем предъявить
оптимальный алгоритм решения задачи и проанализировать его сложность.
В классическом случае нам подходит любая стратегия перебора.
Если, например,
мы ищем запись в телефонном справочнике, мы можем просто просматривать подряд,
или по какой-то стратегии фамилии в телефонном справочнике,
и сравнивать телефонные номера напротив этой фамилии с эталоном.
При емкости телефонного справочника N записей,
в среднем нам потребуется O(N) операций сравнения телефонных номеров.
Удивительно, но для квантового компьютера существует более эффективный алгоритм.
И это — алгоритм Гровера.