Grover’s Algorithm — In Python!
After learning about Grover’s Algorithm, I decided to try my hand at programming it for two and three qubits — in Python 3 using IBM Quantum Experience’s Quantum Lab and Jupyter (Notebook)! In this article, I will guide you through my steps, as well as what I learned. Please, follow along! By the way, here’s the tutorial I followed.
Before we get started. . .
Before we get started, there are a few things we will need to do. First, and foremost, if you don’t know what Grover’s Algorithm is, here is a Medium article by me about Grover’s Algorithm. Secondly, you will need an IBM Quantum Experience account in order to run the algorithm; you can click here to create one. Finally, if you are new to programming with Python, you can check out this tutorial to get yourself familiar with the language.
All right, with that out of the way, let’s get started!
Importing Modules
We need to import specialized modules [created by IBM] specifically designed for writing code for quantum computers, using import statements. By the way, you can also read my comments in the code as well (they are denoted by a ‘#’ or text enclosed in triple quotes → “““example”””).
We first import the “Standard” Python modules, which are MatPLotLib, a module designed for plotting, and NumPy, a module designed to simplify complicated calculations with its built-in functions (such as calculating the dot product of vectors). In this case, we are only using the pyplot “sub-module” of MatPlotLib. I used the abbreviations “plt” and “np” for matplotlib.pyplot and numpy, respectively, just for convenience.
Next, we import Qiskit, a special programming “language” developed by IBM for running code intended for quantum computers using IBMQ. It contains a bunch of special modules with specific functions, such as modules to create quantum circuits and modules for compiling and running the code.
Creating a Function for Initializing Qubits
After importing everything, we create a function to initialize all the qubits, which basically places them in an equal superposition using Hadamard gates. For more information about quantum gates/operations, here is another Medium article by me that describes the different operations/gates [in IBM Quantum Experience].
The function takes in two parameters, QC, which is a quantum circuit, and Qubits, the number of qubits we are initializing. Then, using a for-each loop, we iterator through all the qubits and apply the Hadamard gate to them. Then we return the new quantum circuit, and that completes out initialization function!
Two-Qubit Grover’s Algorithm
We’ll start off simple, with an easy, two-qubit version of Grover’s Algorithm. In this example, we will use the “winner” state⎪w〉=⎪11〉. This means we want the quantum computer to “discover” this state and ignore the others.
We create an integer variable n (of type int) with value 2, and a variable of type QuantumCircuit grover_circuit, a quantum circuit with n = 2 qubits. We initialize our circuit using the Initialize function we just created. Then we output a visual representation of the circuit. This is what it looks like; as you can see, we have the two Hadamard gates.
Applying the Oracle Matrix
After creating the circuit, we apply the Oracle Matrix. In the case of our example, it turns out to be just the controlled-Z gate, which we add to our quantum circuit grover_circuit.
Once again, we can output a visual representation of the circuit. As you can see, in addition to the two H gates, we also have the CZ gate now, which is the blue line with a dot at each end.
Applying the Diffuser
Next, we apply the Diffuser. In this case, it is the H gate (on both qubits), followed by the Z gate (on both qubits), followed by the CZ gate (on both qubits), and finally, the H gate (on both qubits).
As before, we can output the circuit to the screen. You can clearly see the new gates we added, which together makes up the Diffuser.
Simulation!
Believe it or not, that was actually all we need to create a two-qubit Grover’s Algorithm! We can then simulate the algorithm in a quantum simulator to get an idea of the what the expected results should be. It should match up with my intention, which is the winner state ⎪w〉=⎪11〉having a probability 1.000 of being discovered.
The first line gets a backend (using a function from the Aer module) of type ‘statevector_simulator,’ and is assigned to a a variable called sv_sim. Then we execute the circuit grover_circuit using the simulator sv_sim and place its value in a variable called job_sim. Then we get the statevector result of job_sim and assign it to the variable statevec, which we print out.
We then measure the qubits using the measure_all function. Now, instead of using a simulator of type ‘statevector_simulator,’ we will use the ‘qasm-simulator.’ We assign this new backend to the variable qasm_simulator. We create an integer variable (of type int) called shots and set it to 1024. This will be the number of times we repeat our experiment. Then, we simulate the circuit and get the results, stored in the variable results. Next, we store the probabilities of measuring each qubit state using the get_counts function and storing the value in answers. Finally, we plot a histogram of these probabilities.
After the simulation and plotting a histogram of the results, the expectation matches up with the simulation output — the state⎪w〉=⎪11〉was measured with probability 1.000, shown above.
Running on a Real Quantum Computer
After running a simulation of the two-qubit Grover’s Algorithm, we can try it out on a real quantum computer, using IBM Quantum Experience and IBMQ. The results should mirror the simulation.
We load our IBMQ account (in this case it’s my account) and store it in the variable provider. Then we select our device, filtering out the devices with less than three qubits, the devices which are configured to be simulators (so not actual hardware), and the devices which are not operational. We store this device in the ‘device’ variable. Finally, we run our circuit using the same procedures as above.
The two-qubit Grover’s Algorithm is now running on ibmqx2, one of IBMQ’s quantum computers which is connected to the cloud.
The job has successfully run. As expected, the output shows the state⎪w〉=⎪11〉being measured with probability 0.805, which is very close to the simulation. The other results are due to errors in the quantum computation and slight decoherence.
Three-Qubit Grover’s Algorithm
After playing around and experimenting with the two-qubit Grover’s Algorithm, we can take it a step further and try out a three-qubit version. In this algorithm, we will have two winner states, ⎪w〉=⎪101〉and⎪w〉=⎪110〉, instead of one.
Initialization
We have to initialize everything again, which includes creating a new circuit with three qubits (instead of two), as well as redefining the oracle and creating a more generalized diffuser for any number of qubits.
We change the value of the variable n to 3 (since we now have three qubits), and recreate our quantum circuit with n=3 qubits. Then we initialize it with out Initialize function, which we created at the beginning.
You may be wondering, what is the oracle_ex3 and the diffuser(n)? The oracle_ex3 is simply the Oracle Matrix specific to three qubits, and the diffuser(n) is the generalized diffuser mentioned previously. We’ll see more about this soon!
Applying the Oracle Matrix and Diffuser
Once again, we apply the Oracle Matrix to the three qubits, which, this time, consists of two Controlled-Z gates: one for the first and third qubits, and one for the second and third qubits. We can return the oracle as a gate for convenience.
Now, we apply the generalized diffuser for n qubits, which takes in one parameter: nqubits, the number of qubits. It then applies an H gate to each qubit, followed by X gates to each qubit, then an MCZ gate (which consists of an H gate to the last qubit, and MCT gate for each qubit and the last qubits, and another H gate to the last qubit), followed by some more X gates and H gates. Once again, we can return the diffuser as a gate for convenience.
We can output our completed circuit to the screen. The first vertical purple rectangle is our Oracle Matrix, oracle_ex3, and the second vertical purple rectangle is our diffuser for three qubits, diffuser(3).
Simulation
Again, we can simulate our new algorithm. The process for simulation isidentical to the one used for two qubits, so I won’t explain the code too much here. The simulation produces the results, shown below. As you can see, there is about a 50–50 chance of measuring each of our winner states, which is what we’d expect.
Running on a Real Quantum Computer
Finally, we can run our three-qubit Grover’s Algorithm on a real quantum computer, once again using IBMQ and IBM Quantum Experience. The results should match up with the simulated results.
Our job is currently queued on ibmq_anthens, so we will need to wait a while. Luckily, there are only five jobs in the queue, so the wait shouldn’t take too long.
About seven minutes later, our job has successfully run!
We can see the results below. Once again, they match up with what the simulation outputted. The winner states each have about the same probability of being measured, and are both somewhat close to a 50–50 split. The other measurements are due to errors in the quantum computation and slight decoherence.
Final Remarks and Conclusion
Congratulations! Not only have you created a two qubit Grover’s Algorithm, but as three-qubit version as well! In addition, you also successfully defined two pretty complex quantum functions! You can run it as many times as you want, and debug as well.
This was my first time creating a quantum algorithm using Qiskit! I experienced many difficulties, such as bugs in the code and not understanding what certain functions did, especially since I was too lazy to read the Qiskit docs for all the functions and et cetera. Nevertheless, it was an interesting experience and I enjoyed it a lot! I will probably try a harder algorithm, such as Shor’s Algorithm in the near future, so get prepared for a new article coming up soon!
Extras and Resources
If you want to learn more about quantum computing, there are numerous courses out there on this topic! Below I have listed a few (the list is not exhaustive).
- https://www.coursera.org/learn/quantum-computing-algorithms
- https://www.coursera.org/learn/quantum-computing-lfmu
- https://www.coursera.org/learn/physical-basis-quantum-computing
There are also many courses on EdX and Udemy as well, so take a look!
Once again, here’s the link to the tutorial. By the way, if you want a challenge for yourself, you can also attempt the Grover’s Algorithm Sudoku at the end! I tried it, and it was super fun! I think you’ll enjoy it too!
Lastly, here’s the code for the algorithm. Please note that it only works in IBM Quantum Experience Quantum Lab, so if you run it in repl.it, it won’t actually work. Also please don’t just copy and paste it because then you won’t learn anything.
Feedback?
Do you have any feedback for me? Is there anything that wasn’t clear enough? Please don’t hesitate to reach out and tell me on LinkedIn, feedback is always appreciated! In the meantime, stay tuned for more articles coming soon!
