Past exam of the computer science course of the University of Oxford / 2023 / Quantum information (A16608W1)

Source paper: www.whatdotheyknow.com/request/ba_computer_science_past_papers/response/2577745/attach/2/202402%20183%20CS%20Papers.zip?cookie_passthrough=1

Solutions to all three questions.^[ref] A product such as $|01⟩$ abbreviates a tensor product of quantum systems, with system labels ordered as indicated. Operations in a written sequence are applied from left to right in time; in an operator product, the rightmost operator acts first.

A density matrix is a complex $d\times d$ Hermitian matrix that is positive semidefinite and has unit trace:Equivalently, its eigenvalues are nonnegative and sum to one, with an orthonormal basis of eigenvectors.^[ref]

A basic measurement is specified by an orthonormal basis $\{|b_j⟩{\}}_{j=0}^{d-1}$. The Born rule for the density matrix $\rho$ gives the outcome probabilitiesThese probabilities are nonnegative by positive semidefiniteness and sum to one by the resolution of the identity and unit trace. In the computational basis, the answers are simply the diagonal entries ${\rho }_{jj}$.^[ref]

Expand the density matrix of the Bell state and take the partial trace over Alice's qubit:The orthonormality of the computational basis removes the off-diagonal terms. Thus Bob's reduced density matrix is the maximally mixed state

Write the proposed quantum state ensemble as $\{(|u⟩,p),(|v⟩,1-p)\}$ with normalized pure states, so thatTaking the expectation values in $|u⟩$ and $|v⟩$, and setting $c=|⟨u|v⟩{|}^2$, givesConsequently $p\le 1/2$ and $p\ge 1/2$. Substitution then gives $c=0$. The two pure states are therefore orthogonal, with equal probabilities:Conversely, any orthonormal basis of a qubit has projectors summing to $I$, so such a quantum state ensemble does give $I/2$. This proves the characterization of two-state ensembles of a maximally mixed qubit.

Alice uses conjugate-basis steering of a Bell pair. Write the desired orthonormal basis for Bob as $|\psi ⟩=a|0⟩+b|1⟩$ and $|{\psi }^{\perp }⟩=c|0⟩+d|1⟩$. Entrywise complex conjugation in the computational basis gives Alice's orthonormal basisFor either $|u⟩$ in Bob's chosen orthonormal basis, the corresponding unnormalized conditional quantum state isIts squared norm is $1/2$. Thus Alice measures in the complex-conjugate basis, obtaining the required Bob pure states with probability $1/2$ each. Averaging over Alice's undisclosed outcome leaves Bob's density matrix equal to $I/2$, consistent with the no-communication theorem.

Use deterministic two-qubit entanglement dilution, retaining the specified complex probability amplitudes. Alice implements a quantum instrument on $A$ with Kraus operatorsThe Kraus representation completeness condition holds even for complex $\alpha ,\beta$:To realize this using the permitted quantum gates and a basic measurement, Alice initializes an ancilla qubit $C$ to $|0⟩$. Conditional on her computational-basis state being $j$, she applies to $C$ the unitary matrixEach has orthonormal columns. Therefore $W=|0⟩⟨0{|}_A\otimes V_0+|1⟩⟨1{|}_A\otimes V_1$ is a unitary gate, withA computational-basis measurement of $C$ implements the desired quantum instrument. Its two unnormalized branches on $AB$ areEach has probability $1/2$. Alice sends her outcome $m$ as one classical bit. For $m=0$, both parties keep their qubits unchanged. For $m=1$, both apply a Pauli X gate, givingThus both outcomes produce the exact target using one classical bit and local operations. The construction includes $\alpha =0$ or $\beta =0$ and arbitrary relative quantum phases; it requires no quantum channel between the parties.

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.

A bipartite pure state is entangled exactly when it is not a product state: there are no normalized quantum states $|u{⟩}_A,|v{⟩}_B$ such thatEquivalently, its Schmidt rank exceeds one, or either reduced density matrix is a mixed state. This definition concerns quantum entanglement across the specified division into systems $A$ and $B$.

An entangling gate is a unitary transformation $U$ on two quantum systems for which at least one pure product input has an entangled output:It need not create quantum entanglement on every product state. For example, the controlled-NOT gate leaves $|00⟩$ a product state but maps $|+⟩|0⟩$ to a Bell state, so it is an entangling gate.

The sign factor separates as $(-1{)}^{x+y}=(-1{)}^x(-1{)}^y$. Consequently the quantum state factors into a tensor product of quantum systems:It is a product state, so it is not entangled.

Grouping by the first qubit givesThe vectors on both sides form orthonormal bases, so this is a Schmidt decomposition with two nonzero Schmidt coefficients $1/\sqrt{2}$. Hence the state is maximally entangled. Independently, its coefficient matrix has determinantwhich excludes a product state by the two-qubit product-state determinant criterion. Each reduced density matrix is $I/2$.

Alice holds the input qubit $Q$ in $|\psi {⟩}_Q=a|0⟩+b|1⟩$ and her half $A$ of a shared Bell pair $|{\varphi }_{+}{⟩}_{AB}$; Bob holds $B$. Alice applies a controlled-NOT gate $Q\to A$, then a Hadamard gate on $Q$. In the system order $Q,A,B$, the initial quantum state isAfter these two quantum gates, direct expansion yields the quantum teleportation identityAlice performs computational-basis measurements on $Q,A$, and sends the two classical bits $m,n$ to Bob. Each outcome has probability $1/4$, independently of the input pure state. Bob applies the indicated Pauli gates: first $X^n$, then $Z^m$, so his total correction is $Z^m{X}^n$. In every branch,This proves exact quantum teleportation using one Bell pair and two classical bits. Alice's original qubit has been measured; the protocol transfers the quantum state without leaving her another copy.

Write the arbitrary initial pure state asThe reference vectors need not be normalized or orthogonal. By linearity, the same quantum teleportation calculation, with the identity operator on $R$, gives the post-gate quantum stateThus each outcome still has probability $1/4$. Bob's Pauli gate correction leaves the normalized joint quantum stateAll operations act trivially on $R$, so the result is independent of its holder or location. This establishes teleportation as an identity channel on a reference, preserving quantum entanglement with the untouched reference. Since every corrected branch is the same, discarding the classical outcomes also leaves the required joint density matrix.

Combine the hypothetical protocol with superdense coding. Before a message is chosen, Alice and Bob share a further Bell pair $|{\varphi }_{+}{⟩}_{QR}$, with $Q$ at Alice and $R$ at Bob, in addition to any resources needed for the hypothetical quantum teleportation protocol. To encode two classical bits $u,v$, Alice applies the Pauli gates $Z_Q^u{X}_Q^v$, preparingThe four choices are the four mutually orthogonal Bell states. Alice now uses the hypothetical protocol to teleport $Q$ to Bob using only one classical bit. Its assumed preservation of the joint quantum state gives Bob both $B$ and $R$ inBob performs a Bell-basis measurement. Explicitly, a controlled-NOT gate $B\to R$, followed by a Hadamard gate on $B$, givesA computational-basis measurement therefore recovers both message bits with certainty after only one transmitted classical bit. The initial Bell pairs are shared before the message is chosen and carry no message themselves. This proves the classical communication lower bound for exact qubit teleportation: a perfect protocol preserving an external reference needs at least two transmitted classical bits.