Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ФИЗИКА ЭЛЕМЕНТАРНЫХ ЧАСТИЦ И АТОМНОГО ЯДРА

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

F. Ablayev, Nailya Salikhova, Marat Ablayev, Farid Mansurovich Ablayev

Published Sep 24, 2025• 0 citations
OpenAlex

Abstract

We consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm, which implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work with a high probability of obtaining the correct result and with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.

Related papers

Efficient Dictionary Search Quantum Algorithms

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

Abstract In this paper, we consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm [1], that implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.

Physics of Particles and Nuclei•Aug 1, 2025•2 citations

Quantum search in a dictionary using fingerprinting function

Nailya Salikhova

The problem of searching for an element within a dictionary was considered. Over the past decades, various approaches, including classical and quantum algorithms, have been proposed to solve it. One possible solution is the method of quantum amplitude amplification, which underpins the well-known Grover algorithm and enables a quadratic speedup in the search process. In this article, a new approach to searching for an element w of length m in a dictionary V of size n with the use of the quantum fingerprinting function was introduced. The developed algorithm has a query complexity of O(√n) and requires O(logn+logm) qubits.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Apr 7, 2025•1 citation

Quantum search in a dictionary based on fingerprinting-hashing

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

In this work, we present a quantum query algorithm for searching a word of length $m$ in an unsorted dictionary of size $n$. The algorithm uses $O(\sqrt{n})$ queries (Grover operators), like previously known algorithms. What is new is that the algorithm is based on the quantum fingerprinting-hashing technique, which (a) provides a first level of amplitude amplification before applying the sequence of Grover amplitude amplification operators and (b) makes the algorithm more efficient in terms of memory use -- it requires $O(\log n + \log m)$ qubits. Note that previously developed algorithms by other researchers without hashing require $O(\log n + m)$ qubits.

arXiv:2412.11422•Dec 16, 2024•0 citations

Quantum Search for a Given Substring in the Text Using a Hashing Technique

Marat Ablayev, Nailya Salikhova

The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”. In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Jan 1, 2020•3 citations

Hybrid Classical–Quantum Text Search Based on Hashing

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover’s quantum search provides a quadratic speed-up in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical–quantum algorithm (hybrid random–quantum algorithm, to be more precise) that implements Grover’s search to find a given substring in a text. As expected, the algorithm works (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. What is new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.

arXiv:2311.01213•Mathematics•Jun 14, 2024•12 citations

Hybrid Quantum-classical Search Algorithms

Ansis Rosmanis

Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.

arXiv:2202.11443•ACM Transactions on Quantum Computing•Feb 16, 2024•23 citations
We consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm, which implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work with a high probability of obtaining the correct result and with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.
Abstract In this paper, we consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm [1], that implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.
The problem of searching for an element within a dictionary was considered. Over the past decades, various approaches, including classical and quantum algorithms, have been proposed to solve it. One possible solution is the method of quantum amplitude amplification, which underpins the well-known Grover algorithm and enables a quadratic speedup in the search process. In this article, a new approach to searching for an element w of length m in a dictionary V of size n with the use of the quantum fingerprinting function was introduced. The developed algorithm has a query complexity of O(√n) and requires O(logn+logm) qubits.
In this work, we present a quantum query algorithm for searching a word of length mmm in an unsorted dictionary of size nnn. The algorithm uses O(n)O(\sqrt{n})O(n​) queries (Grover operators), like previously known algorithms. What is new is that the algorithm is based on the quantum fingerprinting-hashing technique, which (a) provides a first level of amplitude amplification before applying the sequence of Grover amplitude amplification operators and (b) makes the algorithm more efficient in terms of memory use -- it requires O(log⁡n+log⁡m)O(\log n + \log m)O(logn+logm) qubits. Note that previously developed algorithms by other researchers without hashing require O(log⁡n+m)O(\log n + m)O(logn+m) qubits.
The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”. In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.
The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover’s quantum search provides a quadratic speed-up in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical–quantum algorithm (hybrid random–quantum algorithm, to be more precise) that implements Grover’s search to find a given substring in a text. As expected, the algorithm works (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. What is new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.