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

The algorithm describes how to apply a set of *quantum operators or *** quantum gates** in a

**on**

*quantum circuit**n*qubits which are initially in a

**:**

*zero state*The quantum circuit will transform the *initial**n* qubit state into a *final**n *qubit state which is equal to the target quantum state with a ** high probability**. Then, measuring the final quantum state will return the target 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) *used 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 equal to the target state

*|**x₀*

**⟩**and leave it unchanged otherwise:

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

If we think about it carefully, we can see that the oracle operator is equivalent to the *diagonal identity operator*** **(

*which in matrix form has only diagonal terms which are equal to 1*) with the element corresponding to the target state

*|**x₀*

**⟩**possessing a negative sign. As such, we can write the oracle operator as:

A quick check can verify that this representation is indeed equal to the two above it.

The oracle is the ** core of the algorithm** and defines the computational problem being solved. In essence, it simply

**. As such, Grover’s algorithm can be used to solve any problem which can be represented using a black-box function and so it can be applied to much more than just unstructured search problems.**

*verifies potential solutions to the given problem*## The Phase Inverter Operator

The phase inverter operator is similar to the oracle operator, except rather than adding a negative phase to the state if it’s equal to the target state *|**x₀***⟩ **it instead *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 also be expressed as 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

**and then adding a negative phase, i.e. adding a negative sign. It can be expressed as follows:**

*phase inverter operator*Where the Hadamard operator simply puts all *n *qubits into an ** equal superposition **of possible

*N = 2ⁿ*states. We can substitute in our alternative representation for the phase inverter operator to obtain:

Where the action of the Hadamard operation on a single qubit in the zero state puts it into the following single qubit superposition state:

## Inversion and Reflection Operator Representations

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

As you might guess, inversion and reflection operators perform an ** ‘inversion’** or a

**of a quantum state about some other quantum state |𝜓⟩. They are expressed as follows:**

*‘reflection’*To see how these two forms of operators act on a state let us consider their ** action on an arbitrary state** which is

**:**

*decomposed into orthogonal components*## Inversion

It’s easy to check that applying the inversion operator to the arbitrary state above results in the following:

We can see that the the sign in front of the |𝜓⟩ component of the state has been flipped. This corresponds to a ** ‘reflection’** of the overall state |𝜙⟩ about the orthogonal |𝜓⟩ state. We can visualise this below: