Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 59 (Quantum Information, Entanglement and Nonlocality)

Use $\oplus$ for exclusive or and regard all bits as elements of ${\mathbb{F}}_2$. For every public label $z\in \{0,1{\}}^m$, Alice computes the indicator functionwhile Bob computes $v_z(y)=f(z,y)$ from the known truth table. Exactly one of the $u_z(x)$ is one, so the separated Boolean decomposition is

For each $z$, they invoke an independent PR box with respective input bits $u_z(x),v_z(y)$ and receive outputs $a_z,b_z$. These satisfy $a_z\oplus b_z=u_z(x)v_z(y)$. Alice forms $A={⨁}_z{a}_z$, and Bob forms $B={⨁}_z{b}_z$. Taking the exclusive or of all box constraints provesAlice sends the single bit $A$. Bob combines it with his locally known $B$, obtainingThis is one-bit computation using Popescu–Rohrlich boxes. It uses $2^m$ boxes; decomposing by Bob's input instead gives $2^n$, so the smaller truth-table factorization uses at most $2^{\min (m,n)}$. No efficiency bound on local calculation or box use is needed for the stated unlimited resource.

Each PR box has uniform local output distributions regardless of the other party's input. Independent invocations therefore give Bob a uniform output string before the message, carrying no information about $x$. The useful correlation becomes accessible through Alice's final bit; the construction respects the no-signalling property of the boxes.

The target states here are qubit states, as appropriate to sharing singlet states of two qubits. Write $|\psi ⟩=\alpha |0⟩+\beta |1⟩$ and choose $|{\psi }^{\perp }⟩=-{\beta }^{\ast }|0⟩+{\alpha }^{\ast }|1⟩$. These form an orthonormal basis, and the shared Bell state can be expressed asAlice knows the classical description of $|\psi ⟩$, so she can perform the projective measurement in this basis. The outcome $|{\psi }^{\perp }⟩$ has probability $1/2$ and leaves Bob in $|\psi ⟩$, up to an irrelevant overall phase. Alice sends a success bit: one for this outcome and zero for the other. Bob keeps his qubit only on success. This proves heralded remote preparation of an arbitrary qubit:The other outcome leaves $|{\psi }^{\perp }⟩$ at Bob's side; the protocol makes no claim of success in that branch.

For a block of $n$ targets, share $n$ independent singlet states. Alice measures her $j$th qubit in the basis $|{\psi }_j⟩,|{\psi }_j^{\perp }⟩$. She sends one bit indicating whether all $n$ outcomes were of the successful kind. Because the pairs are independent, all-success has probability $2^{-n}$; conditioned on it, Bob's joint state is precisely ${⨂}_{j=1}^n|{\psi }_j⟩$. Thus one-bit heralding of a remote state preparation block givesOn failure Bob discards the block, so he does not need a list of which component states failed.

For asymptotic remote state preparation by block indexing, prelabel a supply of independent candidate blocks, each containing $n$ singlet states. Alice measures blocks until she finds the first all-success block, of index $J$. She does not send a flag after each trial. Since $q=2^{-n}$ is the success probability of each block,This geometric distribution is independent of the target states. The probability of never succeeding is ${\lim }_{k\to \infty }(1-q{)}^k=0$. Alice needs to communicate only $J$; Bob retrieves the labelled qubits in that block, and thereby knows that every requested state was prepared exactly.

Here is an explicit prefix code for a rare geometric success. Set $M=2^n$ and divide $J-1=MQ+R$, where $0\le R<M$. Encode $Q$ as $Q$ ones followed by zero, then encode $R$ in exactly $n$ bits. Bob can decode this without knowing any target-state description. The message length is $L=n+Q+1$. With $r=(1-q{)}^M$,Since $(1-1/M{)}^M\le e^{-1}$,This version succeeds exactly with probability one and has the stated expected classical communication cost. It consumes $n\mathbb{E}J=n{2}^n$ singlet states on average, compatible with the unlimited entanglement assumption.

There is also a fixed-message-length version. Try at most $K=n{2}^n$ candidate blocks and send the first successful index, or a zero codeword reporting that none succeeded. Encoding the $K+1$ possibilities uses $\lceil {\log }_2(K+1)\rceil =n+{\log }_{2}n+O(1)$ bits. Its failure probability isThus fixed-length communication approaches one bit per state with success probability tending to one; variable-length communication achieves exact eventual success with expected cost approaching one bit per state. Before the index arrives, Bob's unconditional state remains independent of the target descriptions, in agreement with the no-signalling theorem.

For the Kraus operators of the measurement in quantum mechanics, the Born rule givesThe density matrix $A_i\rho A_i^{†}$ is the unnormalized state of that outcome. It is positive, its trace is $p_i$, and completeness gives ${\sum }_i{p}_i=\mathrm{Tr}\rho =1$. There is no conditional state to assign to an event with $p_i=0$.

For a projective measurement, each $P_i$ is an orthogonal projection, satisfying $P_i=P_i^{†}=P_i^2$. Completeness becomes ${\sum }_i{P}_i=I$. Fix $v$ in the range of $P_j$. ThenSince $P_{j}v=v$, the $j$th summand already equals $\Vert v{\Vert }^2$. All other summands are nonnegative, so $P_{i}v=0$ for $i\ne j$. Consequently $P_i{P}_j=0$, and taking adjoints also gives $P_j{P}_i=0$. This proves the stronger completeness forces orthogonality of measurement projections:

For the unitary dilation of a measurement instrument, take a quantum ancilla with orthonormal states $|0⟩,|1⟩,\dots ,|n⟩$, initially in $|0⟩$. DefineThe completeness equation impliesso $V$ is an isometry. Its action on the input subspace can be extended to a unitary operator $U$ on the enlarged system:Choose orthonormal bases in the two complementary subspaces and map one to the other. Their dimensions agree; the extra unused quantum ancilla level also ensures this extension is possible for an infinite-dimensional system. After the coupling, the joint density matrix is

Now perform a projective measurement on the larger system, withThese are pairwise orthogonal and sum to the full identity. The unused $|0⟩$ level has zero weight in $\Omega$, so merging it into outcome one adds no probability. For every $i$,Its trace is $p_i$, and taking the partial trace over the quantum ancilla after normalization gives exactly ${\rho }_i$. Hence unitary coupling to an quantum ancilla, a projective measurement, and discarding the quantum ancilla reproduce both the probabilities and the conditional states of the general measurement. This is the instrument version of a Stinespring dilation, rather than a construction reproducing only the outcome probabilities.

For each hidden variable $\lambda$, a deterministic local hidden-variable model assigns values $a_i(\lambda ),b_j(\lambda )\in \{0,\dots ,d-1\}$ to all settings. The responses depend only on the local setting; their averaging distribution is setting independent, as required by measurement independence.

Let $T(\lambda )$ be the sum of the nonnegative modular representatives in the chained modular Bell inequality. Before reduction modulo $d$, the chain telescopes:Reduction changes this integer only by multiples of $d$. Since all reduced terms are nonnegative,The smallest possible nonnegative value in this residue class is $d-1$. Averaging over the hidden variable provesAdding local random seeds to $\lambda$ gives the same result for stochastic local hidden-variable theories.

For the coplanar qubit realization of the chained Bell inequality, shareAt angle $\theta$ in the $xz$ plane, use the projective measurement of the observableHere ${\sigma }_x,{\sigma }_z$ are Pauli matrices, and the classical bit $a$ records eigenvalue $(-1{)}^a$. Since $⟨{\sigma }_z\otimes {\sigma }_z⟩=⟨{\sigma }_x\otimes {\sigma }_x⟩=1$ and both crossed expected values vanish in this Bell state,The one-party expected values vanish, so the complete joint probabilities areFor binary outcomes, $[a-b]$ is one exactly when $a\ne b$, while $[b-a-1]$ is one exactly when $a=b$. Consequently

For $N\ge 2$, set $\delta =\pi /(2N)$ and choose Alice's angle ${\theta }_i=2(i-1)\delta$ and Bob's angle ${\varphi }_i=(2i-1)\delta$. Every adjacent pair $A_i,B_i$ or $B_i,A_{i+1}$ differs by $\delta$, giving expectation ${\sin }^2(\delta /2)$. The closing pair has angle difference $(2N-1)\delta =\pi -\delta$; its agreement probability is also ${\sin }^2(\delta /2)$. Thus every one of the $2N$ terms contributes equally:Indeed $\sin x<x$ for $x>0$, so this value is below ${\pi }^2/(8N)\le {\pi }^2/16<1$. For an explicit two-setting instance, Alice measures ${\sigma }_z,{\sigma }_x$ and Bob measures $({\sigma }_z+{\sigma }_x)/\sqrt{2},(-{\sigma }_z+{\sigma }_x)/\sqrt{2}$. The four relevant expected values sum toviolating the local bound one. At $N=1$ there is no violation; the two terms always sum to one. As $N\to \infty$, the displayed quantum value is asymptotic to ${\pi }^2/(8N)$ and approaches the algebraic lower bound zero.

The violation rules out a local hidden-variable theory with setting-independent preassigned local responses reproducing these quantum correlations. It does not permit faster-than-light communication: the joint formula gives each local outcome probability $1/2$, independent of the remote setting, as required by the no-signalling theorem. The contradiction concerns the joint correlations and the Bell assumptions, not the ability to send a signal.