Grover′s quantum search algorithm utilizes the parallel properties of quantum mechanics,which has been studied and applied extensively because of its great search efficiency.The principle and performance of Grover′s quantum searching algorithm is researched,especially the quantum algorithm for finding the minimum of a database is deeply researched.Because the search number of the algorithm is high,an improved quantum algorithm which named double threshold for finding a maximum in a database is proposed.The conclusion that the search number of this algorithm is less than the original one through the simulation.The algorithm is applied in multi-user detection,experiment results show that the bit error rate performance of the algorithm is close to the optimal multi-user detection algorithm,and the complexity is less than the optimal one.
Grover′s quantum search algorithm utilizes the parallel properties of quantum mechanics,which has been studied and applied extensively because of its great search efficiency.The principle and performance of Grover′s quantum searching algorithm is researched,especially the quantum algorithm for finding the minimum of a database is deeply researched.Because the search number of the algorithm is high,an improved quantum algorithm which named double threshold for finding a maximum in a database is proposed.The conclusion that the search number of this algorithm is less than the original one through the simulation.The algorithm is applied in multi-user detection,experiment results show that the bit error rate performance of the algorithm is close to the optimal multi-user detection algorithm,and the complexity is less than the optimal one.
This paper illustrated the optimality of Grover quantum search algorithm, and simulated the number of iterations and the specific implementation steps of quantum search algorithm with QCL in Linux operating systems, then validated the time complexity of Grover's quantum searching algorithm is O(√(N)) while the algorithm's time complexity on classical computers is O(N). The Grover quantum search algorithm were shown to improve the performance significantly in the random database search problem. This conclusion was drawn from the simulation in the Linux operating systems adopted to quantum computation language. The present study highlighted the importance of high efficiency of the Grover quantum search algorithm to achieve the best possible performance in such cases. The existence of such efficiency is an outstanding advantage of quantum search algorithm over the conventional approach.
The classical optimal solution of CDMA multi-user detection is consistent with the optimization of a quadratic function, and to find the optimum is a NP hard problem. Reducing the complexity of optimum based on quantum parallel computation is a new trend of multi-user detection techniques. In this paper, we propose a scheme based on Grover's searching algorithm to find the optimum. We give the relationship of bit error rate against signal-to-noise and correlation coefficient by numerical simulation, and simply evaluate the computational complexity of our proposed scheme. The results show that our solution has almost the same performance to the classical optimal one, however, with low complexity
Finding a maximum or minimum is a fundamental building block in many mathematical models. Compared with classical algorithms, Durr, Hoyer's quantum algorithm (DHA) achieves quadratic speed. However, its key step, the quantum exponential searching algorithm (QESA), which is based on Grover algorithm, is not a sure-success algorithm. Meanwhile, quantum circuits encounter the gate decomposition problem due to variation of the scale of data. In this paper, we propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, we provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when we can exactly estimate the ratio of the number of solutions M and the searched space N, our method can improve the successful probability close to 100%. Furthermore, compared with DHA, our algorithm shows an advantage in complexity with large databases and in the gate complexity of constructing oracles. Experiments have been executed on an IBM superconducting processor with two qubits, and a practical problem of finding the minimum from Titanic passengers' age was numerically simulated. Both showed that our optimized maximum or minimum performs more efficiently compared with DHA. Our algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum.
With the growth of Grover's quantum search algorithms,it is applied to practical uses gradually.By introducing of the fun-damental principles of quantum parallelism and quantum algorithms and studying the improved Grover searching algorithm,a quantum mechanical algorithm is given to solve optimal loading problem,and is proved its time complexity to O().As to the optimal loading problem,two methods are given to resolve the problem respectively,that is,greed algorithm in the classic computers and quantum al-gorithm.The time complexity of this two algorithms is gained.In the conclusion,quantum algorithms solve many search problems more efficiently than classic algorithms.
The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.
At present, the scale of quantum computers in the real sense is still small, and quantum simulation has become one of the important ways of quantum theory research, grover quantum search algorithm is suitable for the search problem of disordered database. Firstly, according to the implementation principle of Grover algorithm and Boolean logic relationship, the design idea of multi-objective Oracle is analyzed, based on IBMQ quantum cloud platform, the quantum circuit of Grover algorithm with multi-objective items is simulated. Based on the characteristics of Grover algorithm and the simulation process of quantum gate, the action of multiple identical quantum gates is combined to reduce the update times of probability amplitude and improve the simulation efficiency. The libquantum quantum simulator is used for experiments and the target item is successfully searched, which proves the feasibility of the optimization method and provides reference for the simulation and optimization of other quantum algorithms.