Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-59/1/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 59 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use for exclusive or and regard all bits as elements of . For every public label , Alice computes the indicator functionwhile Bob computes from the known truth table. Exactly one of the is one, so the separated Boolean decomposition is
For each , they invoke an independent PR box with respective input bits and receive outputs . These satisfy . Alice forms , and Bob forms . Taking the exclusive or of all box constraints provesAlice sends the single bit . Bob combines it with his locally known , obtainingThis is one-bit computation using Popescu–Rohrlich boxes. It uses boxes; decomposing by Bob's input instead gives , so the smaller truth-table factorization uses at most . 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 . The useful correlation becomes accessible through Alice's final bit; the construction respects the no-signalling property of the boxes.
New to topics? Read the docs here!