Simulations And Designs About Quantum Algorithms

My thesis is divided into four chapters altogether. Chapter one, the Foreword , has introduced the elementary knowledge of the quantum computer. The research of the quantum computer stems from the study on reversible computer. Landauer points out that the computer generates heat because the information in the computer operation is erasured by operation, which will cause the increase of entropy of the system, therefore must release heat according to the view of thermodynamics in information, all operations are reversible except measurement in the quantum system, so that designing the new-type computer based on quantum mechanics should be considered. In addition, because of receiving the restriction of Einstein's impossible super light speed communicating theory, to improve speed of computer ,we must improve integrated level of chip constantly .on the one hand , this has caused unit's area to distribute heat increasing sharply ;on the other hand ,improvement of integrated level unavoidable to reduce the size to quantum mechanics reigns. so , the particle attribute of electron will play a very important role in calculating at this time. Research the quantum computing becomes inevitable. In the eyes of the scientist especially physicist, it is physics in calculatint, the physics law determines computing capability and the way of calculating. Even a scientist thinks the black hole is a computer with extremely fast speed. There are a lot of people that have already made remarkable contribution to the research of the quantum computer .in the realization IBM walks in the front , they have already produced the quantum computer that can operate simple calculation ,Shor and Grover have put forward the algorithms named after their own names respectively ,that is, the large number factorization algorithm and database search algorithm; in study of quantum computation complexity ,Yao proved that for any function computable in polynomial by a quantum Turing machine there exists a corresponding quantum circuit with polynomial size . Another important job of Shor is that he devolopped quantum error correcting. Though from view of realization and practical use ,there are a lot of difficulty in quantum computer, for example , coupling with surroundings, but they are not obstacle in principle Chapter two introducts Grover quantum search algorithms , and has analysed its advantages and disadvantages on the basis of David Biron's improvment,and put foreword the measure of improving.This chapter provide classification of quantum search algorithms and comparison of quantum search algorithms and traditional search algorithms at first. Tradition search algorithms endeavor to overcome the difficulty that search space is too large, and so too many routes neede to search, so it always try to reduce search space actually, certainly the cost on excavating structure information while utilizing structure information will take into consideration at the same time . And quantum algorithms'difficulty lies in that the solutions has a little amplitude.so algorithm must make amplitude to increase fastly.Grover quantum search algorithm achieve it's aim by increasing the amplitude of solutions at every iteration can be get a solution with a larger probability. Compared to the classical algorithm, Grover algorithm has gained a squarely speedup . Though it dose not speed up the algorithm like Shor algorithm , it correspond to a kind of important application, namely finding an element form a giving set , make this element meet a certain condition .Through analysing Grover algorithm , receives the following nature: amplitude of solutions is the function of iteration times, the best iteration times is the function of the number of solutions , the probability of gaining solutions only relate to number of solutions.David Biron has expanded Grover algorithm to be suitable for the situation that has arbitray initial state, we calculated relations between the amplitude of solutions the amplitude of non solutions and iteration times.Though expanded algorithm get squarely acceleratation ,it dose not work when the sum of amplitude of solutions is equal to that of non solutions', and also it can't change dispersed degree of the state , degradate to be less effective than classical random seletion when the dispersed degree is greater than 1 / N.aiming to the disadvantages,we have proposed improved method, and improve it in order to be suitable for solving the situation when the number of solutions is unknown . In chapter three , a simple quantum computer simulator was implemented .There is not quantum computer In the real meaning in the world now, to test and prove quantum algorithm a lot of people have designed simulation software to simulate quantum algorithm. In extant quantum simulator, some attempt to simulate using the quantum language ,which is very meaningful once real quantum computer come true ,because it can be planted to real quantum computer ;some imitate to specific hardwares , more simulator offer a graphic user's interface fore easy use .Through studying and comparing the simulator of the quantum computer in existence, according to the needs of my own , I use java language to realize the simulator of...