Physicists Triumph at Guess My Number

Andrew M. Steane and Wim van Dam


This article appeared in Physics Today, February 2000, pages 35-39.

Quantum entanglement looks like telepathy when three physicists get together on a game show.

"Let's meet tonight's lucky contestants, ladies and gentlemen, all ready to play Guess my number, for the grand prize of ONE MILLION DOLLARS!"

The suave host turns to the group of three eager-looking people, and addresses the young woman first:
"You are Alice, from Cambridge Massachusetts, and, I think, a research physicist?"
"Yes."
"We don't get many of those on the show. Welcome to Guess my number."
"And next we have, Bob, a quantum mechanic from Oxford, England. Good to have you, Bob!"
Bob moves to join Alice as the host continues smoothly on to the last guest.
"And last, but not least, you are Charles, a computer scientist from New York. Welcome to Guess my number, Charles. It's good to have three people from such completely different walks of life..."
Charles begins to say "Well actually..." but the host moves straight on with the show, a professional who knows well the value of every second on prime-time television.
"Ladies and Gentlemen, in a moment Alice, Bob and Charles are going to step into the three isolation booths and play Guess my number. But before they do so, let's make sure we all remember the rules of the game."
"Alice, Bob and Charles, you are going to sit in our three isolation booths. You can each take anything you can carry into the booths, but once you are in there, you will not be able to communicate with each other, or with anyone else, except me, until the end of the game. Do you understand?"
A calm murmur of "Yes" comes from the contestants. They seem quite happy and eager to get on with the game.
"I see you are each carrying a small case. You seem all prepared! Now, one of you will be the decision maker. Have you already elected your decision maker?"
The contestants indicate their agreement that Alice will be the decision maker.
"Good! Now, this is how the game works. I have before me a collection of apples. Once you are all in the booths, I will take up to four apples from my collection, and divide them between you. To do this I may cut one or more apples in half, but I will not divide them into any smaller pieces. So each of you will receive either nothing, or half an apple, or one apple, or one and a half apples. Now, although you won't know how many apples I started with, you will know that you have shared between you a whole number of apples —or possibly no apples at all! I hope everything is clear so far? We wouldn't want to miss that million-dollar jackpot just for a little misunderstanding would we?"

The laborious going through the rules is really for the benefit of the viewers, of course, and the host is doing her best to keep it interesting.
"Now how are you going to win that jackpot, you ask! Well, tonight, that's going to be up to you, Alice. As decision maker, all you have to do is decide whether you think you and your two fellows have, between you, an even number or an odd number of apples. Is it an even number, like zero, 2 or 4, or an odd number, either one or three? And remember, you only have one of the three pieces! Ladies and gentlemen, that looks a like a tough job for our decision maker Alice! So, according to the rules of Guess my number, we allow her fellow contestants Bob and Charles to lend her a hand. Bob and Charles, you will each have a flag, and after looking at your piece of apple you can hold your flag up, or down. Alice can't see what you are doing, but I will then inform her of the position of each of your two flags, either up or down. With this information, and her own apple, she will then make her choice. That's all there is to it!"

The audience have been listening hard, and some begin to think through whether Bob and Charles will be able to tell Alice what she needs to know. Old hands have come along with their own schemes, they are itching to have a go at the game. The host with a twinkle in her eye addresses the obvious question to the contestants.

"Now, you three have I am sure got together beforehand to work out a scheme to win at Guess my number. So have many contestants before you, but none have managed to beat the system. Would you care to share with us the method you propose to use?"

The contestants demur. They are keeping their secret to themselves! The contestants on this game always do. These ones appear quite confident and keen to get down to business, but so have many poor triplets before them, who went away with a consolation prize, but not the big jackpot of 10 correct answers in a row.

"Alice, Bob, and Charles, would you please enter your isolation booths, and good luck!"

The three make their way into the booths, each carrying a case which looks quite heavy for its size. The audience can see them through the window, but they can't see each other. They open their cases on the desks before them, and get their flags ready.
The host fills the time gap with a bit of patter, and the musicians provide a suitably tension-building background. The first three pieces of apple are distributed, passed through a little drawer on each booth. We see Alice, Bob and Charles all adjusting something inside their cases, then Bob and Charles swiftly raise or lower their flags. The host reminds the audience that the contestants can take anything they like into the booths, but the booths are carefully isolated against every form of communication, including radio transmission or low-frequency sound.

"Alice, I see Bob's flag is up, and Charles' flag is down. Have you reached your decision?"
"Yes Debbie. I think it's an even number of apples."
"Alice, you said an even number, and I can reveal to you that I divided up two apples, which is an even number, so you are right!"

The audience breaths a sigh of relief. But the game moves immediately on to another round. The apples are divided and distributed, Bob and Charles indicate with their flags, and to mounting astonishment, Alice guesses right again and again. Eight times, nine times, then ten times, and a big fanfare sounds the winning of the jackpot. A excited round of applause greets the news, and the contestants are invited to step out and learn of their success.

Of course, this is going to happen by chance every 18 or so runs of the game (see later), and the designers of the program have based their calculations on this, knowing the program will be much more successful if someone wins the jackpot every now and then.

So the host asks Alice, Bob and Charles if they would like to play again, for a chance to either double or halve their winnings. Of course, with expected losses of 416,000 dollars, everyone knows the only sensible thing is to quit while they are on top, but these three seem super-confident. There is no dissuading them, and the game continues, and with a vengeance: the apples are divided into multiples of a quarter, not just a half! But surely something is up? Alice continues to get it right every time. Another ten times! The audience suspects the game has been rigged. The host senses the atmosphere is getting cool. Time for a commercial break!

Among the more alert viewers back at home, the scientific background of the three contestants did not go unnoticed. Nevertheless, the mathematically trained quickly worked out that once Alice looks at her own apple, she can reduce to eight the sixteen possibilities for Bob and Charles' apples, using the rule that the total is a whole number of apples. Four of these eight possibilities make an even number, four an odd. Bob and Charles can use their flags to further reduce the possibilities for Alice, so that half the time she knows the required result, and half the time she has to guess, giving her overall a ¾ chance of success (per round). However, that is as far as they can go. Whatever strategy they choose, and whatever prior information they shared before the game, they can't pin down the remaining possibilities for Alice any further. One of them needs to be allowed to send another bit! The program designers no doubt employed some mathematicians, maybe backed up by some information scientists, to confirm exactly this argument. (In the harder version using quarter apples, Alice needs two further bits (making four in all). This is a maximum; further subdividing the apples does not increase the information needed by Alice, though the proof of this is more involved.)



Alice (top), Bob (top right) and Charles (right) play Guess my number in their isolation booths. We, and the host, can see that three apples have been distributed among the contestants. Bob and Charles are making their binary statements to all the world, by raising and lowering flags. When this information is relayed to Alice, she reports her `guess' that the number of apples is odd. She is right, and she has been getting it right every time. This is most suspicious ... what are those devices that Alice, Bob and Charles have got with them? They seem to be innocent enough, just a group of atoms under laser control. Yet they must be useful somehow, since we can see Alice, Bob and Charles adjust and then examine their next unused atom, each time they receive the apples for a round of the game.

Telepathy or Science?

The astute viewers couldn't help noticing, though, an interesting combination of quantum physics and information science among this bunch of contestants. They called up their local quantum information physicist, who listened carefully to the whole setup, then with a smile explained:

"This is a simple but clear example of what we call entanglement-assisted communication. It is described in two papers by Cleve, Buhrman and van Dam [1,2] (and some of the questions were raised though not answered by Kremer [3]. Those contestants are well known characters to us, and what they are carrying in their three cases is a technological marvel, but something perfectly well allowed by the laws of physics: namely, three small quantum information processors, storing a collection of ten pre-entangled triplets of quantum bits.

Each triplet of qubits (of which Alice, Bob and Charles each have one qubit) is prepared before the show in the completely entangled state |000> + |111>. Alice, Bob and Charles receive, respectively, xa,xb,xc apples, where xi = 0,½,1 or 1½ (and i=a,b,c). They each go to the first so far unused qubit in their processor, and apply the rotation |0><0| + exp(xi π √-1)|1><1|. The game rules ensure that the resulting joint state is either |000> + |111> (when xa+xb+xc is even) or |000> - |111> (when xa+xb+xc is odd).

To enable Alice to know which of these two orthogonal states they jointly own, each person next applies the Hadamard rotation |0> –> (|0> + |1>), |1> –> (|0> - |1>), to their qubit. The resulting state is a three-qubit superposition of all the states of even parity, (|000> + |011> + |101> + |110>) or all the states of odd parity, (|111> + |100> + |010> + |001>). They each measure their qubit (in the basis |0>, |1>). Bob and Charles tell Alice the result of their measurement, by a simple agreed scheme such as flag up means zero, flag down means one, and Alice, having her own measurement result already to hand, immediately knows the parity of the three measurement results and so the answer to the original problem."

Entanglement-assisted communication complexity

The game of Guess my number is just an introduction to the concept of entanglement-enhanced communication. What is striking about the subject is that the communication is all classical: only classical bits and pieces are transmitted and received, so one would have thought that classical reasoning about the amount of information required to be sent would be valid. That it is not, is a particularly clear example of the fact that the science of information cannot be divorced from physics.

It is obvious that what is going on is closely connected to the famous Bell inequalities for non-local correlations between EPR pairs, but it is by now equally well known that Bell-EPR correlations cannot in themselves be used for communication. That is, the existence of entanglement at separated spatial locations does not reduce the number of communication bits that is necessary to convey a piece of information between the locations.

In entanglement-assisted communication, we accept this fact, and examine instead situations where the knowledge sought by Alice, or any of the parties, is a function of classical information which, like the entanglement, is initially distributed among the parties. Typically this knowledge will have the size of a single bit (in the case of Guess my number: even or odd?), which will be less than the required amount of communication.

Note that entanglement-assisted communication is very close to quantum communication, because classical bits plus entanglement can serve to transmit quantum bits by teleportation.

Guess my number involves just a one or two-bit difference between classical and correct reasoning, so it is natural to ask whether larger separations are possible. One way is to offer Alice, Bob and Charles m rounds of apples all at once, and ask Alice to give a single yes/no reply to the question: "does every round in the set contains an even number?" (the AND of all the replies she would have made in the normal game). Clearly, with entanglement assistance, she can use the method given above and require only m signals from Bob and m from Charles, making 2m in total, while it can be shown [4] that the classical limit is at least 3m communicated bits.

This can also be generalised, somewhat more powerfully, in another direction. Suppose we allow further parties. Rather than just three parties as in Guess my number, we consider k parties who wish to know whether their k lots of apple segments all add up to an even or an odd number, and the apples are more finely divided. To quantify the communication complexity CC(P) of a distributed problem P, we account one classical bit, broadcast from one party to every other party, to constitute one bit of communication. So for Guess my number (Gmn) we have for the quantum communication complexity CCq(Gmn)=2 and CCq(m-round Gmn)=2m, in combination with the classical lower bounds CCc(Gmn)≥ 3 and CCc(m-round Gmn)≥ 3m. The result for the k-party game, obtained by Buhrman et al. [4] is a proof that as the number of parties increases, the reduction in communication complexity becomes bigger: CCc(k-party Gmn) ≥ k log k - k versus CCq(k-party Gmn) = k-1, where the latter requires an entangled state of k qubits.

In the limit of many parties (large k) this last quantum complexity is an arbitrarily small fraction of what would be required classically. Far from being of no use at all for communication, entanglement seems now to be extremely useful!

Then again, given the severe difficulty of creating, maintaining and manipulating multipartite entanglement in practice, perhaps this reduction by a factor of CCc/CCq ~ log k is not so exciting. What we would really like is a much greater reduction, and one which does not involve many parties. It turns out this can be achieved. Buhrman, Cleve and Wigderson [5] showed a general way how to adapt Grover's searching algorithm to the communication scenario, allowing them to derive a result for the important Disjointness function: "do Alice and Bob have a free day available on the same date in their private n-page diaries?" For this problem—using prior entanglement—a reliable answer can be obtained with only CCq(Disjn) ≤ n½ log n, whereas every classical probabilistic protocol has complexity linear in n: CCc(Disjn) ~ n.

An even more striking separation is obtained by Raz [6] for a problem involving an m-dimensional vector space. Alice has a vector and a specification of two orthogonal sub-spaces, and Bob has a rotation matrix, all specified to O(log m) bits of precision. The total amount information they are supplied is therefore of order n ~ m2 log m. The Boolean function R to be evaluated is essentially: "which subspace does Bob's matrix rotate Alice's vector into?" It is not very difficult to show that this can be done very efficiently with teleportation: CCq(Rn) ≤ log n. The more challenging part of the proof was the lower bound CCc(Rn) ≥ n¼ / log n on the classical communication complexity, which is significantly higher than its quantum mechanical pendant.

The separation described by Raz is termed `exponential' as the classical communication complexity grows exponentially faster in the input size n than the quantum complexity CCq does. See Ambainis et al. [7] and Buhrman et al. [5] for other types of exponential separation. With the same reasoning the separation by Buhrman et al. is called `quadratic', but this does not make the Disjointness result less impressive. In fact, if we examine the ratio CCc(Disjn) / CCq(Disjn), we find that the `quadratic' gain is much larger than the `exponential' one.

The question, which distributed problems do allow a similar significant `quantum reduction' and which don't, is the focus for much current research. But the results that have already been obtained (like the above) were very unexpected and give us some profound insights into the properties of quantum mechanical systems and into the nature of information itself.

Consider the information accounting in these protocols. Since the classical argument says we require, say, n bits to be transmitted, but the entanglement-assisted protocol only needs ~n½ log n transmitted bits, presumably each transmitted bit is somehow doing the work of n½ / log n bits. The way to make sense of that non-sensical statement is to realise that what is transmitted is not, strictly speaking, an abstract classical bit, but rather a two-valued classical signal. In other words: a real physical entity or change is transmitted, and it is the fact that this entity is coupled to the entangled systems at either end of each transmission, which allows the surprising gain. By calling the entity classical, when in fact all entities are quantal, we just mean that the whole process is insensitive to whether the transmitted entity is in a mixed or a pure state, so it can be safely sent down traditional communication channels without corrupting the transmission. This is, of course, a tremendously easier form of transmission than one which has to preserve the full quantum state.

Experimental prospects

A laboratory demonstration of entanglement-enhanced communication would be, in our opinion, a landmark in quantum physics and quantum information science. It would represent the first time that classical information had passed from one place to another with less than the classically required amount of communication.

The Guess my number protocol is now close to being experimentally achievable. All that is required is a reliable Greenberger Horne and Zeilinger (GHZ) experiment [8,9,10], with the ability to apply simple single-qubit rotations. The GHZ experiments which have been reported to date [11,12,13], though impressive, don't satisfy the demands of the game. The NMR quantum information processing experiments allow some of the properties of the GHZ state |000> + |111> to be demonstrated [11,12], but there is no way to assign Alice, Bob and Charles to independent regions of spacetime in the NMR measurement technique. The quantum optics experiments of Bouwmeester et al. [13] do allow a realisation of the GHZ state with separated measurements on the three particles, but only a tiny fraction (10-10) of the ensemble of photon triplets is in the GHZ state, so Bob and Charles would do better to use a classical strategy rather than risk sending no information to Alice in almost every run. (We don't allow the contestants to post-select which runs they want to use, because that involves the communication of huge amounts of information to Alice, which is also worse than a purely classical strategy.)

It is our hope than the ion trap experiments actively pursued in several labs will soon reach a stage where this game could be played [14,15]. Admittedly, the walls between the booths of Alice, Bob and Charles would only be a few microns thick, and made of nothing, but we can trust these three not to talk to each other. Before each round of the game, they set up three trapped ions in the GHZ state, then they each separately receive their number from the host and adjust the duration of a laser pulse addressed to their ion, and each one reads out the final state of their ion by resonance fluorescence. Reported experimental achievements to date indicate that an overall reliability of one run of the experiment (determined by the fidelity of the prepared GHZ and precision of the rotations and measurements) could be expected to attain the 60% level fairly soon, so Alice's chance of guessing right could be of order 0.6 × 1 + 0.4 × ½ = 0.8, making a statistically significant departure from 75% odds after about a thousand rounds of the game, with no remaining "loopholes" connected with detector efficiencies etc.

As soon as such an experiment is done, the classical data would speak for themselves: the most likely explanation of the phenomenon, without quantum theory, would be that the contestants managed to cheat—since that is a much more likely hypothesis than the other one which suggests itself, namely that they used telepathy!

References

  1. R. Cleve and H. Buhrman. "Substituting quantum entanglement for communication", Physical Review A, 56:1201–1204, 1997.
  2. H. Buhrman, R. Cleve, and W. van Dam. "Quantum entanglement and communication complexity", On the quant-ph archive, report no. quant-ph/9705033.
  3. I. Kremer. "Quantum communication", Master's thesis, Computer Science Department, The Hebrew University of Jerusalem, 1995.
  4. H. Buhrman, W. van Dam, P. Høyer, and A. Tapp. "Muliparty quantum communication complexity", Physical Review A, 60:2737–2741, 1999. On the quant-ph archive, report no. quant-ph/9710054.
  5. H. Buhrman, R. Cleve, and A. Wigderson. "Quantum vs. classical communication and computation", In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), pages 63–68. ACM Press, 1998. On the quant-ph archive, report no. 9705033.
  6. R. Raz. "Exponential separation of quantum and classical communication complexity", In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC'99), pages 358–367, Atlanta, Georgia, May 1999. ACM Press.
  7. A. Ambainis, L.J. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson. "The quantum communication complexity of sampling", In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS'98), pages 342–351, Los Alamitos, California, November 1998. IEEE Computer Society.
  8. D.M. Greenberger, M.A. Horne, and A. Zeilinger. "Going beyond Bell's theorem", In M. Kafatos, editor, Bell's theorem, quantum theory and conceptions of the universe, pages 73–76. Kluwer Academic, Dordrecht, 1989.
  9. D.M. Greenberger, M.A. Horne, A. Shimony, and A. Zeilinger. "Bell's theorem without inequalities", American Journal of Physics, 58:1131–1143, 1990.
  10. N.D. Mermin. "What's wrong with these elements of reality?", Physics Today, pages 9–11, June 1990.
  11. R. Laflamme, E. Knill, W.H. Zurek, P. Catasti, and S.V.S. Mariappan. "NMR Greenberger-Horne-Zeilinger states", Philosophical Transactions of the Royal Society of London A, 356:1941–1948, 1998.
  12. R.J. Nelson, D.G. Cory, and S. Lloyd. "Experimental demonstration of Greenberger-Horne-Zeilinger correlations using nuclear magnetic resonance", On the quant-ph archive, report no. quant-ph/9905028.
  13. D. Bouwmeester, J-W. Pan, M. Daniell, H. Weinfurter, and A. Zeilinger. "Observation of three-photon Greenberger-Horne-Zeilinger entanglement", Physical Review Letters, 82:1345–1349, 1999.
  14. Q.A. Turchette, C.S. Wood, B.E. King, C.J. Myatt, D. Leibfried, W.M. Itano, C. Monroe, and D.J. Wineland. "Deterministic entanglement of two trapped ions", Physical Review Letters, 81(17):3631–3634, 1998.
  15. H.C. Nägerl, D. Leibfried, H. Rohde, G. Thalhammer, J. Eschner, F. Schmidt-Kaler, and R. Blatt. "Laser addressing of individual ions in a linear ion trap", Physical Review A, 60:145–148, 1999.

© 2000 American Institute of Physics. This article may be downloaded for personal use only. Any other use requires the permission of the authors and the American Institute of Physics.