Einstein Relatively Easy

Star InactiveStar InactiveStar InactiveStar InactiveStar Inactive
 
Pin It

 

              Previously, we have exposed the The Deutsch-Jozsa algorithm, one of the first example of an algorithm exponentially faster (1 evaluation) than any possible deterministic classical algorithm (2n-1+1 evaluations). It was a great finding, but unfortunately, not of a practical great interest.

In this article, we would like to introduce another quantum algorithm, the so called Grover's algorithm, after the name of its founder, Lov Grover[1].

Compared to the Deutsch alfgorithm, Grover's algorithm belongs to a completely different class of algorithms represented by the quantum search algorithm. These provide a less striking but still remarkable quadratic speedup over the best possible classical algorithms.

 

Context:

Suppose you are given a large unstructured list of N items. Among these items there is one item with a unique property that we wish to locate; we will call this one the winner w.

To find the winner -- the marked item -- using classical computation, one would have to check on average N/2 of these boxes, and in the worst case, all N of them.
On a quantum computer, however, we can find the marked item in roughly √N steps with Grover's amplitude amplification trick.

 

Principle:

The 'database' or unstructured list is comprised of all the possible computational basis states our qubits can be in. For example, if our list contains 4 items, the list is the states |00>, |01>, |10>, and |11>.  More generally, if the list is composed of 2N items, the list will contain the 2N states of N starting qubits.

The winner state w will be identified by a function f such as:

f(x) = 0 for x != w   

f(x) = 1 for x = w

 

Oracle

In our quantum circuit, this function will be implemented as an Oracle that add a negative phase to the solution state.

The quantum oracle related to a classical function f(x) does the following: for any value of |x> that is not the specific value w, f(x) is 0, hence the original value |x> will be returned.
In case the value w is passed through the Oracle, the result will be -|x> .

We notice that the quantum Oracle is a reversible operator as applying twice f(x) on x gives back x for every x ( if x=w  -|-x> = x)

As an example, suppose we have a beforehand know winner value w = 3 in a list 4 items.

f(0) = 0     f(1)=0      f(2)=0     f(3)=1

then the oracle's matrix will be a 4x4 diagonal matrix of the form:

 

To which state can we apply this oracle? Before looking at the list of items, we have no idea where the marked item is. Therefore, any guess of its location is as good as any other, which can be expressed in terms of a uniform superposition |s>

with N = number of items in the list = number of the states  = 2n  where n = number of qubits

At the start, each state has an equal probability of (1/√N)= 1/N (1/4 in our case) to be the winner.

In our case, it means that our matrix will be applied to the following state (0.5, 0.5, 0.5, 0.5)

By aplying our oracle, we have rotated the winner's state of Π (1/2 -> -1/2) but we did not change at all the measurement probalities. If at this point we were to measure in the standard basis {|x⟩}, this superposition would collapse, according to the fifth quantum law, to any one of the basis states with the same probability of 1/N (1/4 in our case).
Our chances of guessing the right value w is therefore 1 in N, as could be expected. Hence, on average we would need to try about N times to guess the correct item, and this algorithm won't give us any advantage compared to a classical search.

 

Amplitude Amplification

That's why Grover's algorithm includes a procedure called amplitude amplification, which is how a quantum computer significantly enhances this probability. This procedure stretches out (amplifies) the amplitude of the marked item, which shrinks the other items' amplitude, so that measuring the final state will return the right item with near-certainty.

The Diffusion Operator does a so-called "inversion about the mean", which means the following:

  • - all values in the state vector are summed
  • - the average is calculated
  • - all values are replaced with the value that is obtained by mirroring the value about the mean

 

In our case the average value equals:  (1/2 + 1/2 + 1/2 -1/2) /4 = 1/4

We now need to "mirror" the elements (which are either 1/2 or -1/2) around this value of 1/4.

On the below figure, the states before the amplification are shown as blue circles, the states after the amplification are represented as red squares and the average value is shown as a dashed vertical green line with absciss x = 1/4 = 0.25

As we can easily see, mirroring 1/2 (blue points) results in 0, but mirroring -0.5 results in 1.

In the usual matrix representation, the result of the diffusion operator gives

That's exactly what we wanted. At the end of the algorithm, we are certain - with probability equals to one, to get the index corresponding to |11>, which is 3.

In case there are more than 2 qubits, the probability for measuring the correct answer is larger than the probability of measuring any of the other options, but it is not 100%. In that case, the quantum oracle and the diffusion operator have to be applied multiple times. It can be proven mathematically that the number of steps that provides the optimal result is the value closest to N ∗ Π / 4.

 

Algorithm's details

Oracle operator

 We saw previously that the Oracle corresponding to the classical function shoud inverse the winner state as per below:

 

Let's try to justify thereafter why the sign is flipped.

As a reminder from the previous article we know that the oracle maps the state |x\rangle |y\rangle to |x\rangle |y\oplus f(x)\rangle , where \oplus is addition modulo 2. In other words, the oracle leaves the |x> qubit (index qubit) in its original state, and the |y> qubit (Oracle qubit) is replaced by the XOR operation between y and f(x).

 By definition f(x)=0 or f(x) =1, ff we set the Oracle qubit |y> in the state 1/√2(|0> - |1>)

 By examining both outputs, we can generalize the equation as:

We regard |x⟩ as flipped, thus the oracle qubit |y> is not changed, so by convention the oracle qubits are usually not mentioned in the specification of Grover's algorithm.

Thus the operation of the oracle is simply written as:

 

 

[1] Grover, Lov K. (1997). "A framework for fast quantum mechanical algorithms". https://arxiv.org/abs/quant-ph/9711043. Grover has been ranked as the 9th most prominent computer scientist from India.

Language

Breadcrumbs

Quotes

"The essence of my theory is precisely that no independent properties are attributed to space on its own. It can be put jokingly this way. If I allow all things to vanish from the world, then following Newton, the Galilean inertial space remains; following my interpretation, however, nothing remains.."
Letter from A.Einstein to Karl Schwarzschild - Berlin, 9 January 1916

"Quantum mechanics is certainly imposing. But an inner voice tells me that it is not yet the real thing. The theory says a lot, but does not really bring us any closer to the secret of the 'old one'. I, at any rate, am convinced that He is not playing at dice."
Einstein to Max Born, letter 52, 4th december 1926

RSS Feed

feed-imageRSS

Who is online

We have 165 guests and no members online