Deutsch–Jozsa as HSP

The Deutsch–Jozsa algorithm is historically the first quantum algorithm to demonstrate an exponential separation over deterministic classical computation. It solves a promise problem — is a black-box function constant or balanced? — in a single query where a classical deterministic algorithm needs up to $2^{n-1}+1$ queries. Once you understand the Hidden Subgroup Problem (HSP), you gain a cleaner view of why the algorithm works: the constant case maps directly onto an HSP instance over the group $\mathbb{Z}_2^n$ , and the algorithm's structure is that of the standard abelian HSP circuit.

The group structure

Recall from the previous lessons that the HSP asks us to identify a hidden subgroup $H$ of an abelian group $G$ given oracle access to a function $f : G \to S$ that is constant on cosets of $H$ and takes distinct values on distinct cosets.

For the Deutsch–Jozsa problem the setting is:

Group: $G = \mathbb{Z}_2^n$ , the $n$ -bit strings under bitwise XOR (addition mod 2).
Promise: The oracle $f : \mathbb{Z}_2^n \to \{0,1\}$ is either constant or balanced (equal number of 0s and 1s).
Goal: Decide which case holds using as few queries as possible.

The key observation is that the two cases relate differently to the subgroup structure of $\mathbb{Z}_2^n$ :

| Case | Hidden subgroup $H$ | Cosets | |------|--------------------|--------| | Constant | All of $\mathbb{Z}_2^n$ | Only one coset: $G$ itself | | Balanced | No HSP subgroup structure | — |

When $f$ is constant, it is trivially constant on every coset of $G$ (since there is only one coset, $G$ itself) — this is a valid HSP instance with $H = G$ . When $f$ is balanced, the function takes both values $0$ and $1$ equally, and there is in general no proper subgroup $H$ such that $f$ is constant on every coset of $H$ with distinct cosets mapping to distinct values. The balanced case is therefore not a standard HSP instance; instead, it is identified by the quantum algorithm via amplitude cancellation (see the circuit section below).

The quantum subroutine is Fourier sampling

The standard HSP algorithm for abelian groups runs the following circuit:

Prepare an equal superposition over all group elements: apply $H^{\otimes n}$ to $|0^n\rangle$ .
Query the oracle in superposition to entangle the function value with the input register.
Discard (trace out) the output register.
Apply the Quantum Fourier Transform (QFT) over $G$ to the input register.
Measure.

For $G = \mathbb{Z}_2^n$ the QFT is again $H^{\otimes n}$ (since the Hadamard transform is its own inverse and coincides with the Fourier transform over $\mathbb{Z}_2^n$ ). The resulting circuit is exactly the Deutsch–Jozsa circuit:

|0^n\rangle|1\rangle \;\xrightarrow{H^{\otimes n+1}}\; \frac{1}{\sqrt{2^n}}\sum_{x \in \mathbb{Z}_2^n}|x\rangle\otimes\frac{|0\rangle - |1\rangle}{\sqrt{2}} \;\xrightarrow{U_f}\; \frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle\otimes\frac{|0\rangle - |1\rangle}{\sqrt{2}} \;\xrightarrow{H^{\otimes n}}\; \cdots

After the final $H^{\otimes n}$ , the amplitude of the all-zeros string $|0^n\rangle$ is

\alpha_{0^n} = \frac{1}{2^n}\sum_{x \in \mathbb{Z}_2^n} (-1)^{f(x)}.

If $f$ is constant, every term in the sum has the same sign, so $|\alpha_{0^n}|^2 = 1$ : we measure $0^n$ with certainty. If $f$ is balanced, the positive and negative terms cancel exactly, so $\alpha_{0^n} = 0$ : the all-zeros outcome never appears.

Why the HSP lens clarifies the algorithm

From the HSP perspective, the measurement in step 5 samples from the dual group $\hat{G} = \mathbb{Z}_2^n$ . The output distribution concentrates on characters $\chi$ that are constant on $H$ — exactly the characters that are trivial on $H$ , i.e. elements of the annihilator $H^\perp$ of $H$ in $\hat{G}$ .

Constant case ( $H = G$ ): The Fourier-sampling theorem applies directly. $H^\perp = \{0^n\}$ (the only character trivial on all of $G$ ), so the only measurable outcome is $0^n$ .
Balanced case: A general balanced function does not satisfy the strict HSP promise for any nontrivial subgroup (distinct cosets need not have distinct values). The outcome $P(0^n) = 0$ follows instead from the amplitude cancellation derived above: the equal number of $+1$ and $-1$ phases sum to zero.

Relationship to Simon's problem

Simon's problem (the next lesson) is the natural next step in the same family: instead of deciding whether $f$ is constant (i.e., $H = G$ ) or not, we are given a genuine HSP promise — $f$ has hidden period $s$ with $H = \{0^n, s\}$ for an unknown $s$ — and must identify $s$ . The HSP Fourier-sampling strategy is the same, but now we need $O(n)$ samples to pin down all $n$ bits of $s$ .

The progression

\text{Deutsch (1 bit)} \;\subset\; \text{Deutsch–Jozsa} \;\subset\; \text{Simon} \;\subset\; \text{Shor (order-finding)}

is a chain of increasingly powerful HSP instances, all solved by the same conceptual strategy of quantum Fourier sampling over an abelian group.