Exercises: The First Quantum Algorithms

All of these run on a simulator. Solutions to starred exercises are in Answers to Selected Exercises.

Warm-up

20.1 ★ Implement Deutsch–Jozsa for $n = 3$ with a constant-0 oracle, a constant-1 oracle, and a balanced oracle. Report $P(\text{all zeros})$ for each and confirm the values are exactly 1 and exactly 0.

20.2 Draw the Deutsch–Jozsa circuit for $n = 3$ and label the three steps of §20.1's pattern. Which gates belong to which step?

20.3 ★ Substitute a constant $f$ into the amplitude formula $\frac{1}{2^n}\sum_x(-1)^{f(x)+x\cdot y}$ and show algebraically that the $y = 0$ amplitude is $\pm1$ and every other amplitude is 0.

20.4 ★ Do the same for a balanced $f$ and show the $y = 0$ amplitude is exactly 0.

20.5 Why does the algorithm need only one shot rather than many? Contrast with a variational algorithm (Chapter 24), which needs thousands.

Bernstein–Vazirani

20.6 ★ Implement Bernstein–Vazirani and recover secrets of 4, 6, and 8 bits. Confirm every shot returns the same answer.

20.7 The oracle for secret $s$ is a CX from qubit $i$ whenever $s_i = 1$. Explain why the measured bitstring equals $s$, using phase kickback (Chapter 19 §19.3).

20.8 ★★ Build a Bernstein–Vazirani oracle for $s = 0$ (the all-zeros secret). What does the circuit reduce to, and what does the algorithm return?

20.9 ★★ Bernstein–Vazirani gives an $n \to 1$ speedup. Compute the query counts for $n = 10$, 100, and 1000, and state whether this changes complexity class. Compare with Deutsch–Jozsa's separation at the same sizes.

20.10 ★★★ The recursive Bernstein–Vazirani problem gives a super-polynomial separation. Read the construction and implement the depth-2 version for small $n$. What does recursion buy that the flat version does not?

Simon's algorithm

20.11 ★ Implement Simon's oracle for $n = 3$, $s = 110$ and verify by brute force that $f(x) = f(x \oplus s)$ for all $x$.

20.12 ★ Run Simon's circuit 200 times at $n = 4$, $s = 1011$. Confirm that every measured $y$ satisfies $y \cdot s = 0 \pmod 2$, and that exactly $2^{n-1}$ distinct values appear.

20.13 ★★ Implement Gaussian elimination over $\mathbb{F}_2$ and test it on hand-constructed systems, including an underdetermined one. What should it return when the rank is too low?

20.14 ★★ Implement the fixed-shot version — take exactly $n-1$ measurements and solve — and run it 100 times at $n = 6$. What fraction succeeds? Compare to $\prod_{k=1}^{n-1}(1 - 2^{-k}) \approx 0.2888$.

20.15 ★★ Now implement the rank-based version and run it 100 times at the same size. Report the success rate and the mean number of shots consumed. Confirm the mean is close to $n - 1 + O(1)$.

20.16 ★★ How often does 0…0 appear in your measurements, and why is its frequency what it is? What happens if you count it as an equation?

20.17 ★★★ Simon's algorithm assumes $s \neq 0$. What does the circuit produce when $s = 0$ (so $f$ is one-to-one)? Can you detect this case from the measurements alone?

The promise

20.18 ★ Build an oracle that is neither constant nor balanced (mark exactly one input of 16) and run Deutsch–Jozsa on it. Report $P(\text{all zeros})$ and what the standard rule concludes.

20.19 ★ Count the distinct outcomes for a constant oracle, a balanced oracle, and your broken one. Explain why the count alone is a promise-violation detector.

20.20 ★★ Implement check_promise(truth_table, kind) that brute-forces whether a function is constant, balanced, or neither. Explain why the algorithm itself cannot do this.

20.21 ★★ Add the third branch to your Deutsch–Jozsa classifier and verify it disagrees with the two-branch rule exactly on promise-violating inputs. What tolerance should the branch use, and what does it depend on?

20.22 ★★ Build oracles that violate the promise by varying amounts — 1, 3, 5, and 7 marked inputs out of 16 — and plot $P(\text{all zeros})$ against the number of marked inputs. At what point does the algorithm's answer become accidentally right?

20.23 ★★★ Bernstein–Vazirani also has a promise: $f$ must be a parity function. Construct a non-parity $f$, run the algorithm, and characterize the output distribution. Is the violation as visible as Deutsch–Jozsa's?

Project

20.24 ★★ (Project Checkpoint) Build vqelab/algorithms.py with deutsch_jozsa, bernstein_vazirani, simon, solve_f2, and check_promise. Write tests asserting:

1. Constant oracles give $P(\text{all zeros})$ exactly 1, with exactly one distinct outcome.
2. Balanced oracles give exactly 0, with exactly one distinct outcome.
3. A promise-violating oracle is classified PROMISE VIOLATED.
4. The naive two-branch rule would have said "balanced" — and the honest rule disagrees.
5. check_promise correctly identifies constant, balanced, and neither.
6. check_promise recognizes a parity function and rejects a non-parity one.
7. Bernstein–Vazirani recovers the secret on every shot for $n = 4, 6, 8$.
8. solve_f2 solves a known system and reports an underdetermined one as None.
9. Simon recovers the period for several $(n, s)$ pairs.
10. Every Simon measurement is orthogonal to the period.
11. Simon uses exactly $n-1$ equations but may consume more shots, and reports both.
12. A zero period raises.

Tests 3, 4, and 11 encode this chapter's two case studies.

20.25 ★★★ Extend algorithms.py with deutsch_jozsa_from_truth_table(table) that builds the oracle from an arbitrary truth table, checks the promise first, and refuses to run if it is violated — raising with the count of marked inputs. Compare the developer experience to the version that silently answers.

Going further

20.26 ★★★ All four algorithms are instances of the hidden subgroup problem over $(\mathbb{Z}_2)^n$. State each one's hidden subgroup. Then read what Shor's algorithm looks like in this language (the group is $\mathbb{Z}_N$) and explain why the abelian case is the solved one.

20.27 ★★★ Chapter 19 §19.5 measured that an $n$-input oracle costs thousands of T gates. Apply that to Deutsch–Jozsa at $n = 20$: what is the fault-tolerant cost of the "one query" the algorithm famously needs? Compare with $2^{19}+1$ classical evaluations of a cheap function.

20.28 ★★★ Simon's algorithm needs $O(n)$ queries, but each query is an oracle call. Using Chapter 19's oracle_cost, estimate the total T count for Simon at $n = 20$ and compare against the classical $2^{10}$ collision search. Which wins, and at what $n$ does the answer change?