Привет, Хаброжители! Мы недавно сдали в типографию книгу Криса Бернхарда «Квантовые вычисления для настоящих айтишников». Здесь решили поделиться отрывком из книги «Алгоритм Гровера и поиск данных»
Мы вступаем в эпоху больших данных. Эффективный поиск в гигантских массивах данных в настоящее время является животрепещущей задачей для многих крупных компаний. Алгоритм Гровера теоретически способен ускорить поиск данных.
Свой алгоритм Лов Гровер изобрел в 1996 году. Подобно алгоритмам Дойча и Саймона, он имеет более высокую скорость выполнения, по сравнению с классическими алгоритмами с точки зрения запроса сложности. Однако мы не сможем реализовать действующий алгоритм поиска данных, не имея оракулов, которым могли бы задавать свои вопросы. Мы должны сконструировать алгоритм, выполняющий работу оракула. Но прежде чем начать говорить о реализации алгоритма Гровера, посмотрим, что он делает и как.
Алгоритм Гровера
Представьте, что перед вами четыре игральные карты. Они повернуты рубашками вверх. Вы знаете, что одна из них — туз червей и вам нужно найти ее. Сколько карт придется перевернуть, пока вы не узнаете, где лежит туз червей?
Если вам повезет, вы найдете искомую карту с первой же попытки, если не повезет, вы можете перевернуть три карты, и ни одна из них не будет тузом червей. В худшем случае, перевернув три карты, вы будете точно знать, что последняя карта — это искомый туз червей. Итак, мы можем узнать, где находится туз, перевернув от одной до трех карт. В среднем понадобится перевернуть 2,25 карты.
Это одна из задач, которые решает алгоритм Гровера. Перед началом описания алгоритма переформулируем задачу. У нас есть четыре двоичные последовательности: 00, 01, 10 и 11. У нас есть функция f, которая возвращает 0 для трех из этих последовательностей и 1 — для четвертой последовательности. Нам нужно найти двоичную последовательность, соответствующую выходному значению 1. Например, мы можем получить такие результаты: f(00) = 0, f(01) = 0, f(10) = 1 и f(11) = 0. Теперь задача состоит в том, чтобы выяснить, сколько раз следует вычислить функцию, чтобы получить результат f(10) = 1. Здесь мы просто переформулировали задачу, заменив игральные карты функциями, поэтому ответ на этот вопрос уже известен: как и прежде, в среднем потребуется вычислить функцию 2,25 раза.
Как и во всех алгоритмах с запросом сложности мы сконструируем оракула — вентиль, инкапсулирующий функцию. Оракул для нашего примера, где имеется всего четыре двоичные последовательности, показан на рис. 9.1.
Цепь для алгоритма Гровера изображена на рис. 9.2.
Алгоритм выполняет два шага. На первом переворачивается знак амплитуды вероятности, связанной с местом, которое мы пытаемся отыскать. Второй усиливает эту амплитуду вероятности. Посмотрим, как цепь делает это.
После передачи через вентили Адамара два верхних кубита получают состояние
а нижний кубит имеет состояние
Объединенное состояние можно записать как
Затем кубиты проходят через вентиль F. Он инвертирует 0 и 1 в третьем кубите в местоположение, которое мы пытаемся найти. Для нашего случая f(10) = 1 мы получим
Это можно переписать как
В результате мы получаем два верхних кубита, не спутанных с нижним, но амплитуда вероятности
поменяет знак, что указывает на искомое местоположение.Если на этом шаге измерить два верхних кубита, мы получим одно из четырех местоположений, при этом все четыре возможных ответа равновероятны. Нам нужно сделать еще один шаг — усилить амплитуду вероятности. Усиление амплитуды осуществляется путем переворачивания последовательности чисел относительно их среднего. Если число выше среднего, оно переворачивается и становится ниже среднего. Если число ниже среднего, оно переворачивается и становится выше среднего. В каждом случае удаленность от среднего сохраняется. Для иллюстрации используем четыре числа: 1, 1, 1 и –1. Их сумма равна 2, а среднее равно 2/4, или 1/2. Затем начинаем перебирать числа в последовательности. Первое число — это 1. Оно выше среднего на 1/2. После переворота оно должно стать на 1/2 ниже среднего. В данном случае оно превратится в 0. Число –1 ниже среднего на 3/2. После переворота оно должно стать на 3/2 выше среднего, то есть превратиться в 2.
В настоящее время два верхних кубита имеют состояние
Перевернув амплитуды относительно среднего, получаем
.Выполнив измерение, мы определенно получим 10, то есть переворот относительно среднего дает нам именно то, что нужно. Мы должны лишь убедиться в существовании вентиля или, что то же самое, ортогональной матрицы, описывающей переворот относительно среднего. Такая матрица существует:
В результате воздействия вентиля на два верхних кубита мы получаем
В этом примере, где у нас всего два кубита, мы должны использовать оракула только один раз. Нам достаточно задать единственный вопрос. Для случая n = 2 алгоритм Гровера дает точный ответ после единственного вопроса, тогда как в классическом случае в среднем требуется задать 2,25 вопроса.
Эта идея распространяется на случай произвольного числа n кубитов. Мы начинаем с того, что переворачиваем знак амплитуды вероятности, которая соответствует искомому местоположению. Затем выполняем переворот относительно среднего. Однако в этом случае усиление амплитуды происходит не так существенно, как в ситуации с двумя кубитами. Возьмем для примера восемь чисел, семь из которых 1 и одно –1. Их сумма равна 6, а среднее равно 6/8. После переворота относительно среднего числа 1 превратится в 1/2, а число –1 превратится в 10/4. Как следствие, при наличии трех кубитов, измерив один кубит после усиления амплитуды, мы получим искомое местоположение с большей вероятностью, чем другие. Проблема в том, что существует значительная вероятность получить неверный ответ. Нам нужна более высокая вероятность получения верного ответа — нужно еще больше усилить амплитуду перед измерением. Решение состоит в том, чтобы передать все кубиты обратно через цепь. Мы снова переворачиваем знак амплитуды вероятности, связанной с искомым местоположением, и снова выполняем переворот относительно среднего.
Рассмотрим обобщенный случай. Нам нужно найти нечто, находящееся в одном из m возможных местоположений. Чтобы найти его классическим способом, в худшем случае мы должны задать m – 1 вопросов. Число вопросов растет пропорционально m. Гровер рассчитал формулу, которая определяет, сколько раз нужно использовать его цепь, чтобы получить максимальную вероятность правильного ответа. Число, которое дает эта формула, растет пропорционально
. Это квадратичное ускорение.Применения алгоритма Гровера
С реализацией алгоритма связано несколько проблем. Во-первых, квадратичное ускорение оценивается относительно запроса сложности. Чтобы использовать оракула, его нужно создать, и если не отнестись с к этой задаче с должной осторожностью, число шагов, выполняемых оракулом, перевесит число шагов, которое экономит алгоритм, и в результате алгоритм станет медленнее, а не быстрее классического. Другая проблема состоит в том, что, определяя ускорение, мы предполагаем неупорядоченность набора данных. Если набор данных имеет определенную структуру, часто можно найти классический алгоритм, использующий эту структуру и отыскивающий решение намного быстрее. Последняя проблема связана с ускорением. Квадратичное ускорение — не что иное, как экспоненциальное ускорение, которое мы наблюдали в других алгоритмах. Можно ли добиться большего? Давайте рассмотрим эти проблемы.
Обе проблемы, связанные с реализацией оракула и наличием структуры в наборе данных, обоснованы и показывают, что в большинстве случаев алгоритм Гровера не имеет практического применения для поиска в базе данных. Но в некоторых ситуациях наличие структуры в данных делает возможным создание оракула, действующего с высокой эффективностью. В таких ситуациях алгоритм может обогнать классические алгоритмы. Ответ на вопрос о возможности добиться большего успеха уже был дан. Доказано, что алгоритм Гровера является оптимальным. Не существует квантового алгоритма, способного решить задачу с более чем квадратичным ускорением. Квадратичное ускорение, хотя и не такое впечатляющее, как экспоненциальное, все еще дает определенные выгоды. При работе с большими наборами данных любое ускорение может оказаться ценным.
Вероятно, главное применение алгоритм Гровера найдет не для поиска, как было представлено выше, а для его вариаций. В частности, может пригодиться идея усиления амплитуды.
Мы рассмотрели всего несколько алгоритмов, но алгоритмы Шора и Гровера считаются наиболее важными. Существует множество других алгоритмов, основанных на идеях, заложенных в этих двух.1 А теперь переключим наше внимание с квантовых алгоритмов на другие сферы применения квантовых вычислений.
