Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 3 / d / Solution

Let $N_0,N_1$ be the two output counts. Choose a known preparation unitary F with $F|0⟩=N^{-1/2}{\sum }_x|x⟩=:|s⟩$. The Deutsch-Jozsa algorithm applies the supplied phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ and then $F^{†}$, declaring constant exactly for outcome 0. Its amplitude on that outcome isThis is the Deutsch-Jozsa test with an arbitrary uniform-state unitary. For $N=2^m$, the usual preparation is $F=H^{\otimes m}$; the argument itself needs only a uniform preparation on the stated N-dimensional space.

For an actually constant-up-to-k function, the two counts are $k$ and $N-k$, so the outcome-0 probability is $(1-2k/N{)}^2$. The error is returning the other label. ThereforeHere the possible count k is nonnegative, and the supplied bound implies $0\le k/N\le 1/8$. The error is consequently at most $7/16$; at $k=0$ it vanishes. This is the error conditional on the stated constant-up-to-k case, not an average over unspecified prior probabilities. For comparison, the printed balanced-up-to-k definition has count difference $\pm k$, so its outcome-0 probability would be $(k/N{)}^2$, not the expression for the constant-up-to-k case. No change to that promise definition is made.