Basic Amplitude Amplification

In the previous lesson Using Grover’s Algorithm, we conceptualized how Grover’s search algorithm works. It’s also important to translate it into a working quantum circuit.

Grover’s algorithm consists of two major components. First, the oracle identifies and marks a favorable state. Second, the diffuser amplifies the amplitude of good states.

The first stretch of mind involves not thinking in qubits but thinking in states. Of course, qubits are the computational unit we work with. The possible states of a multi-qubit system depend on the qubits we use. Important visualizations of a quantum system, such as the Bloch sphere, build upon the qubit.

We also must keep in mind an essential feature of qubits. We can entangle qubits, and we can’t represent two entangled qubits by two separated qubits anymore. Two entangled qubits share their states. We can’t represent one without the other because if we measure one of the qubits, the other’s state inevitably changes, too.

Moreover, the power of quantum computing lies in the fact that qubits not only form states, but also that all their states can be worked on simultaneously. So, rather than thinking in qubits, we need to think in states.

Let’s start with the simplest case of Grover’s algorithm. We have a single qubit withtwo possible states, on and off, $|1\rangle$ and $|0\rangle$.

The first step in Grover’s algorithm is always the same. We put all qubits into an equal superposition so that each state has the same amplitude and, thus, the same measurement probability. We achieve this through the Hadamard gate.

Now, both possible states, $|0\rangle$ and $|1\rangle$ have a probability of 0.5 each.