ABSTRACT
Grover’s algorithm, which is based on the quantum parallel computation, can find the desired value precisely with iterations in a large unsorted database which contains elements. However, to find the desired value in the database, any classical algorithm would need at least steps.
Low error rate and reduced complexity of communications system are two pursuing targets of all detection techniques.Particularly in recent years, quantum algorithms, based on the parallel quantum computation, simplify some classic information systems which are not easy to solve on the background of classic system. In order to achieve the goal, a much deeper investigation of the signal detection applications with Grover’s algorithm in the MIMO-OFDM system has been developed. At last,we expect to acquire a good compromise between the performance and the computational complexity.
Firstly, the basic principle of Grover’s algorithm is introduced in the thesis and the number of iterations is simulated in classic computer when searching the single solution with Grover’s algorithm.Then the problems of searching multi-objective solution with the Grover’s algorithm are analyzed.And an improved algorithm which can find the object with the successful probability at least 98.01% with one step when the fraction of marked items is greater than 1/4 is proposed for its shortcomings.
Secondly, the MIMO-OFDM systems and several classic signal detection algorithms are introduced, then their detection performances and time complexities are simulated, analyzed and compared.
Finally, a signal detection program based on Grover algorithm of MIMO-OFDM system is designed.Through the MATLAB simulation,the Grover algorithm,its improved algorithm and the traditional detection algorithm are made a comprehensive analysis and comparison in the detection performance and the time complexity.We expect that the improved algorithm can reduce the complexity of the traditional optimum detection algorithm efficiently ,while achieving the same performance.
Keywords:Quantum Computation;Grover Algorithm;The Improved Algorithm;
MIMO-OFDM; Signal Detection