Квантовый поиск в словаре на основе функции отпечатков

Рассмотрена задача поиска элемента в словаре. В последние десятилетия были предложены различные подходы к решению этой проблемы, в том числе классические и квантовые алгоритмы. Метод квантового усиления амплитуды, который лежит в основе хорошо известного алгоритма Гровера, квадратично ускоряет процесс поиска.
Мы представляем новый подход к поиску элемента $w$ длиной $m$ в словаре $V$ размером $n$, основанный на квантовой функции отпечатков. Наш алгоритм имеет запросную сложность $O(\sqrt{n})$ и использует $O(\log n + \log m)$ кубитов, тогда как алгоритмы, представленные в работах других авторов, используют $O(\log n + m)$ кубитов.