The armchair quantum physicist

Alice sends Bob one bit and tells him nothing new — yet he guesses right more often than he should. A small quantum advantage, in the simplest game there is.

Alice and Bob play a collaborative version of (Quantum)SeaBattle with one bit of communication. We hand them a quantum resource and show that the slightest bit of quantum already helps them outperform the classical benchmark — not by telling Bob more, but by letting him choose what his information means.

Stripped of the ships, the QSeaBattle game is a ‘random access code’ [1]: Alice holds a bit string that is unknown to Bob. Bob gets an index Alice cannot see in advance, and he must guess the bit at that index. Alice can send a single bit to support Bob. The optimal classical strategy is the majority strategy (see our earlier post): Alice sends the bit that occurs most, and Bob follows it. This is proven to be the optimal strategy for classical communication [1].

In this post, we will discuss what happens when Alice and Bob share an entangled quantum resource. The short version: the moment their shared resource crosses out of the classical world, they beat the majority strategy — but this is not because Alice can share more information with Bob.

A Magical Box for Two Bits

Let us build from the smallest case. Alice has two bits; Bob is to guess one of them. Around 2009, Pawłowski and Żukowski [2] wrote down exactly the resource we need. They built it as a ‘quantum device’ from an entangled photon pair. We will skip the photons and jump straight to what the device does.

Alice feeds her two bits into her half of the device and out comes a single bit — a 1 or a 0 — which she sends to Bob. Alice’s device has a dial, like the one used to aim at a point on a globe. Bob feeds Alice’s bit into his half of the device, and indicates which bit he is after: Alice’s first, or her second.

Alice’s dial does not decide which bit Bob receives — Bob does that, after he knows his index. What Alice’s dial decides is how much of each bit is on offer. Point the dial toward a pole and the box hands Bob her first bit with certainty … rotate it by a quarter turn, and it is the other way round. Aim halfway between and both bits are equally available — each at a win rate of about 85%, whichever bit Bob picks. Alice decides how much information he gets; Bob decides what he wants.

Alice decides how much he gets; Bob decides what he wants.

As with quantum resources generally, this is a use-once device. Once Alice sets her dial and Bob makes his measurement, the shared resource is consumed. Bob cannot first extract one bit and then return to his half of the device to extract the other bit. He has to choose which question to ask — and once he has chosen, he cannot go back and find out what would have happened had he made the other choice.

The Dial Draws a Sphere

Alice’s dial is not just a metaphor — it is the picture. For any strategy and any single bit, we can score how well Bob tracks that bit with one number, the advantage, running from −1 to +1. Zero is a pure guess; plus one is certainty; minus one is its mirror. Advantage (cᵢ) is the win rate Pᵢ rescaled: Pᵢ = ½(1 + cᵢ). Call the advantages for the two indices (c₁,c₂). As Alice sweeps her dial from pole to pole through angle θ, these are

c₁ = cos θ, c₂ = sin θ,

so c₁² + c₂² = 1. Every dial setting is a point on a circle in the advantage space (see Figure 1). The two poles are the two clean bits; the equator is the even blend. Note that the length is fixed at one — Alice chooses its direction, never its length.

Now overlay what a classical resource can reach. Without the box, Alice’s one bit can lean toward one index or the other, but it must trade — the sum |c₁|+|c₂| cannot exceed one, so the classical strategies fill a diamond. Majority sits at the (1, 1) direction of that diamond, where the advantage is spread evenly. The circle bulges outside the diamond everywhere except at the four corners, where they touch. Those corners are the classical strategies that give up on one bit entirely to nail the other. Everywhere in between, the circle is strictly further out.

That crescent between diamond and circle is the whole point. Every strategy inside it is reachable with the quantum box and impossible classically — no classical resource ever pushes past |c₁|+|c₂| = 1. It appears already at n = 2, the smallest game there is.

The circle is not merely a convenient picture. It is the boundary of what this quantum resource can reach in advantage space.

Now consider what the box does on three bits. For two bits, Alice needed only one angle — a circle is a globe seen edge-on. Pawłowski and Żukowski’s second primitive [2] handles three bits, and there Alice uses both latitude and longitude to aim anywhere on an actual sphere. The three advantages (c₁, c₂, c₃) now satisfy c₁² + c₂² + c₃² = 1, and the classical strategy space is a rhombic dodecahedron sitting inside that sphere, the two touching only at the six poles. Same crescent, one dimension higher.

So the pattern is not an accident of two bits. Wherever the classical strategies fill a flat-faced polytope, the quantum box extends beyond its faces, reaching points that are classically impossible.

Bob Knows No More — He Just Chooses

So, does the quantum version win by telling Bob more? Did the ‘entanglement’ somehow function as a transmission channel for information from Alice to Bob?

It does not. Alice still sends one bit. The quantum advantage does not come from increasing that communication. The box does not stuff more of the board into the message; it is a strictly no-signalling device and, by itself, cannot transmit information from Alice to Bob. To see what does change, let us go back to the geometry.

In both the classical and the quantum case, Alice fixes a point in advantage space— she aims her dial before knowing Bob’s index. Bob then picks which coordinate axis to read. He does not move the point; he chooses which component of it to extract. When he picks the first bit, he reads the c₁ component. When he picks the second, he reads c₂. The point is the same either way.

This is exactly why the sphere beats the diamond. On the diamond, Alice’s advantages are budgeted linearly: |c₁| + |c₂| ≤ 1, so giving more to one axis takes from the other directly. On the sphere, the budget is quadratic: c₁² + c₂² = 1, so both components can be larger simultaneously. The sphere is rounder, but touches the diamond on the axis. Alice doesn’t have more to give — she just loses less in the split.

The caveat, as mentioned earlier, is that to reach the sphere Bob has to use his quantum box, consuming the shared resource in the process. With a classical strategy, the information he receives is reusable: he can extract one index and then use the same information to ask about another. With the quantum box, he gets only one choice. Once he extracts one index, he loses the opportunity to find out what would have happened had he chosen another.

Let’s look at a small game where, with the quantum box, Alice and Bob beat the majority strategy. We use a 4-cell board and compare two strategies. In the first, Alice plays majority on the full board. In the second, she plays majority only on the first two bits, and when these two bits tie, she falls back to the 2-bit quantum primitive from Figure 1 on the last two bits. In this hybrid strategy, classical majority handles the first part of the board; the quantum box handles the tail.

Figure 3 shows the starting point. Before Alice shares anything, Bob’s knowledge is uniformly distributed — each board is equally likely.

Based on Alice’s bit, Bob can form a posterior — a probability over which string she holds. In Figure 4, we show Bob’s posterior if Alice sends a ‘1’ under the classical majority strategy. He knows that she cannot hold a board with no or one ‘1’ (for then she would have sent a ‘0’), and is more likely to hold a board with a majority of 1’s than a tied board. Based on this, he has an advantage of 0.38, uniform over all indices.

Classically, Bob has one lookup table, fixed when Alice created her bit. Whatever index he is later handed, he reads the same table, so his posterior is the same histogram every time. His decoder was frozen at coding.

Now look at what happens with the quantum box. Alice has fixed her point on the sphere — she aimed the dial before knowing Bob’s index. But Bob, when he learns his index, picks which axis to project that point onto. He does not move the point. He reads one component instead of another. He can — after the fact — change the meaning of Alice’s bit.

He can — after the fact — change the meaning of Alice’s bit.

Figure 5 shows both options side by side. When Bob reads the c₃ component, his advantage on bit 2 sharpens to 0.707 (an 85% win rate) while bit 3 drops to a coin flip. When he reads c₄, they swap. Whichever suffix bit Bob chooses, the Shannon entropy is the same: 3.10 bits. What changes is where his advantage lies.

So the quantum advantage is not that Bob is told more. It is that classically the decoder is spent at coding — one table, no take-backs — while the quantum box lets Bob spend his budget after he knows which bit he wants. He projects Alice’s fixed point onto the axis that turned out to matter, and accepts knowing nothing on the one that did not. And all of this without a signal travelling from Bob back to Alice.

That, in one sentence, is what people mean by ‘quantum advantage’ in this game. Not more information — better-timed information.

Not more information — better-timed information

So, What Does the Slightest Quantum Buy?

We started with a classical shared resource that could protect Alice and Bob but never help them win. We end with a shared quantum box that lets them win the moment its correlations step outside the classical world. Drawn as geometry, the classical strategies fill a diamond and the quantum resource rounds it into a sphere; every point of the crescent between them is a game Alice can win more often, and none of it is reachable classically. And she wins it without Bob ever knowing more about her board — the box only lets his question arrive in time to shape what his answer means.

We have drawn the quantum boundary as a sphere — the outer edge of what the box can reach. But is that sphere really the edge of the possible? Nothing in the game so far forbids a stronger resource, one that would bulge past even the sphere, handing Bob correlations no quantum state can. Nature, it appears, refuses to go there — but why? And what would happen if a stronger-than-quantum resource could push beyond it? That we will pick up in a future post, when we introduce post-quantum resources.

The simulations and source code are available on GitHub.

References

[1] A. Ambainis, D. Leung, L. Mancinska, M. Ozols, Quantum Random Access Codes with Shared Randomness, arXiv:0810.2937 (2009).

[2] M. Pawłowski, M. Żukowski, Entanglement-assisted random access codes, Phys. Rev. A 81, 042326 (2010).