GROVER'S ALGORITHM

more background information Quantum states (|0⟩, |1⟩, |+⟩, |-⟩) can be represented as a superposition. |ψ⟩= α|0⟩+ β|1⟩

|α|^2+ |β|^2=1

α=√(1-p,) β=e^jφ √p, 0≤p≤1,0≤φ<2π

|ψ⟩=√(1-p)|0⟩+ e^jφ √p,|1⟩

e^jφ is the phase

The phase can be used to offset the qubit. There are different gates we can use to do the offsets (T, S, Z etc.)

A phase change example can be found here. https://quantum-computing.ibm.com/composer/d065727b7bdddc3f658e2ad8badeb1ba.

Grover's Algorithm

Grover's algorithm shows the exponential advantage of a quantum computer. It is a search algorithm that provides a huge improvement to a regular classical sorting algorithm. This is because Quantum Mechanics systems can be in a state of superposition and algorithms can simultaneously examine multiple states. A search for an item from a random list of n items can be obtained in O(√n)steps.

Basically, all the states (right and wrong answers) are superposed together using a function and then phase angle change operations are applied to the superposition. This makes the probability of the right answer a lot higher than the other answers making it more probable to be measured.

Grover's Algorithm Encoding

The search list is provided in superposition to a function f which returns f(x) = 1 for the right answer and f(x) = 0 for the wrong answer. We binary encode the items as qubits x,w ∈ {0,1}^(n) so that N = 2^n.

We define an oracle matrix to act on any single. U|x⟩= (-1)^f(x)|x⟩, which is –|x⟩ if the item is found.

Grover's Algorithm Function

  1. Uniform superposition
  2. Oracle refection
  3. Additional reflection

The two reflections equal to a rotation. The whole procedure ( 3 steps ) is repeated several times until the answer is the focus. This is approximately √n times. You can find an example of this algorithm here. Grover N=2 A=00 https://quantum-computing.ibm.com/composer/39354dfd1bb6ac3edb8f9a9659c834d4

𝑈𝜔|𝑥⟩=(−1)^𝑓(𝑥)|𝑥⟩ is the oracle. Inputs are represented by this function but in a superposition.

The superposition of all inputs |s⟩

|𝑠⟩=sin𝜃|𝑤⟩+cos𝜃|𝑠′⟩, where 𝜃=arcsin⟨𝑠|𝑤⟩=arcsin√N superposition of the right answer and all the wrong answers.

Amplitude amplification singles out the right answer in the superposition by using quantum gate circuitry to adjust the amplitude of the right answer.

  1. Superposition is done by a Hadamard gate. 𝜃=arcsin(½)=𝜋/6.

all the states = ½(|00⟩+|01⟩+|10⟩+|11⟩)

The circuit currently.

  1. We apply the oracle reflection (see equation above)

Oracle for |𝜔⟩=|11⟩

Let's look at the case |𝑤⟩=|11⟩

. The oracle 𝑈𝜔 in this case acts as follows:

𝑈𝜔|𝑠⟩=𝑈𝜔.½(|00⟩+|01⟩+|10⟩+|11⟩)=½(|00⟩+|01⟩+|10⟩−|11⟩)

This is gotten by the controlled z gate = H gate + CNOT gate + H gate. The CNOT applies an 𝑋 to its target qubit whenever its control is in state |1⟩

see full circuit https://quantum-computing.ibm.com/composer/89fe6d3a014ad268b44b5f8b4a5f4b9c

###Reference https://quantum-computing.ibm.com/docs/iqx/guide/