Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 51 / 1

The answer qubit enters the Boolean quantum oracle in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, because the Pauli X gate followed by the Hadamard gate maps $|0⟩$ to $|-⟩$. Since $X|-⟩=-|-⟩$, quantum phase kickback multiplies the $|xy⟩$ component by $(-1{)}^{f(x,y)}$ and leaves the answer qubit unchanged. The two input qubits enter in the uniform quantum superposition $|++⟩$. ThusEquivalently, using the Controlled-Z gate and the Pauli Z gate,Here the exponent in the phase may be evaluated as an ordinary integer, since its parity agrees with the exclusive or expression. In particular, $d$ contributes only a global phase.

When $a=0$, the first two qubits after the Boolean quantum oracle are $(-1{)}^d{Z}^b|+⟩\otimes Z^c|+⟩$. The Hadamard gate obeys $H{Z}^t|+⟩=|t⟩$ for $t\in \{0,1\}$. Applying the Walsh-Hadamard transform therefore givesConsequently the quantum measurement in the computational basis has the deterministic outcomesThese four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.

All four promised functions have $a=1$. Use quadratic Boolean phase cancellation: apply a Controlled-Z gate to remove the phase $(-1{)}^{xy}$, then apply the Walsh-Hadamard transform. With the rightmost gate acting first, chooseBecause $C_Z^2=I$ and the Controlled-Z gate commutes with the Pauli Z gates,The quantum measurement in the computational basis consequently producesEach answer occurs with probability one for its promised Boolean quantum oracle.

In the ordered computational basis $00,01,10,11$, the first two qubits of $|{\psi }_{0000}⟩$ have amplitudes $(1,1,1,1)/2$, while those of $|{\psi }_{1111}⟩$ have amplitudes $(-1,1,1,1)/2$. Both have the same normalized answer qubit $|-⟩$. Their inner product is thereforeA common unitary operator $U\otimes I$ preserves this nonzero inner product. To distinguish the alternatives with certainty using the prescribed quantum measurement in the computational basis, their first-register outcome supports would have to be disjoint: every outcome possible under one alternative must be impossible under the other. Vectors with disjoint computational basis supports have zero inner product, contradicting its preservation. Thus no such $U$ exists. This is also an instance of perfect discrimination of pure states requires orthogonality; allowing a more general measurement in quantum mechanics would not rescue this pair of states. The obstruction concerns these prepared oracle-output states, rather than every conceivable oracle-query procedure.

A classical query with known answer bit $z$ reveals exactly the one bit $f(x,y)$, since it returns $z\oplus f(x,y)$. For the four promised Boolean functions, the value table isEvery possible first query splits the four alternatives into one class of size one and another of size three. On the branch with three remaining alternatives, a second binary answer can separate at most two classes. At least two alternatives therefore still agree on that branch, regardless of how the second query was chosen adaptively. This decision tree argument proves that a procedure guaranteed to identify every alternative needs at least three queries in the worst case.

For sufficiency, query $00,01,10$. The three-bit answer strings for $1,y,x,x\oplus y$ are respectively $111,010,001,011$, which are all distinct. Hence the exact classical worst-case query requirement is three. Some individual branches can terminate sooner; the lower bound does not assert that every oracle requires three queries.