Grover search algorithm
The first step in Grover algorithm is the initialization this bring all the bits (with Hadamard gate ) in superposition. Then we have the oracle this defines the search action by means of phase inversion. After the Hadamard’s all possibilities are there. The oracle defines the search pattern and will select the right qubit by inverting its phase.
The second step of the Grover algorithm amplifies this result and the answer can be measured. We have an extra ancilla bit starting in the state minus.
As an example, we will start with the search pattern “110”. For the oracle Uf and the second U, we will use a Toffoli gate. For the 3 bit input, a 3 qubit Toffoli gate is needed and furthermore, the pattern must be computed and uncomputed.
Now we need 4 qubits, one for the extra ancilla bit, can we do with 3 qubits?
Therefore we need a Toffoli gate build with basic gates and initialised with Hadamard gate for all qubits. Now the Toffoli gate is in a 3 qubit entangled state.
Let’s try an optimal Grover algorithm on the IBM Quantum computer with this quantum circuit.
Grover algorithm in the simulator with output 110
Grover algorithm in a websimulator