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