2. Parallelism: Deutsch-Jozsa

The Deutsch-Jozsa Algorithm

This was the first "proof of concept" that a quantum computer could do something faster than a classical one.

The Problem: You have a black box function $f(x)$ that takes a bit string input and outputs 0 or 1. The function is guaranteed to be either:

• Constant: Always outputs 0 or always outputs 1.
• Balanced: Outputs 0 for half the inputs and 1 for the other half.

The Solution:

• Classical: You might need to check $2^{n-1} + 1$ inputs to be sure.
• Quantum: You can determine the answer with exactly ONE query.

It works by creating a superposition of all possible inputs, querying the function once, and using interference to separate the "constant" case from the "balanced" case.