One Query to Rule Them All: The Deutsch-Jozsa Algorithm

Project Overview:

Imagine someone hands you a mystery function that takes a number and outputs either 0 or 1, and tells you it is either constant, meaning it always outputs the same value no matter what you put in, or balanced, meaning it outputs 0 for exactly half of all possible inputs and 1 for the other half. Classically, in the worst case, you would need to check more than half of all possible inputs to be completely sure which type it is. The Deutsch-Jozsa algorithm, one of the earliest algorithms to prove quantum computers can outperform classical ones, solves this with a single query, regardless of how large the input space is. In this project you will build the circuit yourself and watch it correctly identify a mystery function in exactly one shot.

Materials Required:

A computer with internet access

A free Google account, to use Google Colab, no installation needed

Basic comfort reading Python

Background: How the Algorithm Actually Works

The trick relies on putting all possible inputs into superposition at once, then using a special version of the mystery function, called an oracle, that marks certain outcomes by flipping their sign instead of literally changing their value. This is combined with a mathematical trick called phase kickback, where information about the function gets encoded into the phase of the qubits rather than their measured value.

After running the inputs through the oracle, the algorithm applies Hadamard gates again to convert that hidden phase information back into something measurable. If the function was constant, all the qubits collapse back to exactly 0 when measured. If the function was balanced, at least one qubit reads as 1. This single measurement tells you the answer with complete certainty, no repeated trials needed.

Step by Step Instructions

Set up your notebook.

Go to Google Colab at colab.research.google.com and create a new notebook.

Install Qiskit.

Type the following into a code cell and run it:

pip install qiskit qiskit-aer

Build the constant oracle first.

We will use 3 input qubits plus 1 helper qubit, called the ancilla. A constant oracle does nothing at all to the qubits, since the output never depends on the input.

from qiskit import QuantumCircuit

from qiskit_aer import AerSimulator

def deutsch_jozsa(oracle_type):

qc = QuantumCircuit(4, 3)

Code

Run it with a constant function first.

qc_constant = deutsch_jozsa("constant")

print(qc_constant.draw())

simulator = AerSimulator()

result = simulator.run(qc_constant, shots=1000).result()

counts = result.get_counts()

print("Constant function result:", counts)

Check the output.

You should see essentially all 1000 shots landing on 000. This single, repeated result is how you know the function is constant, since a balanced function could never produce this pattern.

Now run it with a balanced function.

qc_balanced = deutsch_jozsa("balanced")

result = simulator.run(qc_balanced, shots=1000).result()

counts = result.get_counts()

print("Balanced function result:", counts)

Check this output too.

You should see anything other than 000, spread across other 3 bit combinations. Getting any nonzero result instantly tells you the function was balanced, again from a single query.

Stretch step, build your own custom balanced oracle.

Try changing which qubits get the cx gates in the balanced branch, for example using only qc.cx(0, 3) and qc.cx(2, 3) instead of all three, then rerun and confirm you still reliably get a nonzero, non 000 result, just a different specific pattern.

Congratulations, you just implemented a real quantum algorithm that provides a proven, exponential speedup over the best possible classical approach, and demonstrated it correctly identifying a hidden function's type from a single measurement.

Fun Fact:

The Deutsch-Jozsa algorithm from 1992 is considered one of the first concrete proofs that quantum computers could theoretically outperform classical computers on a specific task, years before more famous algorithms like Shor's factoring algorithm made quantum computing a topic of serious real world interest, particularly in cryptography and cybersecurity.