The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation
Hong-Tao Zhang^{1, 2}, Yong-Tao Dai^{1, 2}, Ling-Ying Tu^{1, 3, *}, Jun Shu^{1, 4}, Hong-Mei Xiong^{1, 2}, Yi-Fan Hu^{1, 2}
^{1}Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China
^{2}Department of Communication, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
^{3}Department of Electronic Information Engineering, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
^{4}Department of Automation, School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Email address:
To cite this article:
Hong-Tao Zhang, Yong-Tao Dai, Ling-Ying Tu, Jun Shu, Hong-Mei Xiong, Yi-Fan Hu. The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation.Communications.Vol.3, No. 2, 2015, pp. 42-48. doi: 10.11648/j.com.20150302.13
Abstract: This paper illustrated the optimality ofGrover 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 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.
Keywords: GroverQuantum Search Algorithm, Optimality, Time Complexity, Linux, QCL
1. Introduction
In 1996, Grover proposed the groundbreaking quantum search algorithm[1] and put forward that the application of quantum computation can search problems for unordered database which carried on two times of acceleration effect in 1997, and it realized the fact that the classical algorithm searching number reduced from N to.The intention of the algorithm[2] is to perform a unitary transform through the initial amplitude superposition, increasing the target of quantum probability amplitude, while reducing other non-target of quantum probability amplitude. The bigger the final goal of quantum probability amplitude is, the greater the searching (measuring) probability of the correct target is. In recent years, in order to improve the success rate of Grover quantum search algorithm, scientists continued to change the algorithm. In 2007, Li Sun et al[3] verified on Experiment 3 qubits Grover quantum search in quantum computation simulation program and achieved the nuclear magnetic resonance and the multiple quantum operator algebraic theory as the foundation, the multi qubit Grover quantum search algorithm of the NMR pulse sequence design method. In the same year, Hongyuan Ma et al[4,5] achieved the Grover quantum search algorithm in a thermal cavity. In 2009, Yudong Zhang et al [6,7] also proposed to improve the algorithm based on expanding the search space. At the same time, in order to compromise between the success rate and the number of iterations, a new parameter I was added to the algorithm which made it adjustable. The simulation experiment of the inverse problem showed that the method was more successful than the traditional Grover algorithm in the same number of iterations. And if the number of iterations was not limited, the probability of success can be higher. In 2013, Guangfu Han et al [8,9] modified the corresponding relationship between the number of iteration step and the phase rotation angle of the Grover improved algorithm ; then simulated numerically these four kinds of improved algorithm which based on PI/2 phase rotation, phase rotation, fixed phase rotation and accurate Grover algorithm and also gave a detailed comparative analysis for the simulation results. In 2015, Avatar Tulsi[10] offered implementation advantages for clause satisfaction problems.
Therefore, after years of improvement, Grover quantum search algorithm is gradually perfect, which has formed a relatively complete system of search algorithm, it can adapt to various different search demand. Evidence has been accumulating to establish generic superiority of quantum search algorithm.
In the present paper we focus our attention on a different aspect of quantum search algorithm, the simulation of the algorithm. In particular, the aim of this work is to simulate the number of iterations and the specific implementation steps of quantum search algorithm with QCL in Linux operating systems. It is necessary for us to do further research on quantum search algorithm, it may be used to speed up the solution to problems in the complexity class NP (such as Hamiltonian cycle problem), to do quantum counting, and to accelerate the Quantum search of an unstructured database and other classic problems, which is widely used and effective. It can effectively crack the DES^{11,12} cipher system, which has accelerated to search for potential use of key password system. This feature of efficiency is an outstanding advantage of quantum search algorithm.
We organize this paper as follows. In Sec. 2, we first explain the basic ideas and the theory of Grover quantum search algorithm. We then analyze the algorithm’s flow chart and the specific implementation steps. Lastly, we prove that the algorithm we have demonstrated is optimal and illustrate the number of iterations of Grover quantum search algorithm. In Sec. 3, the simulation of the Grover quantum search algorithm is carried by QCL in Linux operating systems. we then present results of simulations and analysis it. Section 4 is devoted to conclusion.
2. Grover Quantum Search Algorithm
2.1. Oracle Searching Based on the Idea of Black Box
Oracle represents for the meaning of prophecy, God, philosophers, saints in ancient Greek, while it commonly known as "black box oracle". "Black box" is a program that can perform some computation tasks in computer science, while in quantum computation, it refers to a series of unitary transform that can accomplish some calculation tasks. When it analyzed the complexity of the problem, the costs of computing resources of "black box" are not included.
Suppose we wish to search through a search space of N elements. For convenience we assume N=2^{n}, so the index can be stored in n bits, and that the search problem has exactly M solutions, with 1≤M≤N.A particular instance of the search problem can conveniently be represented by a function f(x), which takes as input an integer x, in the range 0 to N-1.By definition
(1)
Suppose there is a black box, a bit of which is used to identify the search of solution. In fact, the black box can be regarded as a definition for the unitary operator function
(2)
Where Å denotes addition modulo 2, is the index register，and the oracle qubit is a single qubit which is flipped if f(x)=1, and is unchanged otherwise. We can check whether x is a solution to our search problem by preparing , applying the oracle, and checking to see if the oracle qubit has been flipped to.
Usually, in the quantum search algorithm it is useful to apply the oracle with the oracle qubit initially in the state .Then the action of oracle is thus: .
We say that the oracle marks the solutions to the search problem, by shifting the phase of the solution. For an N item search problem with M solutions, it turns out that we only need apply the search oracle times in order to obtain a solution, on a quantum computer. There is a distinction between knowing the solution to a search problem, and being able to recognize the solution. Oracle can identify solutions, but if you want to find the solution requires the application of a certain algorithm once or repeatedly calls oracle.
2.2. The Theory of Grover Quantum Search Algorithm
The basic idea of Grover quantum search algorithm^{13,14,15}is repeatedly apply Grover quantum iteration process to enlarge the search for target items of probability amplitude, while suppressing the non target item probability amplitude. Finally, search for the target item with a high probability (close to 1) by measuring the quantum state.
Design input for n qubits and Oracle work space. Schematically, the search algorithm operates as it shown in Figure 1.
From the Figure 1, we need to execute O() search, and each search is called a Grover iteration. The algorithm begins with the computer in the state |0>, the Hadamard transform is used to put the computer in the equal superposition states,
(3)
Where is the marked state we're looking for.
And then through the O() Grover iteration to complete the search process. The Grover iteration, whose quantum circuit is illustrated in Figure 2,may be broken up into four steps:
(1) Apply the Oracle O to verify whether the search element is the need to search in the solution actual problem solving.
(2) Apply the Hadamard transform H^{}. That is, do the following operations on each bit:
(4)
(5)
(3) Perform a conditional phase shift on the computer, with every computational basis state except |0> receiving a phase shift of -1,
(6)
(4) Apply the Hadamard transform H^{}.
In the above steps, steps 2 and 4, the Hadamard transforms, require operations each, step 3, the conditional phase shift, may be implemented using O(n)gates. The cost of the oracle call depends upon the specific application; for now, we merely need to note that the Grover iteration requires only a single oracle call.
2.3. Grover Quantum Search Algorithm’S Flow Chart and the Specific Implementation Steps
Step1：Preparation of superposition state.
(7)
Step2：Compute parallelly.
(8)
Step3：Z operation transform.
(9)
Step4：Perform D transform on the first component of ---- augment the probability of solution b correspond to the state |b,1〉.where D is described by the matrix
(10)
Namely: the variation amplitude
(11)
=
(12)
Among them, is the amplitude of the.
Step5: Repeat the implementation of step3 and step4 step3 and step4 for k times, and measure the state, we will get the result, and output x as a real solution.
2.4. Optimality of the Grover Quantum Search Algorithm
In the case that there is only one solution for the search problem, we have shown that a quantum computer can search N items, consulting the search oracle only times. We now prove that no quantum algorithm can perform this task using fewer than accesses to the search oracle, and thus the Grover quantum search algorithm we have demonstrated is optimal ^{16,17}.
Suppose the algorithm starts in a state and applies the oracle exactly k times, with unitary operations,,…, interleaved between the oracle operations. Define
(13)
(14)
That is, is the state that results when the sequence of unitary operationsis carried out, without the oracle operations. In order to simplify formulas, we use the notation for and for as a convenience.
(15)
Where is the estimator, it is a measure of the deviation after k steps caused by the oracle, from the evolution that would otherwise have ensued. If this quantity is small, then all the states are roughly the same, and it is impossible to correctly identify x with high probability. This demonstrates two things:(1)a bound onthat shows it can grow no faster than ;(2)a proof thatmust be if it is to be possible to distinguish alternatives. Combining these two results gives the desired lower bound.
Firstly, we give an inductive proof that.
(1) When k=0, =0 is clearly established.
(2) Assume that k is established, so for k+1,there is
(16)
Applying the unitary transform to the second equals on the right hand side: it is only change the abnormal vector direction, do not change the abnormal mold of vector.
Furthermore, we add
to,
thus
(17)
Applying with a= and b= =，
gives
(18)
Applying the Cauchy-Schwarz inequality to the second term on the right hand side, and noting that ，gives
(19)
By the inductive hypothesis, we obtain
(20)
In summary，the establishment of
(21)
Secondly, to complete the proof we need to show that. Defining, and we suppose for all x, so without loss of generality we may assume that, and therefore
(22)
Defining
, and (23)
We have
(24)
Applying the Cauchy-Schwarz inequality gives, so we have
(25)
Combining (22) with (23) gives for sufficiently large N, where c is any constant less than . Since this implies that .
Therefore, to find a solution to the search problem with at least one-half probability, we must call the oracle times.
2.5. The Number of Iterations of Grover Quantum Search Algorithm
In order to obtain a solution of search problems, how many times must the Grover iteration be repeated to rotate near ? The initial states of the system can be described as
(26)
Where,, N is the total number of state, M is the total number of labeled state. And indicates a sum over all x which are solutions to the search problem, indicates a sum over all x which are not solutions to the search problem.
So rotating through radians takes the system to.Then repeating the Grover iteration.
(27)
CI (x) is represented as integer which is closest to the real numbers.
To achieve this, note from the above formula that, so a lower bound on q will give an upper bound on R. Assuming for the moment that, we have, from which we can derive the number of iterations required, where by convention we round halves down, . That is, Grover iterations must be performed in order to obtain a solution to the search problem with high probability. The search times of the classical algorithm is , which is two times of acceleration of the classical search algorithm.
3. The Simulation of the Grover Quantum Search Algorithm
3.1. The Basic Concept of QCL
QCL^{18,19}was put forward by B.Omer in 1998, which is a structured imperative quantum programming language. The grammar of it is similar to C/Pascal, using quantum process and function to define the quantum operation, introducing the quantum register, defining quantum rich data types, considering quantum control structure based on conditions transform. The QCL statement has three categories, simple statements, control flow statements, and interactive command; there exited several types which include scalar, Zhang Liang, quantum, Boolean, string and so on, while the type of scalar include integer, real type, complex type, Boolean and string type; Zhang Liang types include three quantum types, such as a vector, matrix and n order Zhang Liang; Quantum types has the general register (qureg), quantum constant (quconst), the destination register (quvoid), erase the register (quscratch) of several, and designed the institutions of transparent removal which make few qubits can be fully utilized.
3.2. QCL Setup in Linux Operating Systems
QCL is only available in Linux operating systems, and ubuntu is a desktop application based on Linux operating system, so we choose to install QCL in ubuntu. Here are installation steps and the corresponding solutions to problems:
(1) Download the QCL program, the current version is here. (http://tph.tuwien.ac.at/~oemer/tgz/qcl-0.6.4.tgz)
(2) Download and install the bison and flex tools.
(3) Install libplot2c2 and libplot-dev (apt-get install libplot2c2 libplot-dev). This is a key step, otherwise you couldn’t find the include<plot.h> file, the errors will occur, thus unable to install qcl successfully.
(4) Download the latest readline (readline-5.2.tar.gz), then decompress and install.
①tar xvzf readline-5.2.tar.gz; ②./configure; ③make; ④make insatll.
(5) Entering the folder after the decompression, make and then to generate direct current folder QCL, then QCL has been installed successfully.
If the error occurs：/usr/bin/ld:cannot find -lncurses
The solution：apt-get install libncurses-dev
(6) The experimental steps: ①Type ‘qcl’ to start the environment; ②Type ‘include "grover.qcl";’ to import the grover.qcl file; ③Use ‘grover(N)’to run the Grover Search for the number N.
3.3. Experimental Results and Analysis
When N=2048, the search results of Grover quantum search algorithm as shown in figure 4:
Analysis：Floor (x) is the function of "rounding down", or "rounded down", the largest integer that is not larger than x. Ceil (x) function: the smallest integer greater than or equal to the specified expression returns. When N is equal to 2048, this is equivalent to an English dictionary pages, Grover quantum search algorithm is very effective. The number of bits required for n=floor (log (2048,2)) +1=12, the number of iterations of m=ceil (pi/8*sqrt(2^12)) =26, is consistent with the number of iterations of previously mentioned, which verified the time complexity of Grover' s quantum searching algorithm is, but the algorithm' s time complexity on classical computers is .Owing to the qubits entangled, the effect of quantum interference will make the previous results to the next quantum operation. After the operation of this kind of interference is repeated times, the probability of obtaining the correct answer for 1/2.And if you have to repeat the operation a few times, you can find the required solution close to 1.
4. Conclusion
This paper introduces the method of Grover quantum search algorithm in detail, for a database, which contains element, and the search problem has exactly M solutions, with. Firstly, prepare for the uniform superposition state, and then repeat , where O is a Oracle search. The role of O is,, then, otherwise unchanged; secondly, the function of U is changed from |0> to -|0>, and keep all the other computing base invariant. Finally, measuring the final state, a solution with a high probability of the problem is obtained, and the Grover quantum search algorithm has been proved to be the optimal search algorithm. Then simulate the number of iterations of quantum search algorithm with QCL in Linux operating systems, and validate the time complexity of Grover's quantum searching algorithm is, but the algorithm's time complexity on classical computers is .
Acknowledgement
This project was supported by "the quantum computation and quantum communication research team program "of School of electrical and electronic engineering of Hubei University of Technology and "thousand new energy vehicle program of ten cities" of Wuhan Science and Technology Bureau (NO.2013011801010600).
References