Implementing Grover's Algorithm

Hello! Welcome to your next lesson on foundational quantum algorithms.

In our previous lesson, we explored the Deutsch-Jozsa algorithm. We saw how it uses quantum parallelism and interference to solve a specific problem—distinguishing constant from balanced functions—with a single query, offering an exponential speedup over any deterministic classical approach. While powerful, the problem itself is somewhat contrived.

Today, we move to a far more general and practical problem: unstructured search. Our goal is to implement Grover's search algorithm, including the construction of the oracle and diffusion operator, to find a marked item in a small unstructured database. This algorithm is a cornerstone of quantum computing, demonstrating a provable quadratic speedup over the best possible classical algorithms for searching.

We will cover:

1. The unstructured search problem and its classical limits.
2. The core components of Grover's algorithm: the oracle and the diffusion operator.
3. The underlying mechanism of amplitude amplification.
4. A hands-on implementation of a 3-qubit Grover search using Qiskit.

1. The Unstructured Search Problem

Imagine you have a large, unsorted database of $N$ items. You are looking for a specific "marked" item, and you have a function (an "oracle") that can tell you if a given item is the one you're looking for. Classically, with no other information, your only option is to check the items one by one. In the worst case, you'd check all $N$ items; on average, you'd check $N/2$. The query complexity is therefore $O(N)$.

Grover's algorithm tackles this exact problem but on a quantum computer. It can find the marked item with high probability using only $O(\sqrt{N})$ queries to the oracle. This quadratic speedup is significant for large databases.

To get a formal introduction to the problem and a high-level overview of the algorithm's structure, please watch the following segment from a lecture by Prof. John Watrous.

2. The Anatomy of Grover's Algorithm

Grover's algorithm consists of three main stages:

1. Initialization: Prepare the system in an equal superposition of all possible states.
2. Grover Iteration: Repeatedly apply the "Grover operator," which systematically increases the amplitude of the marked state.
3. Measurement: Measure the system. The outcome will be the marked state with high probability.

The heart of the algorithm is the Grover operator, $G$, which is applied iteratively. It is composed of two key sub-operations: the Oracle and the Diffusion Operator.

2.1. The Oracle ($U_f$)

The oracle's job is to "mark" the solution state(s) without revealing which one it is. It does this by applying a phase shift, typically a sign flip ($-1$), to the amplitude of the marked state. If $|w⟩$ is the marked "winner" state, the oracle $U_f$ acts as:

$$U_f|x⟩=\{\begin{array}{ll}-|x⟩& \text{if }x=w\\ |x⟩& \text{if }x\ne w\end{array}$$

This is a "phase oracle." This operation is often implemented using a multi-controlled Z gate. As you saw with the Deutsch-Jozsa algorithm, this phase flip can be achieved via phase kickback using an ancilla qubit, which makes the quantum oracle directly comparable to a classical function call.

The following paper, which reports a 3-qubit implementation on a trapped-ion quantum computer, provides excellent diagrams illustrating these two types of oracles.

2.2. The Diffusion Operator ($D$)

After the oracle flips the sign of the marked state, the diffusion operator amplifies its amplitude. This operator, often denoted $D$ or $U_s$, can be described as an "inversion about the mean." Its action is to reflect the state vector about the initial uniform superposition state $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$.

The operator has the form: $D=2|s⟩⟨s|-I$.

This mathematical form can be implemented with the following sequence of gates:

1. Apply Hadamard gates to all qubits ($H^{\otimes n}$).
2. Apply a phase flip to the $|0{⟩}^{\otimes n}$ state. This is done with a multi-controlled Z gate that is conditioned to act only on the all-zero state.
3. Apply Hadamard gates to all qubits again ($H^{\otimes n}$).

So, the Grover operator is the product of these two operations: $G=D\cdot U_f$.

3. The Mechanism: Amplitude Amplification

Why does applying $G=D\cdot U_f$ repeatedly work? The process can be understood geometrically. The state of the system can be described as a vector in a 2D plane spanned by two orthogonal vectors: the marked state $|w⟩$ and the uniform superposition of all other states, let's call it $|s^{\prime }⟩$.

1. The initial state $|s⟩$ is in this plane, very close to $|s^{\prime }⟩$ and almost orthogonal to $|w⟩$.
2. The oracle $U_f$ reflects the state vector across the $|s^{\prime }⟩$ axis.
3. The diffusion operator $D$ reflects the resulting vector across the initial state $|s⟩$ axis.

The composition of these two reflections is a rotation. Each application of the Grover operator $G$ rotates the state vector slightly closer to the marked state $|w⟩$, thereby "amplifying" its probability amplitude.

The following videos provide an excellent geometric intuition for this process.

After approximately $\frac{\pi }{4}\sqrt{N}$ iterations, the state vector will be very close to $|w⟩$, and a measurement will yield the correct answer with high probability.

4. Implementation: 3-Qubit Grover Search

Now, let's implement Grover's algorithm for a 3-qubit system ($N=8$). Our goal is to find a single marked state, which we'll choose to be $|101⟩$.

The following tutorial from IBM Quantum Learning provides the necessary code building blocks. We will adapt them for our specific problem.

Step 1: Initialization

First, we need a function to initialize our $n$ qubits into a uniform superposition state.

from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram
import numpy as np

def initialize_s(qc, qubits):
    """Apply a H-gate to each qubit in the register."""
    for q in qubits:
        qc.h(q)
    return qc

Step 2: The Oracle for $|101⟩$

Next, we construct the oracle. We need a circuit that flips the phase of the $|101⟩$ state and leaves all other states unchanged. A controlled-controlled-Z (CCZ or Toffoli-Z) gate flips the phase of $|111⟩$. We can adapt it to target $|101⟩$ by flipping the middle qubit's basis before and after the CCZ.

def oracle(qc, qubits):
    """Oracle that marks the |101> state."""
    # Flip the 0 to a 1 for the middle qubit
    qc.x(qubits[1])
    
    # Apply a controlled-controlled-Z gate
    qc.h(qubits[2])
    qc.ccx(qubits[0], qubits[1], qubits[2])
    qc.h(qubits[2])
    
    # Flip the middle qubit back
    qc.x(qubits[1])
    
    return qc

Step 3: The Diffusion Operator

Now, we build the diffusion operator $D=H^{\otimes n}(2|0⟩⟨0|-I)H^{\otimes n}$. The central part, $2|0⟩⟨0|-I$, flips the phase of the $|000⟩$ state. This is a CCZ gate surrounded by X-gates on all control qubits.

def diffusion_operator(qc, qubits):
    """Apply the diffusion operator (inversion about the mean)."""
    # Apply H-gates
    for q in qubits:
        qc.h(q)
    
    # Apply X-gates
    for q in qubits:
        qc.x(q)
        
    # Apply a controlled-controlled-Z gate
    qc.h(qubits[2])
    qc.ccx(qubits[0], qubits[1], qubits[2])
    qc.h(qubits[2])
    
    # Apply X-gates
    for q in qubits:
        qc.x(q)
        
    # Apply H-gates
    for q in qubits:
        qc.h(q)
        
    return qc

Step 4: Assembling the Full Circuit

For $N=8$ items and $M=1$ solution, the optimal number of iterations is $k\approx \frac{\pi }{4}\sqrt{\frac{N}{M}}=\frac{\pi }{4}\sqrt{8}\approx 2.2$. The closest integer is 2, so we will apply the Grover operator twice.

# Define the number of qubits
n = 3
qubits = list(range(n))

# Create the circuit
grover_circuit = QuantumCircuit(n)

# 1. Initialization
grover_circuit = initialize_s(grover_circuit, qubits)
grover_circuit.barrier()

# 2. Grover Iterations
num_iterations = 2
for _ in range(num_iterations):
    grover_circuit = oracle(grover_circuit, qubits)
    grover_circuit.barrier()
    grover_circuit = diffusion_operator(grover_circuit, qubits)
    grover_circuit.barrier()

# 3. Measurement
grover_circuit.measure_all()

# Display the circuit
grover_circuit.draw('mpl')

This circuit implements a 3-qubit Grover search for the state |101⟩. It begins with Hadamard gates for initialization, followed by two iterations of the Grover operator (oracle and diffusion), and concludes with measurement.

Step 5: Simulation

Let's run the circuit on a simulator and check the results.

# Simulate the circuit
backend = Aer.get_backend('qasm_simulator')
result = execute(grover_circuit, backend, shots=1024).result()
counts = result.get_counts()

# Display the results
plot_histogram(counts)

Simulation results for the 3-qubit Grover search. As expected, the marked state |101⟩ is measured with overwhelmingly high probability after two iterations.

The simulation confirms that our circuit successfully finds the marked state $|101⟩$.

Conclusion

In this lesson, we have constructed and implemented Grover's search algorithm, a pivotal quantum algorithm that provides a real-world advantage over classical methods.

Key Takeaways:

• Grover's algorithm solves the unstructured search problem with a query complexity of $O(\sqrt{N})$, a quadratic speedup over the classical $O(N)$.
• The algorithm operates through amplitude amplification, a process driven by the iterative application of the Grover operator.
• The Grover operator consists of two parts: an oracle that flips the phase of the solution state, and a diffusion operator that performs an "inversion about the mean," collectively rotating the state vector towards the solution.
• We successfully implemented a 3-qubit version in Qiskit, building the oracle and diffusion operator from basic gates and verifying the result through simulation.

In our next lesson, we will formalize the analysis of the algorithm's performance. We will derive the quadratic speedup by geometrically analyzing the state's rotation, calculating the precise angle of rotation per iteration and determining the optimal number of queries to maximize the success probability.