Grover’s Search using amplitude amplification and an oracle that finds a marked element.

Grover’s Search Implementation

We are given $N=2^n$ elements, and one element is marked. The task is to find this marked element.

We are going to use $n$ qubits. At the beginning we apply Hadamard to each qubit, so we put our quantum state into superposition. The amplitude of each basis state is set to 1/$\sqrt{N}$ . After that we iterate the following algorithm for several times:

Make a query: apply a query oracle operator to qubits - it flips the sign of the amplitude of the state that corresponds to the marked element.
Inversion: apply a diffusion matrix - the amplitude of each state is reflected over the mean of all amplitudes.

Query operation

Oracle

Suppose that there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ with the following properties:

\[\begin{align*} f(x)&=1 &\mbox{ if $x$ is marked}\\ f(x)&=0 &\mbox{ otherwise} \end{align*}\]

Grover’s algorithm does not actually search a list of elements, but given function $f$ with the above properties, it finds the element $x$ such that $f(x)=1$.

Consider the following function $f:\{0,1\}^2 \rightarrow \{0,1\}$. \[ f: \begin{array}{c|c} \mathbf{In} & \mathbf{Out} \\ \hline |00> & 0 \\ |01> & 0 \\ |10> & 0 \\ |11> & 1 \end{array} \]

f is often called as the oracle or blackbox. In this case element 11 is marked.

Sign flip using Phase kickback

We use phase kickback to flip the sign of the marked element:

Create a circuit with 3 qubits, the last qubit is the ancilla.

A quantum circuit requires a number of ancilla qubits to store partial results; the ancilla qubits are initially in a well-defined state, usually |0〉, and must be returned to the same state at the end of the computation.

Set output qubit (qreg[2]) to |−⟩ by applying X and H.

Set output qubit (qreg[2]) back.

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

qreg = QuantumRegister(3)

mycircuit = QuantumCircuit(qreg)


#set ancilla
mycircuit.x(qreg[2])
mycircuit.h(qreg[2])

mycircuit.barrier()

mycircuit.ccx(qreg[0],qreg[1],qreg[2])

mycircuit.barrier()
    
#set ancilla back
mycircuit.h(qreg[2])
mycircuit.x(qreg[2])

<qiskit.circuit.instructionset.InstructionSet at 0x7f975e698730>

job = execute(mycircuit,Aer.get_backend('unitary_simulator'))
u=job.result().get_unitary(mycircuit,decimals=3).data

for i in range(4):
    s=""
    for j in range(4):
        val = str(u[i][j].real)
        while(len(val)<5): val  = " "+val
        s = s + val
    print(s)
    

mycircuit.draw(output='mpl')

  1.0  0.0  0.0  0.0
  0.0  1.0  0.0  0.0
  0.0  0.0  1.0  0.0
  0.0  0.0  0.0 -1.0

Inversion Operator

In a list, inversion around the mean is achieved through (-element_value + 2* mean of all elements) in the list.

How amplitude amplification works in principle?

We start with a vector X = [10, 10, 10, 10, 10], whose mean is 10. The difference between the fourth element and the rest is: 0.

Phase inversion: [10, 10, 10, -10, 10].
Mean inversion: The mean now is X_bar = 6. The rule for mean inversion is: -X_i + 2X_bar. Thus, we get: [2, 2, 2, 22, 2]. The difference between the fourth element and the rest is: 20 - it increased!
Phase inversion: [2, 2, 2, -22, 2].
Mean inversion: The mean now is X_bar = -2.8. Then, we get: [-7.6, -7.6, -7.6, 16.4, -7.6,]. The difference between the fourth element and the rest is: 24 - it increased!

How amplitude amplification works in Grover Search?

To implement the inversion (diffusion) operation, we will need additional (ancilla) qubit. This is how we implement the inversion operator:

Set the ancilla qubit to |-> by applying X and H.
Apply H to all qubits other than the ancilla.
Apply X to all qubits other than the ancilla.
Apply multiple controlled NOT operator, where the ancilla qubit is target and all other qubits are used for controlling.
Apply X to the ancilla qubit.
Apply X to all qubits other than the ancilla.
Apply H to all qubits other than the ancilla.
Set ancilla qubit back by applying X and H.


def inversion(circuit,quantum_reg):
    
    
    #step 1
    circuit.h(quantum_reg[1])
    circuit.h(quantum_reg[0])
    
    #step 2
    circuit.x(quantum_reg[1])
    circuit.x(quantum_reg[0])

    #step 3
    circuit.ccx(quantum_reg[1],quantum_reg[0],quantum_reg[2])

    #step 4
    circuit.x(quantum_reg[1])
    circuit.x(quantum_reg[0])
    
    #step 5
    circuit.x(quantum_reg[2])
    
    #step 6
    circuit.h(quantum_reg[1])
    circuit.h(quantum_reg[0])

The code below including the inversion function above implements the steps described above

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

qreg1 =  QuantumRegister(3)

mycircuit1 = QuantumCircuit(qreg1)

#set ancilla qubit
mycircuit1.x(qreg1[2])
mycircuit1.h(qreg1[2])

mycircuit1.barrier()
    
inversion(mycircuit1,qreg1)

mycircuit1.barrier()


#set ancilla qubit back
mycircuit1.h(qreg1[2])
mycircuit1.x(qreg1[2])


job = execute(mycircuit1,Aer.get_backend('unitary_simulator'))
u=job.result().get_unitary(mycircuit1,decimals=3).data
for i in range(4):
    s=""
    for j in range(4):
        val = str(u[i][j].real)
        while(len(val)<5): val  = " "+val
        s = s + val
    print(s)
    
mycircuit1.draw(output='mpl')

 -0.5  0.5  0.5  0.5
  0.5 -0.5  0.5  0.5
  0.5  0.5 -0.5  0.5
  0.5  0.5  0.5 -0.5

Bringing everything together

We’ll use both sign flip for the marked element and the inversion operation for the search

In this case 11 is the marked element

def sign_flipper():
    mycircuit.ccx(qreg[0],qreg[1],qreg[2])

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

qreg = QuantumRegister(3)
creg = ClassicalRegister(2)

mycircuit = QuantumCircuit(qreg,creg)


#initial step - equal superposition

for i in range(2):
    mycircuit.h(qreg[i])
    
mycircuit.barrier()

#set ancilla 
mycircuit.x(qreg[2])
mycircuit.h(qreg[2])

mycircuit.barrier()


#change the number of iterations
iterations=1

#Grover's iterations.
#
#Sign_Flipper
#
#Inversion operator
#
sign_flipper()

inversion(mycircuit, qreg)

mycircuit.barrier()

   
#set ancilla

mycircuit.h(qreg[2])
mycircuit.x(qreg[2])

mycircuit.barrier()

mycircuit.measure(qreg[0],creg[0])
mycircuit.measure(qreg[1],creg[1])

job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=10000)
counts = job.result().get_counts(mycircuit)

# print the outcome
for outcome in counts:
    print(outcome,"is observed",counts[outcome],"times")

mycircuit.draw(output='mpl')

11 is observed 10000 times

So this is Grover’s search

If we want to mark any other element, then we need to make changes to the function sign_flipper()

If we want to mark 01 element then the sign_flipper function would change as:

def sign_flipper_01():
    mycircuit.x(qreg[1])
    mycircuit.ccx(qreg[0],qreg[1],qreg[2])
    mycircuit.x(qreg[1])


qreg = QuantumRegister(3)
creg = ClassicalRegister(2)

mycircuit = QuantumCircuit(qreg,creg)


#initial step - equal superposition

for i in range(2):
    mycircuit.h(qreg[i])
    
mycircuit.barrier()

#set ancilla 
mycircuit.x(qreg[2])
mycircuit.h(qreg[2])

mycircuit.barrier()


#change the number of iterations
iterations=1

#Grover's iterations.
#
#Sign_Flipper
#
#Inversion operator
#
sign_flipper_01()

inversion(mycircuit, qreg)

mycircuit.barrier()

   
#set ancilla

mycircuit.h(qreg[2])
mycircuit.x(qreg[2])

mycircuit.barrier()

mycircuit.measure(qreg[0],creg[0])
mycircuit.measure(qreg[1],creg[1])

job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=10000)
counts = job.result().get_counts(mycircuit)

# print the outcome
for outcome in counts:
    print(outcome,"is observed",counts[outcome],"times")

mycircuit.draw(output='mpl')

01 is observed 10000 times