ФЭНДОМ


Алгоритм Гровера — квантовый алгоритм быстрого поиска в неупорядоченной базе данных. Для N записей поиск осуществляется за время O(N1/2) с использованием O(logN) места. Алгоритм был разработан Л. Гровером в 1996 году.

При существующих технических средствах одним из наиболее быстрых алгоритмов поиска является линейный поиск, требующий O(N) времени. Алгоритм Гровера, использующий возможности квантовых компьютеров, позволяет решить задачу поиска за время O(N1/2). Доказано, что он является наиболее быстрым квантовым алгоритмом для поиска в неупорядоченной базе данных. Также доказано, что не существует классических алгоритмов той же эффективности. Алгоритм Гровера обеспечивает квадратичный прирост скорости, в то время как некоторые другие квантовые алгоритмы, например, алгоритм факторизации Шора, дают экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами. Но несмотря на это, квадратичный прирост значителен при достаточно больших значениях N.

Применение Править

Хотя основным назначением алгоритма Гровера принято считать поиск в базе данных, более точно его можно охарактеризовать как «обращение функции». Грубо говоря, имея функцию y=f(x), которая может быть вычислена с использованием квантового компьютера, алгоритм Гровера позволяет вычислить x, зная y. Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных.

Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.

СсылкиПравить

См. также Править



Квантовые алгоритмы
Алгоритм Шора | Алгоритм Гровера | Алгоритм Дойча — Джоза | Задача Фейнмана



<center> Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Алгоритм Гровера. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики