Questions: Deutsch-Jozsa Algorithm

Question 1

The Deutsch-Jozsa algorithm achieves an exponential speedup over classical algorithms for determining whether a function is constant or balanced. What type of speedup is this?

• A. Exponential speedup over all classical algorithms including probabilistic ones
• B. Exponential speedup over deterministic classical algorithms only — a randomized algorithm can solve it with high probability in O(1) queries
• C. Polynomial speedup similar to Grover's algorithm
• D. No speedup — it is primarily of theoretical interest

Answer: (B)

The Deutsch-Jozsa problem has an exponential quantum vs. deterministic-classical separation, but a randomized classical algorithm can solve it with high probability using only O(1) queries (sample a few random inputs; if you ever see both 0 and 1 outputs, it's balanced). The significance is theoretical: it was the first proof that quantum query complexity can be exponentially smaller than deterministic query complexity. The practical speedup over randomized algorithms is constant, not exponential.

Question 2

In the Deutsch-Jozsa circuit, the ancilla qubit is initialized to |1> rather than |0> before the Hadamard is applied. This is an arbitrary convention with no effect on the algorithm.

• T. True
• F. False

Answer: False

Initializing the ancilla to |1> and then applying H produces |-> = (|0> - |1>)/sqrt(2). When the oracle Uf acts on |x>|-> it produces (-1)^f(x)|x>|->. This phase kickback encodes f(x) into the phase of |x> rather than into the ancilla state. If the ancilla were initialized to |0>, the oracle would write f(x) into the ancilla, entangling it with the input register and preventing the interference that the algorithm relies on.

Question 3

Explain the role of interference in the Deutsch-Jozsa algorithm — specifically, why does the final Hadamard transform on the input register produce |0...0> for constant functions but never |0...0> for balanced functions?

Model answer: After the oracle, each computational basis state |x> has acquired a phase (-1)^f(x). The final Hadamard transform on n qubits maps each |x> to a superposition over all basis states. The amplitude of |0...0> in the output is the sum of (-1)^f(x) over all x, divided by 2^n. If f is constant, all phases are the same and the sum is +/-1, giving probability 1 for |0...0>. If f is balanced, half the phases are +1 and half are -1, so the sum is exactly zero, giving probability 0 for |0...0>.

This is a clean example of constructive and destructive interference. The Hadamard transform recombines all 2^n amplitude paths, and the phases imposed by the oracle determine whether they add up or cancel. A constant function produces coherent addition (constructive interference at |0...0>), while a balanced function produces perfect cancellation (destructive interference at |0...0>). This interference pattern lets a single measurement distinguish the two cases with certainty.