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 quantum circuit on 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 verifies potential solutions to the given problem. 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.
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 phase inverter operator and then adding a negative phase, i.e. adding a negative sign. It can be expressed as follows:
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 ‘reflection’ of a quantum state about some other quantum state |𝜓⟩. They are expressed as follows:
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:
