Алгоритм Гровера
Материал из Википедии — свободной энциклопедии
Алгоритм Гровера — это квантовый алгоритм быстрого поиска в неупорядоченной базе данных. Для N записей поиск осуществляется за время O(N1/2) с использованием O(logN) места. Алгоритм был разработан Л. Гровером в 1996 году.
При существующих технических средствах одним из наиболее быстрых алгоритмов поиска является линейный поиск, требующий O(N) времени. Алгоритм Гровера, использующий возможности квантовых компьютеров, позволяет решить задачу поиска за время O(N1/2). Доказано, что он является наиболее быстрым квантовым алгоритмом для поиска в неупорядоченной базе данных. Алгоритм Гровера обеспечивает квадратичный прирост скорости, в то время как некоторые другие квантовые алгоритмы, например, алгоритм факторизации Шора, дают экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами. Но несмотря на это, квадратичный прирост значителен при достаточно больших значениях N.
Как и другие алгоритмы для квантовых компьютеров, алгоритм Гровера вероятностный: он дает верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. (Примером детерминированного квантового алгоритма может служить алгоритм Дойча-Джоза, дающего верный ответ с единичной вероятностью).
[править] Применение
Хотя основным назначением алгоритма Гровера принято считать поиск в базе данных, более точно его можно охарактеризовать как «обращение функции». Грубо говоря, имея функцию y=f(x), которая может быть вычислена с использованием квантового компьютера, алгоритм Гровера позволяет вычислить x, зная y. Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных.
Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.
