On this section we’ll dive into the idea behind how Grover’s quantum search algorithm finds a marked element in an unstructured database with a question complexity of:

The algorithm describes tips on how to apply a set of quantum operators or quantum gates in a quantum circuit on n qubits that are initially in a zero state:

The quantum circuit will transform the initial n qubit state right into a final n qubit state which is the same as the goal quantum state with a high probability. Then, measuring the ultimate quantum state will return the goal ID bit-string x₀ (with high probability).

The Oracle Operator

The oracle operator is the quantum gate equivalent of the black-box function f(x) utilized in the classical algorithm. The oracle will act on an n-qubit quantum state |x⟩ and add a negative phase to the state if it is the same as the goal state |x₀⟩ and leave it unchanged otherwise:

To see how that is linked to the black-box function f(x) we may also represent the oracle operation as:

If we give it some thought fastidiously, we will see that the oracle operator is similar to the diagonal identity operator (which in matrix form has only diagonal terms that are equal to 1) with the element corresponding to the goal state |x₀⟩ possessing a negative sign. As such, we will write the oracle operator as:

A fast check can confirm that this representation is indeed equal to the 2 above it.

The oracle is the core of the algorithm and defines the computational problem being solved. In essence, it simply verifies potential solutions to the given problem. As such, Grover’s algorithm might be used to resolve any problem which might be represented using a black-box function and so it could possibly be applied to far more than simply unstructured search problems.

The Phase Inverter Operator

The phase inverter operator is comparable to the oracle operator, except quite than adding a negative phase to the state if it’s equal to the goal state |x₀⟩ it as an alternative adds a negative phase to the state if it’s equal to the n-qubit zero state |0⟩. As before, the state is left unchanged otherwise.

The phase inverter operator can be expressed because the diagonal identity operator with the element corresponding to the zero state possessing a negative phase:

Grover’s Operator

Grover’s operator D is obtained by applying a Hadamard operator on all n qubits before and after applying the phase inverter operator after which adding a negative phase, i.e. adding a negative sign. It may possibly be expressed as follows:

Where the Hadamard operator simply puts all n qubits into an equal superposition of possible N = 2ⁿ states. We will substitute in our alternative representation for the phase inverter operator to acquire:

Where the motion of the Hadamard operation on a single qubit within the zero state puts it into the next single qubit superposition state:

Inversion and Reflection Operator Representations

To get a clearer and more intuitive understanding of the motion of the oracle operator, phase inverter operator, and Grover’s D operator on the n-qubit quantum state let’s first take a temporary detour to explore two general classes of operators often called inversion and reflection operators.

As you would possibly guess, inversion and reflection operators perform an ‘inversion’ or a ‘reflection’ of a quantum state about another quantum state |𝜓⟩. They’re expressed as follows:

To see how these two types of operators act on a state allow us to consider their motion on an arbitrary state which is decomposed into orthogonal components:

Inversion

It’s easy to ascertain that applying the inversion operator to the arbitrary state above ends in the next:

We will see that the the sign up front of the |𝜓⟩ component of the state has been flipped. This corresponds to a ‘reflection’ of the general state |𝜙⟩ in regards to the orthogonal |𝜓⟩ state. We will visualise this below: