Many of today's technologies rely on big data, so the speed of database searches is critical. The speed at which quantum computers can search databases is one of their many advantages over classical computers, and the Grover quantum search algorithm will be introduced in this article.
01
Search Questions (Classical and Quantum)
The police tracked down a male offender, who eventually entered a neighborhood and fled home. This complex has 400 units, each of which houses a couple, so there are a total of 400 men. The police have photographs of the fugitives and photographs of the 400 individuals in the police database. So, how do you find this criminal out of these 400 suspects? This is a search problem, assuming that the 400 male photos in the database are completely out of order, then this is an unstructured search problem.
The Grover quantum search algorithm is also used to solve this type of search problem. Here's a more general description:
Let's say you're given a large list of N items, one of which we want to find with unique attributes. We refer to this item as the "winner", denoted by W. Or, to use the simplest analogy, suppose we are searching for a fugitive among many suspects, and w is the fugitive.
Consider the simplest scenario: there is only one criminal w in N suspect x, as shown in Figure 1a. Each candidate on the list is first marked with a specific color, fugitive w is red, and all others x are marked in gray. We may prescribe a method for determining a fugitive, for example, by comparing photographs.
Or you can consider a method related to "calculation": assuming we know the criminal's ID number w, we can compare it with the number x of all suspects, i.e., do a subtraction calculation (x-w). The result of the calculation can be expressed by a binary objective test function f(x): if x is not equal to w, f(x) = 0, and if x is a fugitive, i.e. x = w, f(x) = 1.
Figure 1: Search Problem and Test Function f(x)
Because the suspect's data x is out of order, if the classic method is used, the fugitive's number w can only be subtracted one by one. In the worst case, all N suspects need to be checked, and in the best case, 1 suspect must be checked, and on average, N/2 subtractions must be done. Thus, the relationship between the number of operations and N in a classical search is linear: O(N).
So now consider whether it is possible to reduce the complexity of the search operation if it is a quantum search?
The advantage of quantum search lies in the superposition of qubits, as shown in Figure 1b, the "database" in quantum computing is made up of all the computing bases in which qubits may be located. For example, if we have 3 qubits, the list of computational bases is: |000>, |001>,......|111 >, that is, eight values from 0 to 7. The difference between quantum search and classical search is that quantum computing can operate these 8 registers at the same time, as if 8 registers are performing parallel operations at the same time. The more registers there are, the more powerful this parallel "acceleration" becomes.
Another difference from classical computing is that quantum physics is probabilistic, and the numerical values that characterize quantum states are a string of probability amplitudes. For example, at first we didn't know where the fugitive W was looking for, and all the suspects were likely criminals. That is, the initial quantum states given by the 8 registers are probabilistically equal, and the probability spokes of each register being w (fugitive) are the same.
Let's use the process of finding a fugitive as an analogy to illustrate the difference between classical search and quantum search.
Classically, it is assumed that only one photo can be taken out at a time in the database, so there is no better way to compare the fugitive's photo with it one by one. Do 1 time in the best case and 400 times in the worst case, with an average of 200 times.
The quantum situation is like having a magic platform where all the photos can be put together, so that the photos of the fugitives can be compared with all the photos in the database at the same time. Don't rejoice too soon, though! The large platform is easy to collapse and cannot be opened casually, and although there are 400 photos, each photo has a different brightness, and each photo is illuminated with a different probability, which will change according to the degree of exposure of the fugitive's information, for example, at the beginning, it is completely unknown where the fugitive is, therefore, the probability (brightness) is evenly divided on 400 photos, and if you open it at this time, you can't see it clearly.
Scientists always have their own unique approach. Grover found a way to do this, before opening the big platform, he repeatedly performed some "calculations" or "comparisons" on all the photos on the platform, so that the probability of the photos being illuminated changed, and the trend of change was to make more and more probability radiations concentrated in the position corresponding to the fugitive photos in the database. In this way, when the platform is finally opened, almost only the photo of that one position is illuminated. So, the fugitive was caught!
Importantly, Grover's method only takes 20 (square roots of 400) comparisons to find the target in the case of 400 photos, instead of the average 200 times in the classic search. This shows the superiority of quantum algorithms.
02
Grover looks for quantum algorithms
Lov Grover (born 1961) is an Indian-American computer scientist. He gained fame for his invention of quantum algorithms in 1996, the second major algorithm proposed for quantum computing, after the Sauer algorithm in 1994, and finally implemented in scalable physical quantum systems in 2017.
Grover received his B.S. from the Indian Institute of Technology, Delhi in 1981 and his Ph.D. in Electrical Engineering from Stanford University in 1985. In 1984, he joined Bell Labs. From 1987 to 1994, he was a visiting professor at Cornell University. He retired in 2008 as an independent researcher.
In 2001, Lov Grover wrote a paper on how he came up with a quantum search algorithm.
Grover's inspiration comes from both physics and mathematics. From a physical point of view: it is a universal physical law that both classical and quantum systems "move" to the point with the lowest potential energy in the end. Just as a classical ball rolls into a region with lower potential energy, a uniform quantum superposition state that evolves under the Schrödinger equation will also be directed to a region with lower potential energy. See Figure 2.
Figure 2: Grover quantum search algorithm
Grover studied the evolution of the Schrödinger equation in an infinitely short period of time, and also considered quantum states on a finite set of points. He tried to find a quantum algorithm to effectively implement the evolution of quantum states in search problems. For example, the "probability equalization" state shown in Figure 2 corresponds to a relatively high "potential energy", while the quantum state to be searched for and labeled with a target corresponds to a lower "potential energy". Therefore, the search problem is to find an alternate iterative transformation method of unitary operators, and implement a process similar to the evolution of the Schrödinger equation, so that the quantum state with high potential energy gradually evolves to the quantum state with lower "potential energy". Finally, the quantum state with the lowest potential energy is obtained, that is, the state with the highest probability of radiation at the target location. This completes the search task.
We often emphasize that it is the "probability spoke" rather than the "probability" itself in quantum computing, which is an important difference between quantum computing and classical computing, although it is a one-word difference. Probability is the square of the probability spoke. In classical physics, what is superimposed is probability; The superposition state in quantum physics is the superposition of probability amplitudes. It is based on this feature that the search complexity of the Grover algorithm can be reduced from O(N) to O(sqrt(N)).
Another non-negligible feature of quantum computing is that it is inconvenient to measure the quantum state during the operation process, which will cause the wave function to collapse and destroy the quantum state. Therefore, measurements are generally only made at the end.
To summarize the central idea of the Grover algorithm, the parallel operation function of the quantum superposition state is used, after several iterations, the probability amplitude of w at the "marker" is amplified to increase and the probability amplitude of other positions is reduced, and finally the wave function collapses to the state with the largest probability radiation, that is, the w state.
It can be proved that the Grover algorithm can find w by calculating sqrt(N) times. It doesn't sound like a lot of acceleration, it's just a square acceleration. But it's actually the maximum speedup we can expect from a search algorithm. And when N is large, secondary acceleration can really save a lot of time. For example, if there are 100 suspects, ID numbers 1 to 100, randomly and disorderly distributed in 100 registers, to find a particular number, the classical method requires an average of 50 operations, and the quantum algorithm only needs 10 times! In addition, the algorithm can be used for more than just data searching, but can also be used to obtain time improvements for secondary runs for various other algorithms.
03
Specific steps of the Grover algorithm
Figure 3: Schematic diagram of the steps of the Grover algorithm
To sum up, the core of Grover's algorithm is amplitude amplification: the probability amplitude of target w is amplified, and the probability amplitude of all other "non-target terms" x is reduced. The whole process is shown in Figure 3, starting with the preparation of the initial quantum state by Gate H, the iterative cycle in the middle is the amplitude amplification, and the last step after the cycle is the measurement.
The initial state is a uniform quantum superposition state that indicates that all suspects have an equal probability of being a criminal. The homogeneous state |s> can be easily constructed from n H-gates acting on n qubits in the ground state |0>.
Then try to change the probability, and at the same time repeat some operation on the N registers, so that the probability amplitude of the target term w is constantly amplified> and the other probability amplitude |x> is constantly reduced, and this "amplitude amplification" process needs to be repeated until w is found.
The amplitude amplification process of the loop is divided into two steps: the quantum black box function U (oracle), and the diffusion operator operation U.
Figure 4: Geometric interpretation of amplitude amplification
The Amplitude Amplification algorithm has a good geometric interpretation and is represented as a state vector producing rotation in a two-dimensional plane, as shown in Figure 4. The initial state is a uniform superposition of |s>, |w> and |s > a two-dimensional plane in a vector space, and the two vectors |w> and |s >are not completely perpendicular to each other, because |w> also radiates in the superposition state |s> as an N probability. However, we can introduce an additional state |s'> that is located in a two-dimensional plane consisting of |w> and |s> but perpendicular to |>.
The initial state is shown in Figure 4, on the left. In the plane coordinates of |w> and |s'>, the initial state |s> can be expressed as:
|s> = sinT |w> + cosT |s‘>,
Angle T = arcsin (projection of s in w) = arcsin(1/N), the lower left figure of Figure 4 is a bar plot of the uniform superposition state |s>.
Two steps in the iteration:
Step 1, apply the black box function U to flip the state |s>, as shown in Figure 4: U is used to invert the target state |w> and the other states remain unchanged. Geometrically, this corresponds to the flip of the |s> state with respect to the |s'> axis. This means that the amplitude of the |w> in the state |s> becomes negative, and it also means that the average amplitude (represented by the dotted line) decreases.
Step 2, now apply another diffusion operator U with respect to state |s>. This transition maps |s> to state UU|s>. The two reflections U and U correspond to a rotation, which rotates the initial state |s> closer to |w> as shown in the right figure of Figure 4.
The reflection operation of U in the amplitude bar chart can be understood as a reflection about the average amplitude (dashed line). Since the first reflection reduces the average amplitude, this transformation increases the amplitude of the |w> to several times its original value, and also reduces the other amplitudes, so it is called amplitude amplification.
Then repeat steps 1 and 2 and continue the amplitude amplification process until the required is reached.
The process shown in Figure 4 does amplify the amplitude, but at this point we have two questions: First, what exactly are the black box function U and diffusion operator U in the diagram? Second, how many times does this process have to be repeated to find w?
What the oracle function U of the Grover algorithm does is add a negative phase to the solution |w>, that is, for any state |x> in the computational base, you can create a function U:U (x) = x, if |x> is not equal to |w>; And U(x) = -x, if |x> equals |w>, as shown in Figure 5a. This function is called Oracle.
Figure 5: a) The black box function inverts w; b) Phase black box function
In Figure 5a, the black box function U can be expressed as a diagonal matrix where the value corresponding to the target term w is -1 and the others are 1. Figure 5a: The following figure represents a U-matrix of three qubits. Further, Oracle can be implemented with a phase function consisting of the classical test function f(x) shown in Figure 5b.
Some people may say, since you can reverse the term w, don't you already know the position of w? So what else to search for? This is a question that is often confusing when learning the Grover algorithm for beginners. Again, we need to emphasize the peculiarity of quantum computing: it is possible to operate multiple registers at the same time, but it is not possible to check the results of each register. So, although we say that U is able to invert w, we don't know which register the result is inverted because no measurement is taken. The result of the inversion is that each register is fed back based on its own internal data test function f(x).
To put it in layman's terms: each suspect knows for himself whether he is a criminal or not, but we don't know unless it is measured!
Even if you take a measurement, you can't determine the position of w just by reversing |w >. Because |w> is the probability spoke, and the measured result is the probability, i.e., the square of the probability spoke. |w> a change in the sign inverts the probability spoke, but does not affect the probability. The clever thing about the Grover algorithm is that in step 3 we apply another spread function U = 2 |s><s|-1. Its function is to reflect the state vector with respect to the mean amplitude, and the probability amplitude of w after reflection is amplified. Therefore, the combined action of steps 2 and 3 U=UU magnifies the probability of collapse to |w> after measurement.
So, back to the second question: how many times does this process U have to be repeated to maximize the probability amplitude of w?
Each step of the process U brings the position of the state vector closer to the position of |w>, assuming that the angle of each change is a uniform 2θ, and after the initial state |s> is applied t times: |ψ>= (UU)|s>. The final number of times required can be roughly understood as described in Figure 6.
Figure 6: Grover's algorithm
It has also been proven that N^1/2 rotation is sufficient. The reason why it can be reduced from the classical N times to N^1/2 times is that it deals with probability spokes rather than probabilities, that is, it is the probability amplitude that is amplified rather than just the probability, which is also the secret of quantum computing.
Resources:
【1】Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
【2】From Schrödinger's Equation to the Quantum Search Algorithm, Lov K. Grover (Bell Labs, Murray Hill, NJ), https://arxiv.org/abs/quant-ph/0109116
Source: Mozi Salon
Original title: Can quantum computers find criminals faster? |Quantum Computing Heroes (10)
Edited by virens