Multi-qubit Hadamard:
$$H^{\otimes n}\ket{x} = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} \ket{y}$$
Bitwise inner product: \(x \cdot y = \bigoplus_{j} x_j y_j = \left(\sum_j x_j y_j\right) \bmod 2\)
Cancellation lemma: \(\displaystyle\sum_{x \in \{0,1\}^n} (-1)^{x \cdot z} = \begin{cases} 2^n & z = 0^n \\ 0 & z \neq 0^n \end{cases}\)
DJ/BV circuit: \(\ket{0}^{\otimes n} \xrightarrow{H^{\otimes n}} \text{superposition} \xrightarrow{P_f} \text{phases} \xrightarrow{H^{\otimes n}} \text{measure}\)
Simon's circuit: \(\ket{0}^n\ket{0}^n \xrightarrow{H^{\otimes n} \otimes I} \xrightarrow{U_f} \xrightarrow{\text{measure 2nd}} \xrightarrow{H^{\otimes n}} \text{measure 1st}\)
Compute \(H^{\otimes 2}\ket{00}\) using the general formula. Write out every term explicitly.
Using \(H^{\otimes n}\ket{x} = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y}\ket{y}\) with \(x = 00\), \(n = 2\):
Since \(00 \cdot y = 0\) for all \(y\), every sign is \((-1)^0 = +1\):
$$H^{\otimes 2}\ket{00} = \frac{1}{2}\left(\ket{00} + \ket{01} + \ket{10} + \ket{11}\right)$$
This is the uniform superposition over all 2-qubit states. Starting from all zeros always gives the uniform superposition — no minus signs.
Compute \(H^{\otimes 2}\ket{11}\). Which terms get a minus sign?
With \(x = 11\), compute \(x \cdot y = 1 \cdot y_0 + 1 \cdot y_1 = y_0 \oplus y_1\) for each \(y\):
$$H^{\otimes 2}\ket{11} = \frac{1}{2}\left(\ket{00} - \ket{01} - \ket{10} + \ket{11}\right)$$
The terms with an odd number of matching 1-bits get a minus sign. This is \(\ket{-} \otimes \ket{-}\), as you can verify by factoring.
Compute \(H^{\otimes 3}\ket{101}\). List the sign of each of the 8 terms.
With \(x = 101\), the inner product is \(x \cdot y = 1 \cdot y_0 + 0 \cdot y_1 + 1 \cdot y_2 = y_0 \oplus y_2\):
$$H^{\otimes 3}\ket{101} = \frac{1}{2\sqrt{2}}\left(\ket{000} - \ket{001} + \ket{010} - \ket{011} - \ket{100} + \ket{101} - \ket{110} + \ket{111}\right)$$
This factors as \(\ket{-} \otimes \ket{+} \otimes \ket{-}\), matching the input bit pattern: 1 → \(\ket{-}\), 0 → \(\ket{+}\).
Evaluate \(\displaystyle\sum_{x \in \{0,1\}^2} (-1)^{x \cdot 10}\). List each term, then state the result.
Compute \(x \cdot 10 = x_0 \cdot 1 + x_1 \cdot 0 = x_0\) for each \(x\):
$$\sum = (+1) + (+1) + (-1) + (-1) = 0$$
Since \(z = 10 \neq 00\), the cancellation lemma tells us the sum is 0. Half the terms are \(+1\), half are \(-1\).
Without computing each term, what is \(\displaystyle\sum_{x \in \{0,1\}^5} (-1)^{x \cdot 01101}\)?
What about \(\displaystyle\sum_{x \in \{0,1\}^5} (-1)^{x \cdot 00000}\)?
First sum: \(z = 01101 \neq 0^5\), so by the cancellation lemma the sum is 0.
Second sum: \(z = 00000 = 0^5\), so every exponent is 0 and every term is \(+1\). The sum is \(2^5 = \mathbf{32}\).
This is the engine behind Deutsch-Jozsa and Bernstein-Vazirani: for the right phase pattern, all \(2^n\) terms add up constructively; for any wrong pattern, they cancel to zero.
Consider a 2-qubit Deutsch-Jozsa problem. Define \(f: \{0,1\}^2 \to \{0,1\}\) by:
$$f(00) = 0,\quad f(01) = 0,\quad f(10) = 0,\quad f(11) = 0$$
Trace the full circuit. What is the state after each step? What do you measure?
Step 1 — \(H^{\otimes 2}\ket{00}\):
$$\ket{\psi_1} = \frac{1}{2}\left(\ket{00} + \ket{01} + \ket{10} + \ket{11}\right)$$
Step 2 — Phase oracle \(P_f\): Since \(f(x) = 0\) for all \(x\), every term gets phase \((-1)^0 = +1\):
$$\ket{\psi_2} = \frac{1}{2}\left(\ket{00} + \ket{01} + \ket{10} + \ket{11}\right) = \ket{\psi_1}$$
Step 3 — \(H^{\otimes 2}\): Since \(\ket{\psi_2} = H^{\otimes 2}\ket{00}\) and \(H^{\otimes 2}\) is self-inverse:
$$\ket{\psi_3} = H^{\otimes 2} H^{\otimes 2}\ket{00} = \ket{00}$$
Measurement: \(\ket{00}\) with probability 1. All zeros → constant. Correct!
Now consider a balanced function on 2 qubits:
$$f(00) = 0,\quad f(01) = 1,\quad f(10) = 1,\quad f(11) = 0$$
Trace the circuit. Compute the amplitude of every basis state after the second \(H^{\otimes 2}\).
Step 1: \(\ket{\psi_1} = \frac{1}{2}\left(\ket{00} + \ket{01} + \ket{10} + \ket{11}\right)\)
Step 2 — Phase oracle: Apply signs \((-1)^{f(x)}\):
$$\ket{\psi_2} = \frac{1}{2}\left(+\ket{00} - \ket{01} - \ket{10} + \ket{11}\right)$$
Step 3 — \(H^{\otimes 2}\): Compute amplitude of each \(\ket{y}\) using \(\alpha_y = \frac{1}{4}\sum_x (-1)^{f(x) + x \cdot y}\):
\(\alpha_{00}\): signs \(f(x) + x \cdot 00 = f(x)\), so \(\frac{1}{4}(1 - 1 - 1 + 1) = 0\)
\(\alpha_{01}\): \(f(x) + x \cdot 01\) for each \(x\): \(0+0, 1+1, 1+0, 0+1\) = \(0, 0, 1, 1\) → signs \(+, +, -, -\) → \(\frac{1}{4}(1+1-1-1) = 0\)
\(\alpha_{10}\): \(f(x) + x \cdot 10\): \(0+0, 1+0, 1+1, 0+1\) = \(0, 1, 0, 1\) → \(+, -, +, -\) → \(\frac{1}{4}(1-1+1-1) = 0\)
\(\alpha_{11}\): \(f(x) + x \cdot 11\): \(0+0, 1+1, 1+1, 0+0\) = \(0, 0, 0, 0\) → \(+, +, +, +\) → \(\frac{1}{4}(4) = 1\)
$$\ket{\psi_3} = \ket{11}$$
Measurement: \(\ket{11}\) with probability 1. Not \(\ket{00}\) → balanced. Correct!
Note: This particular \(f\) has the sign pattern of \((-1)^{x_0 \oplus x_1}\), which is why the result landed on \(\ket{11}\) specifically.
Prove that for any balanced function, the amplitude of \(\ket{0}^{\otimes n}\) after the DJ circuit is exactly 0.
Hint: What is \(\sum_x (-1)^{f(x)}\) when exactly half the values are 0 and half are 1?
The amplitude of \(\ket{0^n}\) is:
$$\alpha_{0^n} = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} (-1)^{f(x) + x \cdot 0^n} = \frac{1}{2^n} \sum_x (-1)^{f(x)}$$
since \(x \cdot 0^n = 0\) for all \(x\).
If \(f\) is balanced, exactly \(2^{n-1}\) inputs give \(f(x) = 0\) (contributing \(+1\)) and \(2^{n-1}\) give \(f(x) = 1\) (contributing \(-1\)):
$$\sum_x (-1)^{f(x)} = 2^{n-1} \cdot (+1) + 2^{n-1} \cdot (-1) = 0$$
Therefore \(\alpha_{0^n} = 0\) and \(|\alpha_{0^n}|^2 = 0\). We never measure all zeros for a balanced function. Combined with the fact that constant functions always give \(\ket{0^n}\), one query suffices to decide.
Run the Bernstein-Vazirani circuit for \(n = 3\), \(s = 101\). Trace every step from \(\ket{000}\) to the final measurement.
Step 1 — \(H^{\otimes 3}\ket{000}\):
$$\ket{\psi_1} = \frac{1}{2\sqrt{2}} \sum_{x \in \{0,1\}^3} \ket{x}$$
Step 2 — Phase oracle: \(f(x) = s \cdot x = 101 \cdot x = x_0 \oplus x_2\). Compute signs:
$$\ket{\psi_2} = \frac{1}{2\sqrt{2}}\left(\ket{000} - \ket{001} + \ket{010} - \ket{011} - \ket{100} + \ket{101} - \ket{110} + \ket{111}\right)$$
Key insight: This IS exactly \(H^{\otimes 3}\ket{101}\) (compare with Exercise 1.3 above — same signs!).
Step 3 — \(H^{\otimes 3}\):
$$\ket{\psi_3} = H^{\otimes 3} \cdot H^{\otimes 3}\ket{101} = \ket{101}$$
Measurement: \(\ket{101}\) with probability 1. We read off \(s = 101\). One oracle call instead of 3.
For \(n = 4\), \(s = 0110\), compute the amplitude \(\alpha_y\) of measuring an arbitrary \(\ket{y}\). Show that only \(\ket{0110}\) has nonzero amplitude.
The amplitude of \(\ket{y}\) after the full BV circuit is:
$$\alpha_y = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} (-1)^{s \cdot x + x \cdot y} = \frac{1}{2^n} \sum_x (-1)^{x \cdot (s \oplus y)}$$
where we used \(s \cdot x + x \cdot y = x \cdot (s \oplus y) \pmod{2}\).
By the cancellation lemma:
Only \(\ket{0110}\) survives. Measurement gives \(s = 0110\) with certainty.
What happens if you run the BV circuit with \(s = 000\)? What function does \(f(x) = 000 \cdot x\) compute? What do you measure?
\(f(x) = 000 \cdot x = 0\) for all \(x\). This is the constant-zero function.
The phase oracle does nothing: \((-1)^{f(x)} = (-1)^0 = 1\) for all \(x\). The state after the oracle is unchanged from Step 1.
Then \(H^{\otimes n}\) undoes the first \(H^{\otimes n}\): the final state is \(\ket{000}\).
Measurement gives \(s = 000\). This is consistent: both the BV algorithm and the DJ algorithm (with a constant function) measure all zeros. The BV framework includes \(s = 0^n\) as a valid hidden string.
In Simon's algorithm with \(n = 2\) and \(s = 11\), the function satisfies \(f(x) = f(x \oplus 11)\). This gives pairs: \(f(00) = f(11)\) and \(f(01) = f(10)\).
Suppose after applying the oracle \(U_f\) and measuring the output register, you observe \(f(00)\). What is the state of the input register?
Before measurement, the state is \(\frac{1}{2}\sum_x \ket{x}\ket{f(x)}\). Observing \(f(00)\) in the output register collapses the input to the equal superposition of all preimages of \(f(00)\):
$$\ket{\psi} = \frac{1}{\sqrt{2}}\left(\ket{00} + \ket{11}\right)$$
since \(f(00) = f(11)\) (because \(00 \oplus 11 = 11 = s\)).
Continuing from Exercise 5.1, apply \(H^{\otimes 2}\) to the collapsed state \(\frac{1}{\sqrt{2}}(\ket{00} + \ket{11})\). Which \(\ket{y}\) values have nonzero amplitude? Verify that all of them satisfy \(s \cdot y = 0\).
Expand using the Hadamard formula:
$$H^{\otimes 2}\left[\frac{1}{\sqrt{2}}(\ket{00} + \ket{11})\right] = \frac{1}{\sqrt{2}} \cdot \frac{1}{2} \sum_y \left[(-1)^{00 \cdot y} + (-1)^{11 \cdot y}\right]\ket{y}$$
$$= \frac{1}{2\sqrt{2}} \sum_y \left[1 + (-1)^{y_0 \oplus y_1}\right]\ket{y}$$
The factor \([1 + (-1)^{y_0 \oplus y_1}]\) is:
Surviving states: \(\ket{00}\) and \(\ket{11}\), each with amplitude \(\frac{1}{\sqrt{2}}\).
Verification: \(s \cdot 00 = 11 \cdot 00 = 0\) ✔ and \(s \cdot 11 = 11 \cdot 11 = 1 \oplus 1 = 0\) ✔. Both satisfy \(s \cdot y = 0\).
Simon's algorithm with \(n = 3\), \(s = 110\). List all \(y \in \{0,1\}^3\) that satisfy \(s \cdot y = 0 \pmod{2}\). How many are there?
The constraint is \(110 \cdot y = y_0 \oplus y_1 = 0\), meaning \(y_0 = y_1\). The third bit \(y_2\) is unconstrained.
Valid \(y\) values: \(\{000, 001, 110, 111\}\). That's \(\mathbf{4} = 2^{3-1} = 2^2\) values.
In general, for \(s \neq 0^n\), the constraint \(s \cdot y = 0\) defines a subspace of dimension \(n - 1\), so there are \(2^{n-1}\) valid \(y\) values. Each run of Simon's returns one uniformly at random.
You run Simon's algorithm with \(n = 3\) three times and get the equations:
$$s \cdot y_1 = 0: \quad s_0 + s_2 = 0 \quad (y_1 = 101)$$
$$s \cdot y_2 = 0: \quad s_0 + s_1 = 0 \quad (y_2 = 110)$$
$$s \cdot y_3 = 0: \quad s_0 + s_1 + s_2 = 0 \quad (y_3 = 111)$$
Solve the system over \(\text{GF}(2)\) to find \(s\).
Write the system as a matrix equation \(Ys = 0\) over \(\text{GF}(2)\):
$$\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ s_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$$
Gaussian elimination over GF(2):
Row 2 ← Row 2 \(\oplus\) Row 1: \((0, 1, 1)\)
Row 3 ← Row 3 \(\oplus\) Row 1: \((0, 1, 0)\)
Row 3 ← Row 3 \(\oplus\) Row 2: \((0, 0, 1)\)
Reduced system:
$$\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ s_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$$
Back-substitute: Row 3 gives \(s_2 = 0\). Row 2 gives \(s_1 + 0 = 0\) so \(s_1 = 0\). Row 1 gives \(s_0 + 0 = 0\) so \(s_0 = 0\).
\(s = 000\). The only solution is the trivial one, meaning the null space is trivial — the function is one-to-one (injective).
Note: If the matrix has rank \(n\), the null space is \(\{0^n\}\) only. To find a nonzero \(s\), we need the rank to be \(n - 1\), leaving a 1-dimensional null space.
Now suppose with \(n = 3\) you get these measurements:
$$y_1 = 001 \quad (s_2 = 0), \qquad y_2 = 110 \quad (s_0 + s_1 = 0)$$
Find all consistent values of \(s\). Is two equations enough?
From \(s_2 = 0\) and \(s_0 = s_1\), the free variable is \(s_0\):
Two equations give rank 2, so the null space has dimension \(3 - 2 = 1\). The nontrivial solution is \(s = \mathbf{110}\).
Two independent equations was enough here because \(n - 1 = 2\). In general, you need \(n - 1\) linearly independent equations to pin down a unique nonzero \(s\).
In Simon's algorithm, if \(s = 0^n\) (i.e., \(f\) is injective), what happens when you measure the output register? What state does the input register collapse to? What does \(H^{\otimes n}\) produce?
If \(f\) is injective, each output value has exactly one preimage. Measuring \(f(x_0)\) in the output register collapses the input register to the single state \(\ket{x_0}\) (no superposition of two preimages).
Applying \(H^{\otimes n}\) to \(\ket{x_0}\) gives a uniform superposition over all \(y\) with various signs:
$$H^{\otimes n}\ket{x_0} = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x_0 \cdot y}\ket{y}$$
Every \(y \in \{0,1\}^n\) has equal probability \(1/2^n\). The constraint \(s \cdot y = 0\) with \(s = 0^n\) is satisfied by all \(y\), which is consistent: every measurement outcome is valid.
After \(n\) runs, if all \(n\) equations are independent (rank \(n\)), the only solution is \(s = 0^n\) — confirming the function is injective.
Fill in the table of query complexities from memory:
| Algorithm | Classical (det.) | Classical (prob.) | Quantum |
|---|---|---|---|
| Deutsch-Jozsa | ? | ? | ? |
| Bernstein-Vazirani | ? | ? | ? |
| Simon's | ? | ? | ? |
| Algorithm | Classical (det.) | Classical (prob.) | Quantum |
|---|---|---|---|
| Deutsch-Jozsa | \(2^{n-1} + 1\) | \(O(1)\) with high prob. | \(1\) |
| Bernstein-Vazirani | \(n\) | — | \(1\) |
| Simon's | \(2^{n-1} + 1\) | \(\sim 2^{n/2}\) (birthday) | \(\sim n\) |
Key points:
Why does the classical complexity of Bernstein-Vazirani not have a "probabilistic" improvement? That is, why can't you do better than \(n\) classical queries?
Each classical query of \(f(x) = s \cdot x\) returns a single bit of information (the parity of certain bits of \(s\)). The hidden string has \(n\) bits of information. By information-theoretic bounds, you need at least \(n\) queries.
More precisely, the optimal classical strategy queries the standard basis vectors \(e_1, e_2, \ldots, e_n\), and each query \(f(e_i) = s_i\) reveals exactly one bit. Any other query \(f(x)\) for a non-basis vector gives a parity of multiple bits, which is redundant once you know all individual bits. So \(n\) queries are both necessary and sufficient, with no probabilistic shortcut.
Why does Simon's algorithm need a Boolean oracle (not a phase oracle) while DJ and BV use phase oracles? Give two reasons.
Reason 1 — Multi-bit output: Simon's function maps \(\{0,1\}^n \to \{0,1\}^n\). A phase oracle can only encode a single-bit output as \(\pm 1\). With \(n\)-bit outputs, there's no natural way to encode the full output in a phase.
Reason 2 — The collapse mechanism: The key step in Simon's is measuring the output register to collapse the input to the superposition \(\frac{1}{\sqrt{2}}(\ket{x_0} + \ket{x_0 \oplus s})\). This requires the output to be stored in a register so it can be measured. A phase oracle doesn't write the output anywhere — it encodes everything in phases, so there's nothing to measure and no collapse into a two-element superposition.
In short: DJ and BV only need to know whether \(f(x)\) is 0 or 1 (a sign), while Simon's needs the actual output value to identify which inputs collide.