In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Clanek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.
In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Clanek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.
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.
In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.
In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.
Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of algorithms.
Quantum computing is a young but intriguing field of science. It combines quantum mechanics with information theory and computer science to potentially solve certain formerly computationally expensive tasks more efficiently. Classical computers are based on bits that can take on the value zero or one. The values are distinguished by voltage differences in transistors. Quantum computers are instead based on quantum bits, or qubits, that are represented physically by something that exhibits quantum properties, like for example electrons. Qubits also take on the value zero or one, which could correspond to spin up and spin down of an electron. However, qubits can also be in a superposition state between the quantum states corresponding to the value zero and one. This property is what causes quantum computers to be able to outperform classical computers at certain tasks. One of these tasks is searching through an unstructured database. Whereas a classical computer in the worst case has to search through the whole database in order to find the sought element, i.e. the computation time is proportional to the size of the problem, it can be shown that a quantum computer can find the solution in a time proportional to the square root of the size of the problem. This report aims to illustrate the advantages of quantum computing by explicitly solving the classical Windows game Minesweeper, which can be reduced to a problem resembling the unstructured database search problem. It is shown that solving Minesweeper with a quantum algorithm gives a quadratic speedup compared to solving it with a classical algorithm. The report also covers introductory material to quantum mechanics, quantum gates, the particular quantum algorithm Grover's algorithm and complexity classes, which is necessary to grasp in order to understand how Minesweeper can be solved on a quantum computer.
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.