In the last post (Quantum Searching), we saw how quantum search works even without a quantum computer. In this post, we will see how to program the search using the IBM QISKit.

The goal in quantum search is to find the value such that given a function , the value of is equal to 1 when . There can be more than one value of that satisfies this relationship.

As we have seen here, searching for the state is a matter of rotating the state , where . Therefore, the search process is computing for the vector

so that

and then measuring the state to get the basis state that corresponds to the unknown .

To program this, we need to construct the circuits of both and .

But first and foremost, let’s construct the circuit.

## The Circuit

First, start with the n-qubit input state and 1 qubit output state and create a superposition of states using the hadamard operator:

This is equivalent to the circuit:

## The Circuit

Constructing the circuit is equivalent to constructing the circuit.

Apply the unitary operator to the state :

The circuit, shown below in a red box, returns 1 for and 0 otherwise

## Constructing the Circuit

So how do we check if the input qubits are in the state ?

- Initialize all auxiliary qubits to the state.
- Check if the first qubit is . To check this, negate it using the gate . Then using the CNOT gate, this will put qubit in the state if the first qubit is .
- Next, check that the 2nd and 3rd input qubits are in the state using the Controlled-CNOT gate. If both are in state , then the qubit will become .
- Since both and are in the state , this will flip the state of the output qubit .
- Reset the values of the qubits back to using the control gates on the right.
- Finally reset the value of the first qubit back to its original value using the gate X at the far right.

## Constructing the Circuit

The operator W is defined as

It’s just a matter of constructing the circuit that implements .

Let be a basis vector. Then

It is simpler to implement since it acts as the identity for any basis vector not equal to and multiplies by -1. This means we will be implementing , which is ok since the -1 factor will not have any impact when we take the probabilities.

To implement as a circuit, we need one auxiliary qubit that will record if the first and second qubit are both in state using a Controlled-CNOT gate. Then a controlled-Z gate will negate the third qubit if the auxiliary qubit is in state and the third qubit is .

In sequence of operations, first we have to negate the qubits to turn state to . Then we do the sequence below:

Afterwards, we negate again the qubits to return them to previous state. The end result will be taking the state to . The diagram below is the implementation of this circuit. The Hadamards to the left and right make this the implementation of the circuit.

## The full circuit

Now that we have and , the full circuit is:

## QISKit program

Finally, here is the code to implement the quantum search:

# Import the Qiskit SDK from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister from qiskit import execute, Aer from qiskit.tools.visualization import circuit_drawer, plot_histogram # function to apply hadamards to the input and output qubits def h(qcirc, qin, qo): qcirc.h(qo[0]) for i in range(0,3): qcirc.h(qin[i]) # function to return 1 when the state is 6 == 110 (base2) def uf(qcirc, qin, aux1, qo): qcirc.ccx(qin[1],qin[2],aux1[0]) qcirc.x(qin[0]) qcirc.cx(qin[0],aux1[1]) qcirc.ccx(aux1[0],aux1[1],qo[0]) qcirc.cx(qin[0],aux1[1]) qcirc.x(qin[0]) qcirc.ccx(qin[1],qin[2],aux1[0]) # function that implements W def w(qcirc,qin,qaux): for i in range(0,3): qcirc.h(qin[i]) qc.x(qinput[i]) qcirc.ccx(qinput[0],qinput[1],qaux[0]) qcirc.cz(qaux[0],qinput[2]) qcirc.ccx(qinput[0],qinput[1],qaux[0]) qcirc.barrier() for i in range(0,3): qcirc.x(qinput[i]) qcirc.barrier() for i in range(0,3): qcirc.h(qinput[i]) qcirc.barrier() # Define the Registers and circuit. qx1 = QuantumRegister(2,name="aux1") qout = QuantumRegister(1,name="qout") qx = QuantumRegister(1,name="aux2") qinput = QuantumRegister(3,name="qin") coutput = ClassicalRegister(3,name="cout") qc = QuantumCircuit(qinput,qout,coutput,qx1,qx) # start computing. First negate the output register qc.x(qout[0]) qc.barrier() # Apply hadamards to the input and output h(qc,qinput,qout) qc.barrier() # Apply the U_f operator uf(qc,qinput,qx1,qout) qc.barrier() # Apply the W operator w(qc,qinput,qx) qc.barrier() # Visualize the circuit. from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer, qx_color_scheme my_style = {'plotbarrier': True} my_scheme=qx_color_scheme() my_scheme['plotbarrier'] = False drawer(qc, style=my_scheme) # Take a measurement qc.measure(qinput,coutput) # Compile and run the Quantum circuit on a simulator backend backend_sim = Aer.get_backend('qasm_simulator') shots = 1000 job_sim = execute(qc, backend=backend_sim, shots=shots) result_sim = job_sim.result() answer = result_sim.get_counts() plot_histogram(answer)

And here is the result of the computation.

As you can see, the quantum computation was able to find our number with 77% probability. It seems that the accuracy is not that great at 77%. Actually, we can make it more accurate by applying the operator again:

In fact, we can apply up to times, where . See this post for more information.