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