Module 2: The Deutsch-Jozsa Algorithm

1. The Problem for Software Engineers

Imagine you are testing a third-party microservice API that accepts an $n$-bit binary payload and returns a single boolean:

def evaluate_flag(x: int) -> bool:
    # Black-box implementation
    ...

The provider promises that this service adheres to one of two behaviors:

• Constant: It returns the exact same value (always 0 or always 1) for every single possible input.
• Balanced: It returns 0 for exactly half of the possible inputs, and 1 for the other half.

In classical computing, even if you test 100 inputs and all return 0, you cannot be certain the 101st input won't return 1. In the worst case, you must check more than half the search space.

The Deutsch-Jozsa algorithm determines whether the function is constant or balanced in exactly 1 single evaluation, regardless of whether $n=3$ or $n=1,000,000$!

2. How the Quantum Magic Works (Without Physics Jargon)

How can a single call know the global property of an entire function? The secret is a technique called Phase Kickback combined with Hadamard Interference.

Step-by-Step Execution:

1. Initialize in Superposition: All $n$ input qubits start in $\vert 0\rangle$ and pass through a Hadamard ($H$) gate, creating an equal superposition of all $2^n$ possible inputs simultaneously.
2. The Ancilla Trick (Phase Kickback): A helper qubit (ancilla) is initialized to $\vert 1\rangle$ and flipped with $H$ into $\vert-\rangle = \frac{\vert 0\rangle - \vert 1\rangle}{\sqrt{2}}$. When the oracle gate $U_f$ evaluates $\vert x\rangle \vert y \oplus f(x)\rangle$, the value $f(x)$ is "kicked back" as a phase factor $(-1)^{f(x)}$ onto the input state!
3. Inverse Hadamard Transform: A second layer of $H$ gates converts the phase differences back into measurable bit amplitudes.
4. The Decisive Readout Rule:
   • If $f$ is Constant: Every input received the same phase. All paths constructively interfere onto $\vert 00\dots0\rangle$. You will measure all zeros with 100% certainty.
   • If $f$ is Balanced: Exactly half the inputs received a $+1$ phase and half received a $-1$ phase. They completely cancel each other out at $\vert 00\dots0\rangle$! You will measure any non-zero bitstring.

3. Running Deutsch-Jozsa on Quanifi

In Quanifi, this entire workflow runs as an automated data pipeline inside NiFi 2.11:

Figure 2.2: The Deutsch-Jozsa pipeline in Quanifi (NiFi 2.11). ↔ Scroll horizontally to inspect processors • Click to enlarge

Pipeline Components:

• DJ — Trigger (GenerateFlowFile): Emits a trigger FlowFile to initiate the test run.
• Qrisp Deutsch-Jozsa (QrispDeutschJozsa): High-level quantum processor. It synthesizes the oracle, compiles the circuit into OpenQASM 2.0, executes the statevector simulation, and attaches verdict attributes.
• DJ — Report (QuanifiReport): Takes the completed FlowFile, generates a full visual HTML audit card with circuit diagram and probability distributions, and writes it to reports/qrisp-deutsch-jozsa.html.

Triggering the Flow:

1. Make sure Docker is running (docker compose up -d).
2. Open NiFi at https://localhost:8443/nifi and enter the Qrisp Components & Textbook Algorithms group.
3. Right-click on DJ — Trigger and click Run Once (or start and immediately stop it).
4. Watch the FlowFile move across the queue into Qrisp Deutsch-Jozsa and then into DJ — Report. In ~2 seconds, all queues return to 0.

4. How to Read and Interpret the Results

After the flow finishes, open the generated HTML report file in your browser:

open reports/qrisp-deutsch-jozsa.html

Look at the resulting metadata attributes card: