Consider the Bernstein-Vazirani algorithm applied to the function \(f(x_0, x_1) = s_0 \cdot x_0 + s_1 \cdot x_1 \pmod{2}\) where the secret string is \(s = 10\) (i.e., \(s_0 = 1, s_1 = 0\)).
(1) Write down the truth table for \(f\).
(2) Draw/describe the phase oracle circuit for \(f\).
(3) Evaluate the BV circuit step by step. Show that the state after the oracle is \(\ket{-}\ket{+}\).
(4) Show that measurement returns \(s = 10\) with 100% probability.
(1) Truth table:
Since \(f(x_0, x_1) = 1 \cdot x_0 + 0 \cdot x_1 = x_0 \pmod{2}\), the function simply returns the first bit:
$$\begin{array}{cc|c} x_0 & x_1 & f(x_0, x_1) \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array}$$
(2) Phase oracle circuit:
The phase oracle implements \(P_f\ket{x_0, x_1} = (-1)^{f(x_0, x_1)}\ket{x_0, x_1}\). Since \(f(x_0, x_1) = x_0\), the oracle just applies a phase of \((-1)^{x_0}\) to the first qubit. This is exactly the \(Z\) gate on qubit 0:
$$P_f = Z \otimes I$$
In general, for BV with secret string \(s\), the phase oracle is \(P_f = Z^{s_0} \otimes Z^{s_1} \otimes \cdots \otimes Z^{s_{n-1}}\), where \(Z^0 = I\) and \(Z^1 = Z\). Here: \(Z \otimes I\).
(3) Step-by-step evaluation of the BV circuit:
The BV circuit is: \(H^{\otimes 2} \to P_f \to H^{\otimes 2}\), applied to initial state \(\ket{00}\).
Step 1: Apply \(H \otimes H\) to \(\ket{00}\):
$$H\ket{0} \otimes H\ket{0} = \ket{+}\ket{+}$$
Step 2: Apply oracle \(P_f = Z \otimes I\):
$$(Z \otimes I)\ket{+}\ket{+} = Z\ket{+} \otimes I\ket{+} = \ket{-}\ket{+}$$
This works because \(Z\ket{+} = Z \cdot \frac{1}{\sqrt{2}}(\ket{0}+\ket{1}) = \frac{1}{\sqrt{2}}(\ket{0}-\ket{1}) = \ket{-}\).
So after the oracle, the state is \(\ket{-}\ket{+}\), as required.
Step 3: Apply \(H \otimes H\):
$$H\ket{-} \otimes H\ket{+} = \ket{1}\ket{0} = \ket{10}$$
Using \(H\ket{-} = \ket{1}\) and \(H\ket{+} = \ket{0}\).
(4) Measurement probability:
The final state is exactly \(\ket{10}\) — a computational basis state with no superposition. Measurement yields \(10\) with probability \(|1|^2 = 1\), i.e., 100%. This equals the secret string \(s = 10\). The algorithm recovers \(s\) in a single query, as guaranteed by BV.
(a) Give the explicit matrix for \(F_3\) (the 3-point discrete Fourier transform as a matrix).
(b) Could you turn \(F_3\) into a quantum gate?
(a) Explicit matrix for \(F_3\):
The DFT matrix \(F_N\) has entries \((F_N)_{jk} = \frac{1}{\sqrt{N}} \omega_N^{jk}\) where \(\omega_N = e^{2\pi i/N}\).
For \(N = 3\): \(\omega_3 = e^{2\pi i/3}\). The exponents \(jk\) for \(j,k \in \{0,1,2\}\) are:
$$F_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} \omega_3^0 & \omega_3^0 & \omega_3^0 \\ \omega_3^0 & \omega_3^1 & \omega_3^2 \\ \omega_3^0 & \omega_3^2 & \omega_3^4 \end{pmatrix} = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega_3 & \omega_3^2 \\ 1 & \omega_3^2 & \omega_3^4 \end{pmatrix}$$
Since \(\omega_3^3 = 1\), we have \(\omega_3^4 = \omega_3\). So:
$$F_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega_3 & \omega_3^2 \\ 1 & \omega_3^2 & \omega_3 \end{pmatrix}$$
where \(\omega_3 = e^{2\pi i/3} = -\frac{1}{2} + \frac{\sqrt{3}}{2}i\) and \(\omega_3^2 = e^{4\pi i/3} = -\frac{1}{2} - \frac{\sqrt{3}}{2}i\).
(b) Can \(F_3\) be a quantum gate?
No. A quantum gate must operate on a system of qubits, which means it acts on a Hilbert space of dimension \(2^n\) for some \(n\). The matrix \(F_3\) is \(3 \times 3\), and \(3\) is not a power of \(2\). There is no number of qubits that gives a 3-dimensional state space.
\(F_3\) is unitary (we prove this in general in Exercise 6), so mathematically it preserves norms and inner products. The issue is purely that qubit systems have dimensions \(2, 4, 8, 16, \ldots\) and 3 is not in this sequence. You would need a qutrit (a 3-level quantum system) to implement \(F_3\) as a gate.
In contrast, \(F_2 = H\) (the Hadamard) and \(F_4\) (which acts on 2 qubits) are valid quantum gates.
(a) Calculate \(F_4\ket{0}\).
(b) Calculate \(F_4\ket{x}\) for each \(x \in \{0, 1, 2, 3\}\).
(c) Show that \(1 + \omega_4 + \omega_4^2 + \omega_4^3 = 0\).
(d) Use your results from (b) and (c) to calculate \(F_4 \cdot \frac{1}{\sqrt{4}}(\ket{0} + \ket{1} + \ket{2} + \ket{3})\).
(e) Check your answer to (d) against a general formula.
(a) \(F_4\ket{0}\):
Using the definition \(F_N\ket{x} = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \omega_N^{xy}\ket{y}\) with \(N = 4, x = 0\):
$$F_4\ket{0} = \frac{1}{\sqrt{4}} \sum_{y=0}^{3} \omega_4^{0 \cdot y}\ket{y} = \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3})$$
All phases are \(\omega_4^0 = 1\), so \(F_4\ket{0}\) is the uniform superposition.
(b) \(F_4\ket{x}\) for \(x \in \{0,1,2,3\}\):
First, note that \(\omega_4 = e^{2\pi i/4} = e^{i\pi/2} = i\). So \(\omega_4 = i\), \(\omega_4^2 = -1\), \(\omega_4^3 = -i\).
\(x = 0\): (computed above)
$$F_4\ket{0} = \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3})$$
\(x = 1\): Phases are \(\omega_4^y = i^y\):
$$F_4\ket{1} = \frac{1}{2}(\ket{0} + i\ket{1} - \ket{2} - i\ket{3})$$
\(x = 2\): Phases are \(\omega_4^{2y} = (-1)^y\):
$$F_4\ket{2} = \frac{1}{2}(\ket{0} - \ket{1} + \ket{2} - \ket{3})$$
\(x = 3\): Phases are \(\omega_4^{3y} = (-i)^y\):
$$F_4\ket{3} = \frac{1}{2}(\ket{0} - i\ket{1} - \ket{2} + i\ket{3})$$
(c) Show \(1 + \omega_4 + \omega_4^2 + \omega_4^3 = 0\):
Method 1 (direct): Substitute \(\omega_4 = i\):
$$1 + i + i^2 + i^3 = 1 + i + (-1) + (-i) = 0 \;\;\checkmark$$
Method 2 (geometric series): For \(r = \omega_4 \neq 1\):
$$\sum_{k=0}^{3} \omega_4^k = \frac{1 - \omega_4^4}{1 - \omega_4} = \frac{1 - 1}{1 - i} = 0$$
since \(\omega_4^4 = (e^{2\pi i/4})^4 = e^{2\pi i} = 1\).
This is a special case of the general identity: \(\sum_{k=0}^{N-1} \omega_N^{mk} = N \cdot \delta_{m, 0 \bmod N}\). For \(m \neq 0 \bmod N\), the \(N\) roots of unity sum to zero.
(d) Calculate \(F_4 \cdot \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3})\):
By linearity, use results from (b):
$$F_4 \cdot \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3}) = \frac{1}{2}\left(F_4\ket{0} + F_4\ket{1} + F_4\ket{2} + F_4\ket{3}\right)$$
Collect the coefficient of each output basis state \(\ket{y}\):
Coefficient of \(\ket{0}\): \(\frac{1}{2} \cdot \frac{1}{2}(1 + 1 + 1 + 1) = \frac{4}{4} = 1\)
Coefficient of \(\ket{1}\): \(\frac{1}{2} \cdot \frac{1}{2}(1 + i + (-1) + (-i)) = \frac{1}{4}(1 + i - 1 - i) = 0\)
Coefficient of \(\ket{2}\): \(\frac{1}{2} \cdot \frac{1}{2}(1 + (-1) + 1 + (-1)) = 0\)
Coefficient of \(\ket{3}\): \(\frac{1}{2} \cdot \frac{1}{2}(1 + (-i) + (-1) + i) = 0\)
$$F_4 \cdot \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3}) = \ket{0}$$
The uniform superposition maps back to \(\ket{0}\). The cancellation in \(\ket{1}, \ket{2}, \ket{3}\) is exactly the identity from part (c): the roots of unity sum to zero.
(e) Check against general formula:
We computed \(F_4\ket{0} = \frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3})\) in part (a). So the input \(\frac{1}{2}(\ket{0} + \ket{1} + \ket{2} + \ket{3}) = F_4\ket{0}\).
Since the QFT is unitary, \(F_4 F_4^\dagger = I\), but note \(F_4^2 \neq I\) in general. However, we can use the fact that our input is \(F_4\ket{0}\), so we're computing \(F_4(F_4\ket{0}) = F_4^2\ket{0}\).
For the DFT, it is known that \(F_N^2\) is the "reversal operator": \(F_N^2\ket{x} = \ket{N - x \bmod N}\). So \(F_4^2\ket{0} = \ket{4 - 0 \bmod 4} = \ket{0}\). This confirms our answer.
Alternatively, the general orthogonality relation \(\sum_{x=0}^{N-1} \omega_N^{(j-k)x} = N\,\delta_{jk}\) directly gives the result: when we apply \(F_4\) to the uniform superposition (= \(F_4\ket{0}\)), only the \(\ket{0}\) component survives.
A circuit has two 2-qubit registers \(\ket{x_2 x_1}\) and \(\ket{y_2 y_1}\). The circuit performs the following steps:
Show that this circuit computes \(\ket{x}\ket{y} \to \ket{x}\ket{x + y \bmod 4}\).
The key insight is that the QFT converts addition into phase rotations, which are easy to implement with controlled gates.
Step 1: QFT on \(\ket{y}\).
The QFT maps \(\ket{y}\) into the Fourier basis:
$$F_4\ket{y} = \frac{1}{2}\sum_{k=0}^{3} \omega_4^{ky}\ket{k}$$
Step 2: Controlled rotations add \(x\) in the Fourier basis.
In the Fourier basis, the state \(\ket{k}\) carries a phase \(\omega_4^{ky}\). To add \(x\) to \(y\), we need to change the phase from \(\omega_4^{ky}\) to \(\omega_4^{k(y+x)} = \omega_4^{ky} \cdot \omega_4^{kx}\). So we need to multiply each Fourier component \(\ket{k}\) by \(\omega_4^{kx}\).
The 2-qubit label \(k = 2k_2 + k_1\) and \(x = 2x_2 + x_1\), so:
$$\omega_4^{kx} = \omega_4^{(2k_2 + k_1)(2x_2 + x_1)} = \omega_4^{4k_2 x_2} \cdot \omega_4^{2k_2 x_1} \cdot \omega_4^{2k_1 x_2} \cdot \omega_4^{k_1 x_1}$$
Since \(\omega_4^4 = 1\), the first factor is 1. So:
$$\omega_4^{kx} = \omega_4^{2k_2 x_1} \cdot \omega_4^{2k_1 x_2} \cdot \omega_4^{k_1 x_1}$$
Now, \(\omega_4^{2} = -1 = e^{i\pi}\), so \(\omega_4^{2k_2 x_1} = e^{i\pi k_2 x_1}\). This phase on qubit \(y_2\) controlled by \(x_1\) is exactly \(R_1 = Z\) (phase \(e^{i\pi} = -1\) when \(k_2 = 1\)), controlled by \(x_1\).
Similarly, \(\omega_4^{2k_1 x_2} = e^{i\pi k_1 x_2}\) is \(R_1 = Z\) on qubit \(y_2\)... wait, let's be more careful. The phase \(\omega_4^{2k_1 x_2}\) applies when \(k_1 = 1\), controlled by \(x_2\). This is a controlled-\(R_1\) on \(y_2\) with \(x_2\) as control. (Since \(\omega_4^2 = e^{i\pi}\) and \(R_1\) adds phase \(e^{i\pi}\) to \(\ket{1}\).)
And \(\omega_4^{k_1 x_1} = e^{i\pi k_1 x_1 / 2}\), which applies phase \(\omega_4 = e^{i\pi/2}\) to \(\ket{1}\) on qubit \(y_1\), controlled by \(x_1\). This is controlled-\(R_2\) (since \(R_2 = S\) adds phase \(e^{i\pi/2}\)).
So the three controlled rotations are exactly:
Actually, let's be precise with the R-gate convention. \(R_s\) adds phase \(\omega_{2^s} = e^{2\pi i / 2^s}\). So:
The controlled rotations in the circuit produce:
Let me restart with a cleaner approach. Write \(y\) in binary as \(y = 2y_2 + y_1\). After the QFT, the state of each qubit in the Fourier basis (using the product representation of the QFT) is:
$$F_4\ket{y} = \frac{1}{2}\left(\ket{0} + e^{2\pi i \cdot y/2}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \cdot y/4}\ket{1}\right)$$
where the first factor is qubit \(y_1\) (least significant) and the second is qubit \(y_2\) (most significant). Using the product formula for the QFT:
To add \(x\), we need to shift the phases: replace \(y\) with \(y + x\) in each exponent.
For qubit \(y_1\): need to change \((-1)^{y_1}\) to \((-1)^{y_1 + x_1}\). This requires multiplying by \((-1)^{x_1} = e^{i\pi x_1}\). When \(x_1 = 1\), apply \(R_1 = Z\). This is: \(x_1\)-controlled \(R_1\) on \(y_1\).
For qubit \(y_2\): need to change \(\omega_4^{y}\) to \(\omega_4^{y+x} = \omega_4^y \cdot \omega_4^x = \omega_4^y \cdot \omega_4^{2x_2 + x_1}\). So multiply by \(\omega_4^{2x_2} \cdot \omega_4^{x_1}\).
So the three controlled rotations are:
which matches the circuit description exactly.
Step 3: Inverse QFT.
After the controlled rotations, the Fourier-basis state encodes \(y + x\). Applying \(F_4^\dagger\) converts back to the computational basis:
$$F_4^\dagger \left(\text{Fourier representation of } y+x\right) = \ket{(y + x) \bmod 4}$$
The full transformation is therefore \(\ket{x}\ket{y} \to \ket{x}\ket{(x + y) \bmod 4}\). The \(\bmod 4\) comes naturally from the periodicity of the phases: \(\omega_4^4 = 1\), so any overflow wraps around.
This is the Draper adder: QFT the target register, add via controlled phase rotations, inverse QFT. It generalizes to \(n\)-qubit addition with \(O(n^2)\) gates.
Show that the following 3-qubit circuit computes \(F_8\):
$$\ket{k_1}: \;H \to R_2 \to R_3 \to \times$$
$$\ket{k_2}: \;\bullet \to H \to R_2$$
$$\ket{k_3}: \;\;\;\;\;\;\;\;\;\bullet \to \bullet \to H \to \times$$
where \(R_s = \begin{pmatrix}1 & 0 \\ 0 & \omega_{2^s}\end{pmatrix}\), the dots (\(\bullet\)) are control qubits for the \(R\) gates above them, and \(\times\) denotes a SWAP between \(\ket{k_1}\) and \(\ket{k_3}\).
We need to show that this circuit produces \(F_8\ket{k} = \frac{1}{\sqrt{8}} \sum_{j=0}^{7} \omega_8^{jk}\ket{j}\) for input \(\ket{k} = \ket{k_1 k_2 k_3}\) where \(k = 4k_1 + 2k_2 + k_3\).
The QFT has a product representation. For \(N = 2^n\), the QFT of \(\ket{k}\) can be written as a tensor product of single-qubit states:
$$F_{2^n}\ket{k_1 \ldots k_n} = \frac{1}{\sqrt{2^n}} \bigotimes_{j=1}^{n} \left(\ket{0} + e^{2\pi i \cdot 0.k_j k_{j+1} \cdots k_n}\ket{1}\right)$$
where \(0.k_j k_{j+1} \cdots k_n\) is the binary fraction \(\sum_{l=0}^{n-j} k_{j+l}/2^{l+1}\).
For \(n = 3\), \(F_8\ket{k_1 k_2 k_3}\) is:
$$\frac{1}{\sqrt{8}} \left(\ket{0} + e^{2\pi i \cdot 0.k_3}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \cdot 0.k_2 k_3}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \cdot 0.k_1 k_2 k_3}\ket{1}\right)$$
Note: the output is in bit-reversed order compared to the input — the first qubit of the output depends on \(k_3\) only, while the last depends on all of \(k_1, k_2, k_3\). This is why we need the SWAP at the end.
Now trace through the circuit, qubit by qubit:
Qubit \(k_1\) (most significant):
Qubit \(k_2\) (middle):
Qubit \(k_3\) (least significant):
Before the SWAP, the 3-qubit state is:
$$\frac{1}{\sqrt{8}} \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_1 k_2 k_3}\ket{1}\right)}_{\text{qubit 1}} \otimes \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_2 k_3}\ket{1}\right)}_{\text{qubit 2}} \otimes \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_3}\ket{1}\right)}_{\text{qubit 3}}$$
After the SWAP of qubits 1 and 3:
$$\frac{1}{\sqrt{8}} \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_3}\ket{1}\right)}_{\text{qubit 1}} \otimes \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_2 k_3}\ket{1}\right)}_{\text{qubit 2}} \otimes \underbrace{\left(\ket{0} + e^{2\pi i \cdot 0.k_1 k_2 k_3}\ket{1}\right)}_{\text{qubit 3}}$$
This matches the product representation of \(F_8\ket{k_1 k_2 k_3}\) exactly. Therefore the circuit computes \(F_8\).
Gate count: The circuit uses 3 Hadamards + 2 controlled-\(R_2\) + 1 controlled-\(R_3\) + 1 SWAP = \(3 + 2 + 1 = 6\) non-trivial gates (plus the SWAP). In general, the QFT on \(n\) qubits uses \(n(n+1)/2\) gates, which is \(O(n^2)\) — exponentially fewer than the \(O(N \log N) = O(n \cdot 2^n)\) operations of the classical FFT.
Prove that the Quantum Fourier Transform is unitary: \(F_N (F_N)^\dagger = I\).
We need to show that \(F_N F_N^\dagger = I\), which is equivalent to showing that the columns of \(F_N\) form an orthonormal set.
The matrix elements are \((F_N)_{jk} = \frac{1}{\sqrt{N}} \omega_N^{jk}\), so \((F_N^\dagger)_{jk} = \overline{(F_N)_{kj}} = \frac{1}{\sqrt{N}} \omega_N^{-kj}\).
Compute the \((j,k)\) entry of \(F_N F_N^\dagger\):
$$(F_N F_N^\dagger)_{jk} = \sum_{m=0}^{N-1} (F_N)_{jm} (F_N^\dagger)_{mk} = \sum_{m=0}^{N-1} \frac{1}{\sqrt{N}} \omega_N^{jm} \cdot \frac{1}{\sqrt{N}} \omega_N^{-km}$$
$$= \frac{1}{N} \sum_{m=0}^{N-1} \omega_N^{(j-k)m}$$
Now apply the geometric series / roots of unity identity. Let \(r = \omega_N^{j-k}\):
Case 1: \(j = k\). Then \(r = \omega_N^0 = 1\), so \(\sum_{m=0}^{N-1} 1^m = N\). Result: \(\frac{1}{N} \cdot N = 1\).
Case 2: \(j \neq k\). Then \(r = \omega_N^{j-k} \neq 1\) (since \(0 < |j-k| < N\), and \(\omega_N\) is a primitive \(N\)-th root of unity). By the geometric series formula:
$$\sum_{m=0}^{N-1} r^m = \frac{1 - r^N}{1 - r} = \frac{1 - (\omega_N^{j-k})^N}{1 - \omega_N^{j-k}} = \frac{1 - (\omega_N^N)^{j-k}}{1 - \omega_N^{j-k}} = \frac{1 - 1^{j-k}}{1 - \omega_N^{j-k}} = \frac{0}{1 - \omega_N^{j-k}} = 0$$
Result: \(\frac{1}{N} \cdot 0 = 0\).
Therefore:
$$(F_N F_N^\dagger)_{jk} = \delta_{jk} = \begin{cases} 1 & \text{if } j = k \\ 0 & \text{if } j \neq k \end{cases}$$
which means \(F_N F_N^\dagger = I\). The QFT is unitary. \(\square\)
Note: this proof works for any \(N\), not just powers of 2. The Fourier matrix is always unitary. The restriction to \(N = 2^n\) is only needed when implementing it as a quantum circuit (because qubits give dimensions that are powers of 2).
Explain what "quantum parallelism" is.
Quantum parallelism is the ability of a quantum computer to evaluate a function \(f\) on all inputs simultaneously using a single application of the oracle \(U_f\).
Starting from \(\ket{0}^{\otimes n}\), apply \(H^{\otimes n}\) to create the uniform superposition \(\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n - 1} \ket{x}\). Then apply the oracle:
$$U_f \left(\frac{1}{\sqrt{2^n}} \sum_x \ket{x}\ket{0}\right) = \frac{1}{\sqrt{2^n}} \sum_x \ket{x}\ket{f(x)}$$
The result contains \(f(x)\) for all \(2^n\) inputs at once. This looks like evaluating \(f\) on exponentially many inputs with a single oracle call.
The catch: Measurement collapses the superposition. You get a single random \((x, f(x))\) pair — no better than classical random evaluation. The power of quantum computing is not in computing all values of \(f\), but in using interference to extract global properties of \(f\) (like its period, or whether it's constant vs balanced) that would require many classical evaluations to determine.
Quantum parallelism is the starting point (create the superposition), but interference and clever measurement are what deliver the speedup.
Explain in which sense quantum computing achieves a speedup for the Deutsch-Jozsa problem. Discuss: deterministic vs probabilistic algorithms, worst-case vs best-case.
The Deutsch-Jozsa problem: given a function \(f: \{0,1\}^n \to \{0,1\}\) promised to be either constant (same output for all inputs) or balanced (outputs 0 on exactly half the inputs, 1 on the other half), determine which.
Quantum: The Deutsch-Jozsa algorithm solves this with 1 oracle query, deterministically (100% success probability).
Classical deterministic (worst-case): You need \(2^{n-1} + 1\) queries in the worst case. After \(2^{n-1}\) queries that all return the same value, you still can't distinguish constant from balanced — a balanced function could have all its 0s (or 1s) concentrated in the half you queried. The \((2^{n-1} + 1)\)-th query settles it.
Classical probabilistic (best-case): If you allow randomness and bounded error, just query \(k\) random inputs. If you ever see two different outputs, it's balanced (certain). If all \(k\) outputs are the same, it's probably constant. After \(k\) queries all returning the same value, the probability of it being balanced is at most \(2^{1-k}\) (since a balanced function would need to "hide" its other output values in the unqueried half). With \(k = O(1)\) queries you get high confidence.
The speedup:
This is why Deutsch-Jozsa is considered a "proof of concept" rather than a practical speedup. The exponential separation exists only if you insist on determinism. In practice, a classical algorithm with 99.99% confidence after 20 queries is good enough. The real practical quantum speedups (Shor's, Grover's) hold even against probabilistic classical algorithms.
Explain why having fewer quantum gates for the QFT than classical operations for the FFT is not sufficient to claim that quantum computers compute the Fourier transform faster. Hint: think about input and output.
The QFT circuit on \(n\) qubits uses \(O(n^2)\) gates to transform \(N = 2^n\) amplitudes, while the classical FFT uses \(O(N \log N) = O(n \cdot 2^n)\) operations on \(N\) numbers. Naively, this looks like an exponential speedup. But it isn't, because of the input/output bottleneck:
Input problem: The QFT acts on the \(2^n\) amplitudes of an \(n\)-qubit state. To load an arbitrary classical vector \((a_0, a_1, \ldots, a_{N-1})\) into a quantum state \(\sum_j a_j \ket{j}\), you need a state preparation procedure. In general, preparing an arbitrary \(N\)-dimensional quantum state requires \(O(N)\) gates — you've already lost the exponential advantage just loading the data.
Output problem: After the QFT, the Fourier coefficients are encoded in the amplitudes of the quantum state. But you cannot read out all \(N\) amplitudes. Measurement gives you a single basis state \(\ket{j}\) sampled with probability \(|a_j|^2\). To reconstruct all \(N\) Fourier coefficients with good accuracy, you'd need \(O(N)\) repetitions of the entire computation — again erasing the speedup.
The gate count comparison is misleading because the classical FFT takes \(N\) numbers as input and produces \(N\) numbers as output, all accessible. The QFT takes an already-prepared quantum state and produces another quantum state whose amplitudes are inaccessible individually. You're comparing a subroutine (QFT) with a complete algorithm (FFT).
Where the QFT IS useful: When the input state is already prepared as part of a larger quantum algorithm (not from classical data), and you don't need all the output amplitudes — you just need a measurement outcome that reveals some global property (like a period). This is exactly what happens in Shor's algorithm: the QFT is used as a subroutine within a quantum algorithm, and the measurement after the QFT extracts the period without needing to read all amplitudes.
Given that \(r\) divides \(N\), show that:
$$F_N \left(\sqrt{\frac{r}{N}} \sum_{x=0}^{N/r - 1} \ket{x \cdot r}\right) = \sqrt{\frac{1}{r}} \sum_{x=0}^{r-1} \ket{x \cdot N/r}$$
Hint: Apply the QFT definition and use the geometric series for roots of unity.
Setup: Let the input state be \(\ket{\psi} = \sqrt{\frac{r}{N}} \sum_{a=0}^{N/r-1} \ket{ar}\). This is a uniform superposition over states spaced \(r\) apart: \(\ket{0}, \ket{r}, \ket{2r}, \ldots, \ket{N-r}\).
Step 1: Apply the QFT definition.
$$F_N\ket{\psi} = \sqrt{\frac{r}{N}} \sum_{a=0}^{N/r-1} F_N\ket{ar} = \sqrt{\frac{r}{N}} \sum_{a=0}^{N/r-1} \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \omega_N^{j \cdot ar} \ket{j}$$
$$= \frac{\sqrt{r}}{N} \sum_{j=0}^{N-1} \left(\sum_{a=0}^{N/r-1} \omega_N^{jar}\right) \ket{j}$$
Step 2: Evaluate the inner sum using geometric series.
The inner sum is \(\sum_{a=0}^{N/r-1} (\omega_N^{jr})^a\). Let \(\alpha = \omega_N^{jr} = e^{2\pi i jr/N}\). This is a geometric series with ratio \(\alpha\) and \(N/r\) terms.
So the inner sum is \((N/r) \cdot \delta_{j, \text{multiple of } N/r}\).
Step 3: Substitute back.
Writing \(j = b \cdot N/r\) for \(b = 0, 1, \ldots, r-1\):
$$F_N\ket{\psi} = \frac{\sqrt{r}}{N} \sum_{b=0}^{r-1} \frac{N}{r} \ket{b \cdot N/r} = \frac{1}{\sqrt{r}} \sum_{b=0}^{r-1} \ket{b \cdot N/r}$$
This is exactly the target: a uniform superposition over states spaced \(N/r\) apart. \(\square\)
Physical interpretation: A periodic input with period \(r\) maps to a periodic output with period \(N/r\). This is the quantum version of the classical fact that the Fourier transform of a comb with spacing \(r\) is a comb with spacing \(N/r\). This is the core mechanism behind Shor's algorithm: the QFT converts periodicity in the computational basis into peaks at multiples of \(N/r\), from which the period \(r\) can be extracted by measurement.