Think if you have a problem set of unordered list and you have many combinations of solutions, how would you solve the problem?
This is where Grover's search Algorithm comes into play. Basically, this algorithm helps you to minimize the combinations of solutions and cut out the ones that are not a part of solution. So you input all the problem set in the Grover's algorithm and it uses a oracle function to process that input and gives you the output. If the output is 1, then you got your solution. If it's 1, then you keep giving your input again and again until you find the result 1.
About "Oracle" function: Amplitude amplification is a general purpose quantum algorithm, or subroutine, that can be used to obtain a quadratic speedup over a handful of classical algorithms. Grover’s algorithm was the first to demonstrate this speedup on unstructured search problems. Formulating a Grover's search problem requires an oracle function that marks one or more computational basis states as the states we are interested in finding, and an amplification circuit that increases the amplitude of marked states, consequently suppressing the remaining states.
Example
The circuit above has a string of 3 bits as an input for a certain problem. The output given depends on whether the input string is a solution to the problem or not.
The result of this checking computation will still be either True or False, but the behaviour of this circuit is slightly different to how you might expect. To use this circuit with Grover's algorithm, we want the oracle to change the phase of the output state by 180° (i.e. multiply by -1) if the state is a solution. This is why Qiskit calls the class 'PhaseOracle'.
Note: PhaseOracle means the Oracle function shifts the phase of the output state by multiplying -1 to the output.
As it shows in the picture, if the output is a solution there is a minus (-) sign in the front of the state. Otherwise, there is not.
Looking at the matrix above, we can see that the rows/columns corresponding to the binary strings 000, 011, and 101 have -1 entries on the diagonal. This means that when the quantum state corresponding to these strings is input into the oracle, the oracle flips the phase of the state (multiplies it by -1), which is a key step in Grover's algorithm for marking the solutions.
The matrix is an 8x8 matrix, which means it can represent all 2^3 (or 8) possible combinations of 3-bit strings. The positions of the -1s in the matrix would be:
000 corresponds to the first position (row 1, column 1),
011 corresponds to the fourth position (row 4, column 4),
101 corresponds to the sixth position (row 6, column 6).
Overview of Grover's algorithm
Now we understand the problem, we finally come to Grover’s algorithm. Grover’s algorithm has three steps:
Here's a quick rundown of my experiment with Grover's Algorithm (Refer to Qiskit documentation if you want to learn more)
Here I initiated the marked states and set the variable "oracle" by calling "grover_oracle" and setting marked_states inside of it.
Next, we can again use Qiskit's tools to create a circuit that does steps 2 & 3 for us.
Now we implement the oracle function in the circuit
Here the marked states means the combinations we are trying on the ciruit to see if it's the solution or not. Here, the marked states are 101,100 & 110. So you can see on the histogram that these states has the highest bars. Quantum computers can have randomness in their results, so it's common to repeat the circuit a few times. This circuit was repeated 1024 times, which is the default number of times to repeat a circuit in Qiskit.
Hope you enjoyed this short blog on grover's algorithm. Leave a comment to support.
Top comments (0)