Exercises: Chapter 12 — The Deutsch-Jozsa and Bernstein-Vazirani Algorithms — Simple Problems, Exponential Speedup, and the First Taste of Quantum Advantage

Exercise 12.1 — Deutsch-Jozsa with Noisy Oracles Suppose the oracle has a small probability $\varepsilon$ of giving the wrong answer (i.e., $U_f$ is replaced by a noisy channel). Analyze how this affects the Deutsch-Jozsa algorithm. At what value of $\varepsilon$ does the quantum algorithm lose its advantage? Implement a noisy oracle in Qiskit and measure the success probability as a function of $\varepsilon$.

Exercise 12.2 — Generalized Bernstein-Vazirani Consider the generalized Bernstein-Vazirani problem where $f(x) = s \cdot x \oplus b$ for a hidden string $s \in \{0,1\}^n$ and a hidden bit $b \in \{0,1\}$. Show that the standard Bernstein-Vazirani circuit still recovers $s$, but $b$ is lost. Design a modified circuit that recovers both $s$ and $b$ in one query.

Exercise 12.3 — Oracle Synthesis Write a Qiskit function that, given an arbitrary 3-bit Boolean function specified as a length-8 list of output bits, synthesizes the oracle $U_f$ using at most 8 multi-controlled gates. Test it with the Deutsch-Jozsa algorithm on several constant and balanced functions.

Exercise 12.4 — Fourier Duality Prove that the Hadamard transform is self-inverse: $H^{\otimes n} H^{\otimes n} = I^{\otimes n}$. Use this to explain why applying $H^{\otimes n}$ before and after the oracle in the Deutsch-Jozsa algorithm converts the phase information $(-1)^{f(x)}$ into computational basis information.

Exercise 12.5 — Promise Problem Classification The Deutsch-Jozsa problem relies on a promise (the function is either constant or balanced). What happens if you run the Deutsch-Jozsa circuit on a function that is neither constant nor balanced? Compute the probability of measuring $|0\rangle^{\otimes n}$ for a function where a fraction $p$ of inputs give $f(x) = 1$. Implement and test in Qiskit.

Exercise 12.6 — Detailed Derivation for n=3 Trace through the full Deutsch-Jozsa algorithm for $n = 3$ with the balanced oracle $f(x) = x_0 \oplus x_1$. Compute the state at each step and verify that the probability of measuring $|000\rangle$ is 0.

Exercise 12.7 — Inner Product Oracle Circuit For $n = 4$ and $s = 1101$, draw the complete Bernstein-Vazirani circuit, showing all CNOT gates. How many CNOT gates are needed? What is the total gate count (including Hadamard gates)?

Exercise 12.8 — Deutsch-Jozsa with Probabilistic Oracles Consider a probabilistic oracle that computes $f(x)$ with probability $1 - \varepsilon$ and outputs a random bit with probability $\varepsilon$. Derive the probability that the Deutsch-Jozsa algorithm correctly identifies a constant function as constant, as a function of $\varepsilon$ and $n$.

Exercise 12.9 — Relationship to Simon's Problem Simon's problem is defined as follows: given $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that $f(x) = f(y)$ iff $x \oplus y \in \{0^n, s\}$ for some hidden $s$, find $s$. Explain how Simon's problem generalizes Bernstein-Vazirani. What happens to Simon's algorithm when $s = 0^n$?

Exercise 12.10 — Query Complexity Lower Bounds Prove that any classical randomized algorithm for the Bernstein-Vazirani problem requires at least $n$ queries in the worst case, even with bounded error. Hint: use an information-theoretic argument based on the fact that each query reveals at most 1 bit of information about $s$.