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.
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.
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.
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.
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.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution D on Boolean functions, the probability an algorithm equipped with τc classical and τq quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most νD⋅(2τc+2τq+1)2, where νD captures the average (over D) fraction of preimages of 1. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution D. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.