Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 / 3 / b

Let $|u_i⟩$ denote the specified image of $|i⟩|0⟩$. Its components comprise $N-1$ distinct ordered-pair basis states, each with coefficient $\pm N^{-1/2}$, together with $|0,0⟩$ with coefficient $N^{-1/2}$. Hence $⟨u_i|u_i⟩=1$.

For distinct indices $i<j$, only two output basis states occur in both images. Their common $|0,0⟩$ contributions have product $1/N$, while the $|i,j⟩$ contributions have product $-1/N$. ThusThe specified map is therefore a linear isometry on the $N$-dimensional input subspace. Complete the input vectors $|i,0⟩$ to an orthonormal basis of the $N^2$-dimensional space, and independently complete their images $|u_i⟩$ to another orthonormal basis. Map the first full basis to the second. This is a unitary extension of a finite-dimensional isometry, giving the required $\tilde{U}$. The prescribed columns are orthonormal, so a full unitary extension exists. Its construction depends only on $N$, not on the unknown string, and is permitted by the question's exact-unitary assumption.

Let $w$ be the number of ones. The displayed output state assigns the outcome $(0,0)$ probabilityFor a constant string, $w=0$ or $N$, so this probability is one. For a balanced string, $w=N/2$, so it is zero. Under the promise, $(0,0)$ certifies a constant string, and any other possible outcome certifies a balanced string. A nonzero ordered-pair outcome must have $i<j$ and ${\hat{x}}_i-{\hat{x}}_j\ne 0$, which also certifies $x_i\ne x_j$ without separately reading either bit. This is the fact used by opposite-pair elimination for exact quantum balance testing.

Maintain a known list of the still-active indices, initially all $N=2K$ positions. On a list of even size $M$, perform the three-step construction with $M$ replacing $N$. A known reversible relabeling prepares and queries the corresponding original indices, so quantum phase kickback still needs only one call to $O_{\mathbf{x}}$. The full unitary extension for that current size is independent of the remaining unknown values. It is allowed even when $M$ is not a power of two.

If the measurement gives $(0,0)$, its amplitude is the imbalance divided by $M$. A balanced active string has zero such amplitude, so an observed zero pair certifies that the active string is unbalanced. Return unbalanced immediately. No probability-of-error estimate is needed: an impossible outcome never occurs in the balanced case.

Otherwise the measured pair corresponds to two opposite bits. Delete those two indices and repeat. Each deletion removes exactly one zero and one one, preserving the difference between their counts. Thus the active string is balanced if and only if the original one is balanced. If all indices are removed, return balanced. This is opposite-pair elimination for exact quantum balance testing; it never requires determining which member of a deleted pair is zero.

Each query either terminates with a valid imbalance certificate or reduces the active length by two. After at most $K$ opposite-pair outcomes the active list is empty. The result is certain on every input, with worst-case query countThe same argument includes the $M=2$ last step: equal bits give $(0,0)$ with certainty, while opposite bits give the sole nonzero pair with certainty. There is no additional final query. The measurement probabilities are normalized because $(M-2w{)}^2+4w(M-w)=M^2$.