This project is made as a part of the IITR QCG- Open Summer Project, 2022. It involves solving a boolean satisfiability problem (dinner problem) using Grover's algorithm.
- Description / Internal Working
- Features
- Tech Stack / Dependencies
- Getting Started / Setup
- User Guide
- Challenges Faced and Learnings
- Resources
- Bug Reporting
- Feature Request
This project aims at solving a dinner problem (boolean satisfiability problem ) using Grover's algorithm.
SAT(Boolean Satisfiability Problem) is the problem of determining if there exists an interpretation that satisfies a given boolean formula. It asks whether the variables of a given boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable.
A Boolean SAT problem can be solved by determining all the input combinations that fit into a boolean function such that the output is true. Since searching through the combinations is needed, Grover's algorithm is used.
Grover’s algorithm, also known as the quantum search algorithm, is a quantum algorithm designed by Los Grover in 1996 to search for an element in an unsorted array quadratically faster ( O(sqrt(N) ) : Time Complexity) than the classical linear search for large datasets. This project aims at solving a particular boolean satisfiability problem (dinner problem) using Grover's algorithm.
Frank wants to throw a dinner party to celebrate Alice and Bob’s engagement. He is also considering inviting their mutual friends Charles, Dave and Eve. However, he is aware that Charles will come to the party only if Dave comes without Eve. Frank wants to know what possible combinations of invitations he can write for his friends Alice, Bob, Charles, Dave and Eve.
Help Frank calculate all the possible combinations using Grover’s algorithm.
- Create 5 quantum channel labelled as qi, i ∈ {0, 1, 2, 3, 4}. where qo represents presence of Alice, q1 represents presence of Bob, q2 represents presence of Charles, q3 represents presence of Dave, q4 represents presence of Eve. Apply Hadamard gate to each channel - it creates superposition of every possible states.
- Create an oracle that flips a state if it satisfies the problem statement.
- Reflect all the states about the mean and amplify the amplitudes of the possible states that satisfy the problem statement.
- Run the final circuit on Statevector Simulator Backend - to calculate amplitudes, and Qasm Simulator - to print histogram of the frequency of the states.
- The amplitudes of the states are calculated by running the circuit on a Statevector Simulator Backend.
- Final Grover circuit drawn in a image type file (.png)
- The possible counts of all the states is measured by running the circuit on a Qasm Simulator and stored in counts.txt file.
- The histogram of the frequency of all the states is also plotted.
- Add more features...
Python : The complete project is written in python programming language.
Qiskit : Provides tools for creating and manipulating quantum programs and running them on prototype quantum devices on IBM Quantum Experience or on simulators on a local computer.
Numpy : To work with matrices.
matplotlib : Plotting library for python, used to plot figures.
Visual Studio Code : Editor used in the project.
- Clone this repository.
git clone https://github.com/ansh25saini/Grover_Algorithm_Project.git- Install the given requirements, one-by-one-
pip3 install jupyter
pip3 install qiskit
pip3 install matplotlibThe amplitudes of the states are calculated by running the circuit on a Statevector Simulator Backend.
Statevector([-0.08562621-1.64517430e-16j, -0.08562621-5.70308882e-16j, -0.08562621-4.59238028e-16j, -0.08562621-5.47310893e-16j, -0.08562621-1.81524369e-16j, -0.08562621-4.97960940e-16j, -0.08562621-4.86993603e-16j, -0.08562621-5.25327667e-16j, -0.08562621-3.42227314e-16j, -0.08562621-5.62145286e-16j, -0.08562621-5.23634951e-16j, -0.08562621-6.33539263e-16j, -0.08562621-3.31877132e-16j, -0.08562621-5.00810593e-16j, -0.08562621-5.62029814e-16j, -0.08562621-5.03945867e-16j, -0.08562621-9.25056760e-17j, -0.08562621-4.08091507e-16j, -0.08562621-3.14367887e-16j, -0.08562621-3.64276836e-16j, -0.08562621-2.58698834e-16j, -0.08562621-3.01049095e-16j, -0.08562621-3.10898440e-16j, -0.08562621-2.34740755e-16j, 0.4005097 +2.19258526e-15j, 0.4005097 +2.54512603e-15j, 0.4005097 +2.01811652e-15j, 0.4005097 +2.18576796e-15j, -0.08562621-4.50684960e-16j, -0.08562621-4.60023861e-16j, 0.4005097 +2.33360524e-15j, -0.08562621-4.77036923e-16j], dims=(2, 2, 2, 2, 2))
The final Grover circuit in (.png) type file
The counts of all the possible states, used to print histogram, is present in counts.txt file in the project directory. Download Link
The histogram of the frequency of all the states is also included. It is calculated using the counts, which are measured by running the circuit on a Qasm Simulator.
- Learnt about qubits, quantum gates and quantum circuits.
- Got familiar with Qiskit and Grover's Algorithm.
- Faced major challenges in implementing diffuser for amplitude amplification.
- Learnt about how matplot library can be used to plot figures.
- Help from IIT Roorkee Quantum Computing Group
- Qiskit Textbook
- Grover's Algorithm
- Grover's Algorithm Qiskit Textbook
- SAT Problem using Grover's Algorithm
Feel free to open an issue on GitHub if you find bugs.
- Feel free to open an issue on GitHub to add any additional features you feel could enhance this project.
- You can also discuss and provide suggestions to me on LinkedIn.
if (youEnjoyed) {
⭐ starThisRepository();
}