Past exam of the computer science course of the University of Oxford / 2023 / Quantum information / 2

In the ordered computational basis $|0⟩,|1⟩$, the Pauli X gate, Pauli Y gate, Pauli Z gate, Hadamard gate and T gate areIn the ordered two-qubit computational basis $|00⟩,|01⟩,|10⟩,|11⟩$, with the first qubit controlling the second, the controlled-NOT gate isHere the T gate uses the conventional representative with first diagonal entry one; another common representative differs only by a global phase.

Initialize one qubit in $|0⟩$, then apply a Hadamard gate, a T gate, and a Hadamard gate, in that temporal order. Defining the Pauli X eigenstates $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$, the successive quantum states are

Initialize three qubits in $|000⟩$. Apply a Hadamard gate on the first, then controlled-NOT gates $1\to 2$ and $1\to 3$:Apply the T gate twice to the first qubit. Because $T^2=\mathrm{diag}(1,i)$, the resulting GHZ state with the specified relative quantum phase is

Initialize two qubits in $|00⟩$. A Hadamard gate on the first followed by a controlled-NOT gate $1\to 2$ prepares the Bell state $|{\varphi }_{+}⟩$. The permitted T gates and Hadamard gates implement the needed Pauli gates exactly:Apply $T_1^4$, followed by $H_2,T_2,T_2,T_2,T_2,H_2$. These are a Pauli Z gate on the first qubit and a Pauli X gate on the second, givingEvery operation is in the allowed gate set; no quantum measurement or probabilistic branch is needed.

Use three-way qutrit sign-flip discrimination. Prepare the qutrit in the uniform superposition stateFor an unknown label $j\in \{0,1,2\}$, the supplied unitary operator is $U_j=I-2|j⟩⟨j|$. Apply it once and then apply the known inversion about the meanSince $D^{†}=D$ and $D^2=I$, this is an allowed unitary transformation. Using $⟨s|j⟩=1/\sqrt{3}$ givesPerform a computational-basis measurement and guess that its outcome is the unknown label. The Born rule givesEach incorrect outcome has probability $1/27$, verifying normalization. The success probability is $25/27$ separately for every label, so no assumption about their prior probabilities is needed.

We prove the one-query constancy obstruction for phase oracles while allowing arbitrary quantum ancillas. By purification of a density operator, the quantum state immediately before the sole query can be taken asThe ancilla vectors need not be normalized or orthogonal. Classical randomness and earlier quantum measurements can be included in additional ancillas; allowing access to these systems only gives the proposed algorithm more power.

For the zero constant function, the phase oracle is $I$, leaving $|\Psi ⟩$ unchanged. For each $j$, consider the Boolean function that is one at $j$ and zero elsewhere. Since $M>2$, it is nonconstant, and its phase oracle producesAny later fixed unitary transformation preserves these inner products. An arbitrary final quantum measurement cannot distinguish the constant output from each nonconstant output with certainty unless they are orthogonal, by perfect discrimination of pure states requires orthogonality. Explicitly, an accepting POVM effect $E$ would satisfy $E|\Psi ⟩=|\Psi ⟩$ and $E|{\Psi }_j⟩=0$, forcing $⟨\Psi |{\Psi }_j⟩=0$.

Therefore exact classification requires $p_j=1/2$ for every $j$. Summing giveswhich contradicts $M>2$. Thus one query cannot decide constancy with certainty. The other constant function gives $-I$, differing only by a global phase, so it does not change the argument. For comparison, $M=2$ permits $p_0=p_1=1/2$; the impossibility arises from demanding the test work for every nonconstant Boolean function.