Deutsch-Jozsa Algorithm in Qiskit

1. The Deutsch-Jozsa Circuit Structure in Qiskit

As we discussed previously, the algorithm has a distinct structure that we can think of as a "Hadamard sandwich." It prepares a superposition, queries the oracle, and then uses interference to get the answer. Let's outline the steps to build this in Qiskit for an $n$-bit function.

The circuit requires $n$ qubits for the input and one additional qubit, called an ancilla, for the output. So, we'll need $n+1$ qubits in total.

The general process is:

1. Initialization: Start with $n+1$ qubits in the $|0⟩$ state.
2. Ancilla Preparation: Apply an X gate to the ancilla qubit to flip it to $|1⟩$.
3. Superposition: Apply Hadamard (H) gates to all $n+1$ qubits. This puts the $n$ input qubits into an equal superposition of all possible $2^n$ states, and the ancilla qubit into the state $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$.
4. Oracle Query: Apply the quantum oracle, $U_f$.
5. Interference: Apply H gates to the first $n$ input qubits.
6. Measurement: Measure the first $n$ input qubits.

Now, let's translate this into a Qiskit circuit. The IBM Quantum Learning resource provides a very clear template for this.

The key insight is that this structure is always the same. The only part that changes depending on the specific problem is the oracle, $U_f$.

2. Building the Oracle, $U_f$

The "given oracle" in our learning outcome is the quantum circuit that implements the function $f(x)$. The oracle must be a unitary operation that acts on the input and ancilla qubits. For a function $f:\{0,1{\}}^n\to \{0,1\}$, the oracle $U_f$ performs the mapping:

where $|x⟩$ is the $n$-qubit input register, $|y⟩$ is the single ancilla qubit, and $\oplus$ denotes addition modulo 2 (a classical XOR operation).

Let's see how to build oracles for both constant and balanced functions.

Constant Oracle

A constant oracle is straightforward.

• For $f(x)=0$ for all $x$: The function is $y\oplus 0=y$. The oracle does nothing. It's an identity operation.
• For $f(x)=1$ for all $x$: The function is $y\oplus 1=\neg y$. The oracle applies an X (NOT) gate to the ancilla qubit, regardless of the input $|x⟩$.

Balanced Oracle

A balanced oracle is more interesting. There are many ways to construct one. A common example is a function that is 1 for a specific input bitstring and 0 for all others. A more structured example is a parity function, where $f(x)$ is 1 if the input string $x$ has an odd number of 1s, and 0 otherwise.

This can be implemented with a cascade of CNOT gates, where each input qubit acts as a control for a CNOT targeting the ancilla. Since a CNOT is equivalent to a controlled-XOR, this sequence effectively calculates the XOR sum (parity) of the input bits onto the ancilla.

The following resource provides excellent code examples for building various oracles.

3. Assembling and Running the Full Algorithm

Now we have the two main components: the "Hadamard sandwich" circuit and the oracle. Let's put them together. The sentdex video below offers a very hands-on walkthrough of this entire process, from defining the oracles to running the final circuit.

Let's consolidate what you've learned into a complete example. We'll implement the algorithm for $n=3$ input qubits.

Step 1: Define the Oracles

First, we create Python functions that return QuantumCircuit objects for our oracles.

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




# For n=3 input qubits, the circuit has 3+1 = 4 qubits
n = 3




# Oracle for a CONSTANT function, f(x) = 1
# This oracle flips the ancilla qubit regardless of the input.
constant_oracle = QuantumCircuit(n + 1)
constant_oracle.x(n) # Apply X gate to the ancilla qubit (at index n)
constant_oracle.name = "Constant f(x)=1"




# Oracle for a BALANCED function (parity)
# f(x) = 1 if the input has an odd number of 1s
balanced_oracle = QuantumCircuit(n + 1)



# Apply CNOT gates from each input qubit to the ancilla qubit
for qubit in range(n):
    balanced_oracle.cx(qubit, n)
balanced_oracle.name = "Balanced (Parity)"

Step 2: Build the Main Deutsch-Jozsa Circuit

Now, we create a function that takes an oracle and wraps it in the Deutsch-Jozsa algorithm structure.

def dj_circuit(oracle):
    n = oracle.num_qubits - 1



    # Create the circuit with n+1 quantum bits and n classical bits
    qc = QuantumCircuit(n + 1, n)
    



    # Prepare the ancilla in state |->
    qc.x(n)
    qc.h(n)
    



    # Apply Hadamard to all input qubits
    for qubit in range(n):
        qc.h(qubit)
    



    # Add a barrier for visualization
    qc.barrier()
    



    # Append the oracle
    qc.append(oracle, range(n + 1))
    



    # Add another barrier
    qc.barrier()
    



    # Apply Hadamard to input qubits again
    for qubit in range(n):
        qc.h(qubit)
        



    # Measure the input qubits
    qc.measure(range(n), range(n))
    
    return qc

Step 3: Run with the Constant Oracle

Let's build the circuit with the constant oracle and see the result.

# Create the full circuit
full_circuit_constant = dj_circuit(constant_oracle)
print("Circuit with Constant Oracle:")
display(full_circuit_constant.draw('mpl'))




# Simulate the circuit
simulator = Aer.get_backend('aer_simulator')



# We only need one shot to get the answer!
result = simulator.run(full_circuit_constant, shots=1, memory=True).result()
counts = result.get_counts()

print("\nResult from one shot:", counts)
plot_histogram(counts)

You should see that the measurement result is '000' with 100% certainty.

Step 4: Run with the Balanced Oracle

Now, let's swap in the balanced oracle.

# Create the full circuit
full_circuit_balanced = dj_circuit(balanced_oracle)
print("Circuit with Balanced Oracle:")
display(full_circuit_balanced.draw('mpl'))




# Simulate the circuit
result = simulator.run(full_circuit_balanced, shots=1, memory=True).result()
counts = result.get_counts()

print("\nResult from one shot:", counts)
plot_histogram(counts)

This time, the result should be anything but '000'. For the parity oracle, it willdeterministically be '111'.

The final video clip shows the same procedure for a randomly generated Deutsch-Jozsa function.

Conclusion

In this lesson, you successfully translated the abstract concepts of the Deutsch-Jozsa algorithm into a working quantum program using Qiskit. You have seen how the algorithm's power comes from a fixed quantum circuit structure that cleverly uses interference, with the problem-specific logic entirely contained within a swappable quantum oracle.

Key Takeaways:

• The Deutsch-Jozsa algorithm is implemented in Qiskit using a "Hadamard sandwich" structure around an oracle, $U_f$.
• Implementing the algorithm "for a given oracle" means building a QuantumCircuit that performs the mapping $|x⟩|y⟩\to |x⟩|y\oplus f(x)⟩$.
• Constant oracles are simple (identity or an X gate on the ancilla), while balanced oracles can be built with controlled gates like CNOTs to reflect the function's logic.
• By running the circuit just once, we can distinguish between a constant and a balanced function: a measurement of 00...0 means the function is constant, and any other result means it's balanced.

Preview of the Next Lesson:
The Deutsch-Jozsa algorithm, while a fantastic proof of concept, solves a rather contrived problem. In our next lesson, we will explore the Bernstein-Vazirani algorithm. You'll find it uses a nearly identical circuit structure, but it solves a more interesting problem: efficiently finding a hidden binary string encoded within an oracle.