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