Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Лов К. Гровер
(Lov K. Grover) ${ }^{1}$
Квантовая механика дает возможность ускорить процесс поиска среди неупорядоченных данных. Например, представим себе телефонную книгу, в которой содержится $N$ фамилий, расположенных совершенно произвольным образом. Чтобы найти чей-либо телефон с вероятностью большей чем $50 \%$, любой классический алгоритм (как детерминистический, так и вероятностный) потребует обращения к базе данных как минимум $0.5 N$ раз. Квантово-механическая система может находиться в суперпозиции состояний и одновременно проверять множество имен. При надлежащем задании программы поиска вычисления искомого состояния на каждом этапе усиливают друг друга, в то время как остальные интерферируют случайным образом. В результате нужный телефонный номер может быть найден лишь за $O(\sqrt{N})$ обращений к базе данных.
