Эффективные алгоритмы поиска в словаре

Аннотации

Аннотация

Рассматривается задача поиска элемента в словаре. В последние десятилетия были предложены различные подходы к решению этой задачи: классические и квантовые алгоритмы.

Представлены два алгоритма: гибридный классический квантовый алгоритм, который основан на алгоритме поиска Гровера, и «чистый» квантовый алгоритм, основанный на квантовом методе отпечатков. Оба алгоритма работают с высокой вероятностью получения правильного результата и с квадратичным ускорением по сравнению с классическими алгоритмами. Алгоритмы авторов гораздо эффективнее используют память с точки зрения количества используемых кубитов по сравнению с ранее известными квантовыми алгоритмами.