Q is for Quantum
Page 5
Well, why can’t we buy one of these magical, misty computers yet?
We can build many versions of the PETE box already, and our current computers already contain devices (transistors) implementing the computer rules like NOT and CNOT and CSWAP and so on. So why can’t we just join them all up?
The reason we cannot just grab some components at Fry’s electronics and hack up a misty computer is because the computer-rules devices we have built (so far) are all really nosy: they just can’t help themselves looking at the color of the ball exiting the PETE box. We try and try to get them to not do it, but they are like a curious cat that desperately needs to see the color, and their observations keep on burning away the valuable mist. Nosiness leads to noisiness.
We are making a lot of progress, however, and I am optimistic we will create large scale, useful misty states very soon.
Many, many words ago I claimed the existence of misty states would profoundly change your whole view of the physical world. But with respect to computers, this now seems to be a bit of hyperbole, as if I was just writing a standard pop-sci book. I mean, sure these new computers will impact your life, they may even help extend it hundreds of years, but the progression of our lives is already marked by the continual increase in computing power we have all witnessed and come to expect. In terms of challenging deep-seated conceptions about how the universe works we are going to have to delve into a more detailed look at the illogical behavior of the misty states. This will show they are completely incompatible with “sensible and obvious” expectations we have about the nature of physical reality.
Summary of Part I
Two distinct physical properties (e.g., black and white color) of a system (e.g., balls) can be manipulated by extremely simple rules (e.g., NOT, CCNOT, etc.) that nonetheless can produce the profound complexity of computation, and moreover map directly to the basic logic of our thought processes.
There exist some experiments that exhibit fundamental randomness. The origin of the randomness is subtler than our simple ignorance about what’s going on inside the experiment.
Two distinct physical states can sometimes be in a misty state or “superposition,” which is jargon for a new state of physical/logical being.
Our observations of things cannot be completely passive.
These misty states are definitely math and possibly physics, but their status is contentious.
The misty states grow rapidly as you bring in more systems. But the same can be said about your lunch prospects.
Regardless of what they are, a suitably built computer will be able to utilize misty states to do certain computations in vastly fewer steps than regular computers would require. This means we don’t need to care about the speed at which they execute each step: they will win because they use a different logic.
The excitement about misty computers is not because they will let us solve problems we currently tackle a bit faster, it is because they open up vast new territories of previously unthinkable problems to take on.
Misty computers do not compute the uncomputable—the set of in-principle soluble problems is the same. They just make previously highly infeasible problems tractable.
The boxes we have encountered are:
In the diagram, only cases where the output is different from the input are shown—in all other cases the boxes do not change the input.
Part II: Q-ENTANGLEMENT
A tale of testing telepathy
Many people—let’s call them psychics—claim to have telepathic ability; that is, an ability for instantaneous communication between two separated minds, via means unknown. Whenever asked to evaluate claims of powers that go beyond the laws of physics as we currently understand them, the prominent magician James Randi (who in the past has offered a $1 million dollar prize for any demonstration of such) will insist the claimants first make precise exactly what it is they say they can do. He has found there is no point in designing the test and then challenging the psychics to meet its standards, because the psychics can wriggle out by saying their powers are not compatible with meeting the specific challenge the skeptical tester would like. Rather, it is best to test exactly what it is the psychics claim to be able to do, making sure only to install obvious and agreed-upon safeguards against cheating.
Imagine (as I hope is actually true) that you are skeptical of generic claims of psychic abilities, but you are open to being convinced otherwise by a suitably rigorous demonstration. You are working for Randi when two psychics, Alice and Bob, contact you (by regular means), claiming to be telepathic. You now enter a negotiation as to how they will demonstrate their ability. Unfortunately, and this is quite typical, they do not claim to be able to do something obvious and readily testable, like transmit a simple message. Their powers, they say, are subtler.
Eventually the protocol they propose involves them each being separated in well-shielded rooms, to prevent communication by any regular means. Within each room a tester will flip a coin and tell the psychic in that room the outcome, “heads” or “tails.” The psychics will each then have to say to their tester one of two very magical words—namely, either “black” or “white.”
Proposed test of telepathy:
The psychics win the $1 million if both coin flips come up tails and they both say “black.”
There are two rules:
Rule 1: If both coins are heads, the psychics must not both say “black.”
Rule 2: If one coin is heads and the other is tails, the psychic told “heads” must not say “white” when the psychic told “tails” says “black.”
If either of the rules are broken, the psychics are severely punished.
There is quite a lot to think about in terms of understanding this proposal.
Firstly, the “game” will need to be played multiple times. If it is only played once and something other than “tails-tails” comes up, then the psychics have no opportunity to win at all.
Secondly, the proposal is that the psychics are “severely punished” if they break either of the two rules. What is something so bad nobody would risk it, even for a million dollars? Think of the worst thing that could happen to someone (head chopped off, pet cat skinned alive until it’s half-dead, ugly selfie posted on Instagram—whatever). Are you confident the punishment is so bad they will not risk it for a million dollars? Less drastic would be to impose a proviso: if any of their answers ever break one of the two rules, the whole game is off, and they definitely lose. If it so happens that every time the game is played and they try to win by non-telepathic means, they also necessarily run some risk of breaking one of the rules, then by playing many times you can make it very, very unlikely (much less than a one-in-a-million chance) that they could win.
Thirdly, if the psychics are isolated and cannot communicate then the testers also are unable to communicate. So, they will need to play a bunch of times, and then the testers get together and compare the coin flips and psychics’ answers in order to check if the psychics ever won (and, if so, did they also always satisfy the two rules?).
But all of this is jumping the gun a little. Why would they need to be psychic to win at all?
I would encourage you to stop now and think about possible strategies for Alice and Bob. To make it easier, here is a summary of the answers that are or are not allowed under the two rules:
It seems like there should be no problem for them to win the game. But there is. You should try for yourself to prove that they cannot win the game while simultaneously always obeying the two rules (unless, of course, they are actually telepathic). One way to see the issues is to play out what you imagine the conversation between the two psychics will be when they get together to work out what they are going to do.
AN IMAGINED CONVERSATION BETWEEN THE PSYCHICS
ALICE: Awesome, those suckers accepted our proposed test. Obviously we aren’t actually psychic, but I’m sure we can win this game.
BOB: Let’s work out a strategy. Actually, we both
know I’m not the sharpest pencil in the box, Alice—I better let you work it out.
ALICE: Fine. By Rule 1, when we both get heads, we cannot both answer “black.” So how about I will answer “white” when I get heads, and you can answer “black” when you get heads.
BOB: Woah, slow down there, Alice. I think I better write this down, it sounds complicated already.
Bob hunts for pencil and paper, finally finds one and draws a diagram.
Bob shows it to Alice.
BOB: (Proudly) See, I made a table of what we should do. I drew a picture of each coin and its two possible outcomes H or T that the tester could tell us, and I’m putting B to mean black and W to mean white next to each outcome for what color we should answer.
ALICE: Yes Bob, it’s very pretty. Let’s keep going. Since we only win by both answering “black” when we both get tails, when we see tails we should always answer “black.”
Bob duly makes a note of this as well.
ALICE: So there you go, we have a solution. Now, let’s think about what to spend all that money on….
Bob is looking a bit puzzled, scratching his head. Alice has started to daydream.
BOB: Uh, Alice, I think there is a liiiiiittle problem. By Rule 2 if I get tails and you get heads I am not allowed to answer “black” when you answer “white.” See, I put a line through the combination that breaks the rule:
Alice slowly refocuses her attention.
BOB: And because you won’t know whether the coin in my room came up heads or tails, there is a risk we will break this rule.
ALICE: (Impatiently) Yes, Bob, I see the point. Let me think for a second.
Both Alice and Bob enter deep concentration.
BOB: (Eagerly) Oh, wait, I have an idea—we can make sure to not break Rule 2 by using almost the same idea as you had Alice, except that I will say white when I get told tails. See, this is what I propose we answer, it clearly satisfies both Rule 1 and Rule 2:
ALICE: (A little sarcastically) Sure Bob, that’s great. We will obey both the rules. But don’t you see a problem with that?
BOB: Uh, no, looks fine to me.
ALICE: Think, Bob, think. If we give those answers, then we will never win. When we both get told “tails,” you will be answering “white”—and we only win if we both say “black” when we both get told “tails.”
BOB: Oh, yeah, um sorry Alice.
ALICE: (Muttering to herself) For tails we both answer “black,” but by Rule 1 at least one of us needs to answer “white” for heads, and Rule 2 rules out the other person saying “black” for tails, which rules out winning….
BOB: I can’t think through logical stuff like you, Alice. So I’m going to draw out every possible way we can choose to answer, and then put a line through every combination that violates one of the rules.
Bob starts drawing and after a few minutes produces his diagram:
BOB: Nooooow I see the problem. There are some answers we can give that don’t break any of the rules, but the winning combinations are the ones in the bottom row for which we both answer black when both coin flips are tails. All of those have at least one line through them because they disobey one or both of the rules.
ALICE: Damn, what have we gotten ourselves into? If only I were actually telepathic, then I would just telepathize the coin outcome my tester gets to you, and even you would be able to make sure we win. But I’m not telepathic, and I’m sure you’re not, Bob, since it presumably requires having more than three brain cells.
BOB: Hey, no need to get nasty now. Even a three-brain-celled person can lead a nuclear weaponized country, you know.
Scene ends with two grouchy “psychics” not talking to each other, at least not verbally.
Let me harp on a little longer about the psychics’ options if they are not telepathic. Perhaps it is a mistake for them to pre-determine their strategy? Maybe they should only decide on a “black” versus “white” answer once they know the coin flip they are told by their tester? For example, they could use a coin flip of their own and base their color choice partially on the outcome. Can you see why such a “non-deterministic” (i.e., not pre-determined) strategy won’t help? It makes the other psychic even less sure what their partner is answering, and that cannot help them win. Even if their strategy is chosen randomly in this way, it will still amount to one of the sixteen diagrams Bob drew above, and so will either not have any chance of winning, or will run some risk of breaking a rule. Once again we see we need to test them multiple times to be sure they didn’t just get lucky.
If the psychics are not telepathic and rather employ some combination of the strategies in the diagram Bob drew above, then whenever they cheat (by deciding their colors based on the last row in the diagram, which are all the possibilities where they both answer black for tails) they run at least a one-in-four chance of breaking one of the rules. You can see this in the diagram: for each of the enumerated potential cheating tactics in the last row, at least one of the four possible coin combinations makes them answer colors forbidden by the rules. They also have a one-in-four chance of winning, since this is how often both coin flips would come up tails. Finally, they have a one-in-two chance that nothing happens: they don’t win (because the coin flips did not come up both tails), but at least they don’t break a rule and get caught.
You and Randi don’t really care what cheating strategy they would optimally employ—you just want to pick a number of times they must win, such that you and he can be confident that they would have less than (say) a one-in-a-million chance of winning unless they really are telepathic. Calculating odds like this is a bit tricky. They will need to cheat many times, and each time that they cheat and don’t win they need to get away with it. Intuitively their likelihood of doing so decreases rapidly, much as the chances of you playing roulette and it landing on red over and over and over again decreases rapidly the more times you play. Fortunately, you have your friend in the bank, the same one who gave you inside information when you were robbing it in Part I. Unlike most people who work in banking, your friend understands this kind of thing. He tells you that if they win twenty times using any of the strategies from the last row in the table above, the probability they get away with cheating is less than one in a million. (If you want to see the calculation go to the webpage for this book).
You explain to the psychics that you want to play the game multiple times, both to give them a chance to win and to safeguard against cheating, and you require at least twenty wins. They come back and say that if the game is played four thousand times—so that by the law of averages the coin flips will both come up tails about a thousand times—they will definitely win more than twenty times, and will never break a rule in any of the four thousand games.
Once you understand all this you and Randi agree with the psychics that this is a fair test. You even get a bit carried away, and offer to also throw in a couple of genuine gold bars you came across recently.
Playing the games
The day of the test comes, and there is much fanfare as the world’s media descends. Alice and Bob show up. Hang on, what is going on? They are both carrying a large number of boxes that they each want to take into their isolated room. They say that there is nothing in the rules preventing them having “telepathic aids.”
Now, given more time and without the glare of the media, you would hopefully realize that you should contact me or some other scientist just to be sure you haven’t missed something. But here is the thing: You and Randi are fully convinced that you have managed to completely isolate the two rooms that each psychic/tester pair will be closed into. What could it really matter if Alice and Bob bring some stuff in with them? Even if they bring in powerful supercomputers to help them do complicated calculations that might somehow help determine the color they should announce to each coin flip, you are sure from the arguments presented above that they cannot simultaneously obey the rules and ensure a win, and so they run a risk of being caught cheating. Of
course, you do understand from your bank escapade that a misty computer can do some calculations faster than any supercomputer, but all the computing power in the world isn’t going to change the fact they ultimately need to answer “black” or “white” according to some simple constraints that are easily shown to not be consistently achievable. So you decide to let the test go ahead.
Since you and Randi are the ones with serious money at stake, you have decided, as an extra hedge against possible cheating (“Hey skeptical tester friend, want half a million bucks and a gold bar?”), that you each will act as a tester.
When you get into the room with Alice you find that she has brought in a huge pile of boxes, each labeled STORAGE and numbered from 1 to 4,000. You get a slight sinking feeling when you see that she also brings in a box labelled “PETE.”
The test begins. You flip your coin and it comes up “tails,” which you call out to Alice. Alice then takes the small box labeled STORAGE 1, holds it above the PETE box, pulls some kind of lever and almost immediately a black ball falls out from it. “My first answer is black,” Alice tells you. You write it on the piece of paper you brought to record the coin flips and corresponding black/white answers: