Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 10E (Quantum Information and Computation)

The all-zero amplitude is $2^{-n}{\sum }_x(-1{)}^{f(x)}=1-2k/2^n$, so its probability is $(1-2k/2^n{)}^2$. For a general nontrivial $k$ it lies strictly between zero and one.

For constant $f$, $k=0$ or $2^n$, so the all-zero result occurs with probability one.

For perfect balance, $k=2^{n-1}$ and the all-zero probability is zero. For other balances the one-shot outcomes overlap the constant case. Repeat Deutsch-Jozsa algorithm and declare nonconstant upon any nonzero result. Constants are never misclassified; a $k$-balanced function fails after $R$ trials with probability $q^R$, $q=(1-2k/2^n{)}^2$. It suffices that $R\ge \log ϵ/\log q$, using that many oracle calls.