Given this method for splitting all the strings into pairs based on the first $(n-1)$ bits, labelled by $\tilde{\mathbf{x}}$, we can provide a fairly concrete scheme for finding the secret combination to our lock. Let $H_n$ refer to the Hadamard acting on the last qubit. Since $H\vert 0\rangle = \vert +\rangle$, if the $n$-th qubit is in state $|0\rangle$, acting with $H_n$ gives us $\vert +\rangle$ on that qubit, and hence $\vert \psi_{\tilde{\mathbf{x}}}\rangle = H_n\vert \tilde{\mathbf{x}}0\rangle$. Applying the oracle yields $$ \begin{align*} U_f\vert \psi_{\tilde{\mathbf{x}}}\rangle & = \vert \tilde{\mathbf{x}}\rangle \otimes \frac{1}{\sqrt{2}}\left((-1)^{f(\tilde{\mathbf{x}}0)}\vert 0\rangle + (-1)^{f(\tilde{\mathbf{x}}1)}\vert 1\rangle\right) = \\ & = \begin{cases} \pm\vert \tilde{\mathbf{x}}\rangle \otimes \vert -\rangle & \text{if solution present;} \\ \vert \tilde{\mathbf{x}}\rangle \otimes \vert +\rangle & \text{otherwise.} \end{cases} \end{align*} $$ If we apply $H_n$ once more, we convert the $\vert +\rangle$ state to $\vert 0\rangle$, and the $\vert -\rangle$ state to $\vert 1\rangle$: $$ \begin{align*} \vert \varphi\rangle & = H_n U_f \vert \psi_{\tilde{\mathbf{x}}}\rangle \\ & = \begin{cases} \pm \vert \tilde{\mathbf{x}}1\rangle & \text{solution present} \\ \pm \vert \tilde{\mathbf{x}}0\rangle & \text{otherwise.} \end{cases} \end{align*} $$ So we can simply measure the last qubit and see what we get! In case you find the math a bit dry, here is a circuit diagram to indicate what is actually going on:

Although we can speed up our lock-breaking by testing in pairs, we will still need to test many pairs before finding the solution! The next exercise tells us how many pairs we will need to test on average. ***Exercise A.3.2.*** When searching for an $n$-bit solution, how many queries are required on average when we test in pairs?

Hint.

Suppose that each position in the list is equally likely, and compute the expected position.

Solution.

Let $L = 2^{n-1}$, the number of pairs. If the position $\ell$ of the combination is random and uniform in the list, the average position is $$ \begin{align*} \sum_{\ell=1}^L \frac{\ell}{L} & = \frac{1}{L}(1 + 2 + \cdots + L) = \\ & = \frac{1}{2L} L(L + 1) = \\ & = \frac{1}{2}(L+1). \end{align*} $$ Thus, the average number of pairs we will need to test is $(L+1)/2 = (2^{n-1}+1)/2$. ▢

Codercise A.3.1 — The oracle in the circuit

Codercise A.3.2 — Breaking the lock a bit faster

Testing in pairs

A pair-programming scheme