The Deutsch–Jozsa Algorithm

1. 1
   Step 1:

   $$U_f\lvert x,y\rangle=\lvert x,\,y\oplus f(x)\rangle\in\big\{\lvert x',y'\rangle:\ x'\in\{0,1\}^n,\ y'\in\{0,1\}\big\}$$

   Each basis state is mapped to a basis state, so every column of the matrix of $U_f$ contains exactly one entry $1$ and all other entries $0$.
2. 2
   Step 2:

   $$U_f^2\lvert x,y\rangle=U_f\lvert x,\,y\oplus f(x)\rangle=\lvert x,\,y\oplus f(x)\oplus f(x)\rangle=\lvert x,y\rangle$$

   Apply the definition twice: the input register $x$ is unchanged by the first application, so the second one adds the same bit $f(x)$, and $b\oplus b=0$ for every bit $b$.
3. 3
   Step 3:

   $$U_f^2=I\ \Longrightarrow\ U_f\ \text{is a bijection of the basis with}\ U_f^{-1}=U_f$$

   $U_f^2$ agrees with $I$ on a basis, so $U_f^2=I$ by linearity. A map that is its own inverse is bijective; in particular two different basis states never have the same image, so every row also contains exactly one $1$: $U_f$ is a permutation matrix.
4. 4
   Step 4:

   $$(U_f^TU_f)_{jk}=\sum_iP_{ij}P_{ik}=\delta_{jk}\ \Longrightarrow\ U_f^\dagger U_f=U_f^TU_f=I$$

   For a permutation matrix $P$, columns $j$ and $k$ are the standard basis vectors $e_{\pi(j)}$ and $e_{\pi(k)}$, which are orthonormal. The entries are real, so $U_f^\dagger=U_f^T$.
5. 5
   Step 5:

   $$U_f^\dagger=U_f^{-1}=U_f$$

   Unitarity gives $U_f^\dagger=U_f^{-1}$ and the involution gives $U_f^{-1}=U_f$; hence $U_f$ is also Hermitian, a real symmetric permutation matrix.

∎

1. 1
   Step 1:

   $$n=1:\quad H\lvert x\rangle=\tfrac1{\sqrt2}\big(\lvert0\rangle+(-1)^x\lvert1\rangle\big)=\tfrac1{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\lvert z\rangle$$

   Base case. $H=\tfrac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$: column $x=0$ is $\tfrac1{\sqrt2}(1,1)^T$ and column $x=1$ is $\tfrac1{\sqrt2}(1,-1)^T$. The coefficient of $\lvert z\rangle$ is $\tfrac1{\sqrt2}(-1)^{xz}$, since $xz=1$ only for $x=z=1$.
2. 2
   Step 2:

   $$x=x'x_n\in\{0,1\}^{n+1},\ x'\in\{0,1\}^n:\quad H^{\otimes(n+1)}\lvert x\rangle=\big(H^{\otimes n}\lvert x'\rangle\big)\otimes\big(H\lvert x_n\rangle\big)$$

   Inductive step: assume the claim for $n$ and split $x$ into its first $n$ bits $x'=x_0\cdots x_{n-1}$ and its last bit $x_n$. Then $\lvert x\rangle=\lvert x'\rangle\otimes\lvert x_n\rangle$, $H^{\otimes(n+1)}=H^{\otimes n}\otimes H$, and $(A\otimes B)(\lvert u\rangle\otimes\lvert v\rangle)=A\lvert u\rangle\otimes B\lvert v\rangle$.
3. 3
   Step 3:

   $$=\Big(\frac1{2^{n/2}}\sum_{z'\in\{0,1\}^n}(-1)^{x'\cdot z'}\lvert z'\rangle\Big)\otimes\Big(\frac1{\sqrt2}\sum_{z_n\in\{0,1\}}(-1)^{x_nz_n}\lvert z_n\rangle\Big)$$

   Insert the induction hypothesis for the first factor and the base case for the second.
4. 4
   Step 4:

   $$=\frac1{2^{(n+1)/2}}\sum_{z'\in\{0,1\}^n}\ \sum_{z_n\in\{0,1\}}(-1)^{x'\cdot z'+x_nz_n}\,\lvert z'\rangle\otimes\lvert z_n\rangle$$

   The tensor product is bilinear, so the product of two sums is the double sum of the products; the prefactors multiply to $2^{-n/2}\cdot2^{-1/2}=2^{-(n+1)/2}$ and the signs multiply to $(-1)^{x'\cdot z'+x_nz_n}$.
5. 5
   Step 5:

   $$=\frac1{2^{(n+1)/2}}\sum_{z\in\{0,1\}^{n+1}}(-1)^{x\cdot z}\lvert z\rangle$$

   The pairs $(z',z_n)$ run exactly once over all $z=z'z_n\in\{0,1\}^{n+1}$, $\lvert z'\rangle\otimes\lvert z_n\rangle=\lvert z\rangle$, and $x\cdot z=x'\cdot z'\oplus x_nz_n\equiv x'\cdot z'+x_nz_n\pmod2$, which is all that $(-1)^{(\cdot)}$ sees. This is the claim for $n+1$; by induction it holds for all $n\ge1$.

∎

1. 1
   Step 1:

   $$f\equiv c:\quad a_{0^n}=\frac1{2^n}\sum_x(-1)^c=\frac{2^n(-1)^c}{2^n}=(-1)^c,\qquad P(0^n)=1$$

   All $2^n$ terms equal $(-1)^c$.
2. 2
   Step 2:

   $$\sum_z\lvert a_z\rvert^2=1\ \Longrightarrow\ a_z=0\ \text{for all}\ z\neq0^n,\qquad\lvert\psi_3\rangle=(-1)^c\lvert0^n\rangle\lvert-\rangle$$

   $\lvert\psi_3\rangle$ is a unit vector (unitaries preserve the norm), so once $\lvert a_{0^n}\rvert=1$ all other amplitudes vanish: the full state after the second $H^{\otimes n}$ is the basis state $\lvert0^n\rangle$ times a global sign.
3. 3
   Step 3:

   $$f\ \text{balanced}:\quad\sum_x(-1)^{f(x)}=\#\{x:f(x)=0\}-\#\{x:f(x)=1\}=2^{n-1}-2^{n-1}=0$$

   Each input with $f(x)=0$ contributes $+1$ and each input with $f(x)=1$ contributes $-1$; balanced means both counts are $2^{n-1}$.
4. 4
   Step 4:

   $$a_{0^n}=0,\qquad P(0^n)=0,\qquad\lvert\psi_3\rangle=\sum_{z\neq0^n}a_z\lvert z\rangle\lvert-\rangle$$

   So a balanced function always produces a non-zero string $z$; which one depends on $f$, but any $z\neq0^n$ certifies "balanced".

∎

1. 1
   Step 1:

   $$\text{adversary: answer } f(x_i)=0\ \text{to every query } x_1,x_2,\dots,x_q,\qquad q\le2^{n-1}$$

   Suppose an algorithm $A$ always halts after at most $q\le2^{n-1}$ queries. Run it against an adversary who answers $0$ to every query. Because $A$ is deterministic, each query point $x_{i+1}$ and the final output are functions of the earlier answers only; against the all-zero answers $A$ queries a fixed set $S=\{x_1,\dots,x_q\}$ with $\lvert S\rvert\le2^{n-1}$ and outputs a fixed answer.
2. 2
   Step 2:

   $$f_0\equiv0\quad\text{is constant and consistent with every answer}$$

   The constant zero function gives exactly the answers the adversary gave.
3. 3
   Step 3:

   $$T\supseteq S,\ \lvert T\rvert=2^{n-1};\qquad f_1(x)=\begin{cases}0,&x\in T\\1,&x\notin T\end{cases}\quad\text{is balanced and consistent}$$

   Since $\lvert S\rvert\le2^{n-1}$ we can enlarge $S$ to a set $T$ of exactly $2^{n-1}$ inputs. Then $f_1$ takes the value $0$ on $2^{n-1}$ inputs and $1$ on the other $2^{n-1}$, so it is balanced, and it is $0$ on every queried point.
4. 4
   Step 4:

   $$A(f_0)=A(f_1)\quad\text{while}\quad f_0\ \text{constant},\ f_1\ \text{balanced}$$

   On $f_0$ and on $f_1$ the algorithm sees the same answers, hence (by determinism, inductively over the queries) asks the same questions and produces the same output. That output is wrong for one of them, contradicting correctness. Therefore some input forces at least $2^{n-1}+1$ queries.
5. 5
   Step 5:

   $$2^{n-1}+1\ \text{queries suffice: if all answers are equal, } f \text{ is constant; otherwise balanced}$$

   Query any $2^{n-1}+1$ distinct inputs. A balanced function has only $2^{n-1}$ zeros and $2^{n-1}$ ones, so it cannot return $2^{n-1}+1$ equal answers; seeing two different values rules out a constant function. Under the promise the answer is always correct.

∎

1. 1
   Step 1:

   $$f\equiv c\ \Longrightarrow\ f(x_1)=\cdots=f(x_k)=c\ \Longrightarrow\ \text{output "constant"}$$

   A constant function always returns equal answers, so there is no error on constant inputs (one-sided error).
2. 2
   Step 2:

   $$f\ \text{balanced}:\quad\Pr[f(x_i)=0]=\Pr[f(x_i)=1]=\tfrac{2^{n-1}}{2^n}=\tfrac12,\ \text{independently for } i=1,\dots,k$$

   Each $x_i$ is uniform over $\{0,1\}^n$ and exactly half the inputs map to each value.
3. 3
   Step 3:

   $$\Pr[\text{error}]=\Pr[\text{all }0]+\Pr[\text{all }1]=\big(\tfrac12\big)^k+\big(\tfrac12\big)^k=2^{1-k}$$

   The algorithm errs on a balanced $f$ exactly when the $k$ answers all agree; the two events are disjoint and each has probability $2^{-k}$ by independence.

∎