To set the scene, imagine you are trying to rob a bank. When you finally tunnel into the vault, you find yourself in a room containing eight giant gold bars. You have inside information that this bank has many vaults, and, in any given vault, either all eight of the bars are fake, or four are fake and four are genuine. The fake bars are very good, you cannot tell them apart from the genuine ones without extremely sophisticated laboratory-scale equipment, which of course you cannot just carry around.
The employees of the bank also cannot distinguish genuine bars from fake ones. Rather than give them a list of the genuine bar locations, which could be copied or stolen, the witty bank manager has installed in the corner of the vault one of our black and white ball computers, labelled Archimedes. Every bar in the room has a location uniquely identified by a combination of black and white circles, like this:
To check whether a particular bar is genuine or not, a bank employee drops three balls, with colors corresponding to that bar’s location, into Archimedes, and a fourth “target” ball which starts off black:
Archimedes works in such a way that if the gold bar at the location corresponding to the input balls is genuine, then a NOT is applied to the target ball. So, if the target comes out white then the employee knows that particular bar is genuine, if it remains black it is fake. The three location balls just emerge the same color they entered—similar to the control ball(s) of a CNOT or CSWAP or CCNOT box.
Imagine you know that this is how Archimedes works, but there is a snag. The time it takes for the balls to fall through Archimedes is very long—let’s say an hour. Perhaps this is an extra layer of safety for the bank to thwart people like you, or perhaps it is because inside Archimedes are a huge number of boxes executing some very complicated computation (otherwise possibly you would just smash Archimedes open to see if the information you need is easily accessible!). You definitely do not have time to check more than one bar before you had better get the heck out of the vault. To make matters worse, you are part of a gang, which has busted open many of the vaults. The gang leader has declared that anyone who steals only fake bars will be executed, as they will have wasted valuable space in the getaway truck.
It would seem the best thing you can do is pick one bar location at random and check if it is genuine or fake. If it is genuine, that’s great—you know you are in a vault with four genuine bars, and so stealing all eight bars is worthwhile. If it is fake, however, you will still be unsure which type of vault you have entered, it could be of either type. Without PETE boxes this really is the best you can do. Using Archimedes only once you can never be sure that you will be sure in an hour about which type of vault you are in.
Fortunately for you, and also for me (if you paid for it—though given your current escapade this seems unlikely), you have read this book and came prepared with some PETE boxes. This is going to let you determine for absolute sure which type of vault you are in, using Archimedes only once—that is, in just one hour.
The method to achieve this little piece of magic is as follows. You place four PETE boxes above all four entrance holes to Archimedes, and three PETE boxes at the bottom where the first three location balls emerge (there is no need to put a PETE box below the target hole). You drop into the first three PETE boxes a white ball, and into the fourth PETE box above the target hole, you drop a black ball.
One hour later, when the balls emerge, you check the color of the first three location balls. If all three balls are white then you are 100% guaranteed that you are in a vault containing only fake bars. If any (or all) of the first three balls are black, you are 100% guaranteed that you are in a vault containing four genuine bars and four fake bars.
To see that these last two assertions are true is a little bit of a messy calculation, I suspect it will be the messiest in the whole book, and so you should definitely skip it on a first reading if you’re not yet comfortable with these misty-state manipulations. Although the calculation is messy, it does not use any new rules beyond those I have already introduced you to.
Before you skip ahead, here is the intuitive description of how it works. The three PETE boxes above the location holes create a large misty state, in which all eight possible gold bar locations appear (all without a negative-sign label). The target ball enters Archimedes in a misty state of white and a negative-black. Archimedes performs a calculation in the mist that acts on all possible location configurations at the same time. This is one part of the magic—a regular computer cannot do anything like this. The last three PETE boxes at the bottom of the computer are there to cause interference—the adding and subtracting of some of the configurations in the mist because of the negative signs. The interference is carefully tailored in just the right way such that the only possible way the first three balls end up white (the same color they went in) is if all the bars are fake; if four of the bars are genuine then at least one of the three location balls will come out flipped to black.
You didn’t have to initially use three white balls at the location holes. If you begin with a different initial color configuration then you will find those three balls definitely emerge the same configuration they went in if all bars are fake, and definitely emerge in one of the many other color configurations if four of the bars are genuine.
The Archimedes calculation (consider this an aside)
We drop a white ball in the three PETE boxes above the location holes, and a black ball in the one above the target hole.
Case 1. All bars fake: If you are in a vault that only contains fake bars then Archimedes does nothing to the misty state; its effect is the same as if it was not there at all. After an hour the three location balls that exit Archimedes then each go through another PETE box. As we have seen, the combination of two PETE boxes in succession is the same as doing nothing—a white will emerge white, a black will emerge black. Since we input three white balls, we conclude that if you are in a vault containing only fake bars, you will definitely see the first three balls come out white.
Case 2. Four genuine bars: After entering the first line of four PETE boxes the balls are in the misty state:
[W,B][W,B][W,B][W,–B]
By the rules for combining mists, this is the same as a single large mist of 16 configurations.
The mist after 4 PETE boxes, but before Archimedes:
[WWWW, WWBW, WBWW, WBBW,
BWWW, BWBW, BBWW, BBBW,
–WWWB,–WWBB,–WBWB,–WBBB,
–BWWB,–BWBB,–BBWB,–BBBB]
This misty state now goes through Archimedes, which applies a NOT whenever the first three balls correspond to the locations of genuine bars. To illustrate, let me just pick four such locations at random. Let’s say the four genuine bars are at the locations labelled WWB, WBW, BWB and BBB.
The mist after Archimedes, before the final PETE boxes:
[WWWW, WWBB, WBWB, WBBW,
BWWW, BWBB, BBWW, BBBB,
–WWWB,–WWBW,–WBWW,–WBBB,
–BWWB,–BWBW,–BBWB,–BBBW]
which is the same as
[WWW,–WWB,–WBW,WBB,BWW,–BWB,BBW,–BBB][W,–B]
To make it easier to see what’s going on I used bold font to indicate the target ball colors that Archimedes flipped by applying a NOT. We see that the configurations corresponding to locations which contain a genuine bar now have a negative-sign label. Unfortunately, the negative signs cannot be observed, and so if we destroyed the mist by observing the balls now we would learn nothing useful. The final three PETE boxes are going to help cause interference so that these negative-sign labels have some useful effect.
It is a fortunate happenstance for this particular problem that the full mist of sixteen configurations can be split back apart into a mist of the location balls containing eight configurations, and a mist of the target ball containing just two. This will simplify the analysis, but in general this kind of thing does not happen in a misty computer (although for this particular problem it would happen no matter which four locations I had chosen
to contain genuine bars).
We now take this mist of the eight configurations for the location balls and send each ball through another PETE box. Can you see what a giant mist this is going to produce? For example, just the BBW configuration in the mist will break up into eight configurations like this:
BBW
evolves through 3 PETE boxes to
[W,–B][W,–B][W,B]
which is the same as
[WWW,WWB,–WBW,–WBB,–BWW,–BWB,BBW,BBB]
Thus the total mist of the location balls, after evolving through the second set of PETE boxes, potentially has 8x8=64 configurations in it—although many of these will disappear due to interference. Here then is then a calculation of the full set of final configurations in the mist. Don’t say I never do anything for you (and if you are reading this electronically you may want to resize the font to make this palatably line up):
[WWW,–WWB,–WBW,WBB,BWW,–BWB,BBW,–BBB]
evolves through 3 PETE boxes to:
[WWW, WWB, WBW, WBB, BWW, BWB, BBW, BBB,
–WWW, WWB,–WBW, WBB,–BWW, BWB,–BBW, BBB,
–WWW,–WWB, WBW, WBB,–BWW,–BWB, BBW, BBB,
WWW,–WWB,–WBW, WBB, BWW,–BWB,–BBW, BBB,
WWW, WWB, WBW, WBB,–BWW,–BWB,–BBW,–BBB,
–WWW, WWB,–WBW, WBB, BWW,–BWB, BBW,–BBB,
WWW, WWB,–WBW,–WBB,–BWW,–BWB, BBW, BBB,
–WWW, WWB, WBW,–WBB, BWW,–BWB,–BBW, BBB]
In the large output mist the first line originates from the WWW, the second from the –WWB and so on. If you look at the 64 configurations in the final mist, you see that there are exactly the same number of WWW configurations with a positive label as a negative-sign one. This means they all disappear by interference. Which in turn means when you observe the three location balls you will definitely not see all three of them white. At least one of them will be black.
Even if you raced through all that (as I would do on a first reading) and didn’t really follow it, that’s OK. The final claim is that the only way to see all three location balls emerge white is for you to be in a vault containing all fake bars. Conversely, if any or all of the balls come out black when you observe them, then you are in a vault containing four genuine bars.
If you have the fortitude, it would be a good idea to redo this calculation for yourself, picking a different four locations for the genuine bars than the ones I chose.
Before leaving this complicated aside aside, let me remark that it is just as annoying for me as it is for you that I have had to describe this whole Archimedes problem and its solution in terms of the individual boxes and what they do on specific ball configurations. It is much like if we wanted to play a computer game but first needed to specify how each individual transistor within the computer should be set. In practice, for regular computers we have programs built via programming languages which let us determine what the computer should do by giving it a set of instructions that we ourselves can understand quite naturally. Unfortunately, we have no good programming language for a misty computer. This is not because we don’t want one. So why haven’t we made one? Well, if you have ever written some computer code you know that a program is just a set of logical instructions for the computer to follow; instructions of the form “check IF this thing AND NOT that thing are the same, and if they are THEN do the following.” But that is all just a phrasing of regular logic, amenable to boxes obeying the computer rules—rules that we cannot use naturally to describe a misty computer!
Is there no limit to the magic?
I phrased the story above in terms of a vault containing eight bars. If there were double this number of bars, then the sixteen location labels would require four circles, and Archimedes would have four location holes. Yet, as long as you had the extra PETE boxes for the extra access into Archimedes you would still be able to determine the type of vault you were in by using Archimedes just once. This remains true whether the vault has 8 or 16 or 32 or 64 or… or 1024, or 2048, or …. or 65536 or… or any such “doubling number” of gold bars. In just one hour you can be absolutely sure of whether you were in a vault of all fake bars, or a vault where half of them are genuine.
Contrast this with the following worst case scenario. You enter a vault with 65,536 bars, and you have no PETE boxes. The gang leader now insists you do not leave the vault until you are absolutely sure which type of vault you are in. Perhaps you have entered a vault of fake bars. You start choosing locations at random and testing them and Archimedes tells you “fake, fake, fake,….” Are you definitely in a vault full of fake bars? No, because you may have entered a vault containing 50% genuine bars and 50% fake bars, but you are just really unlucky and keep testing the locations of fake bars. In that case you would also keep seeing “fake, fake, fake,…” as the answer. Until you have tested more than half of the 65,536 bar locations you could not be absolutely sure of which type of vault you were in. Do you really want to spend half of 65,536 hours (nearly four years) checking? Jail would be way more fun.
This last example brings home a crucial distinction between regular computers and those, like Archimedes, capable of utilizing misty states. Because it needs a much, much smaller number of steps, we see that even a slow ball-based computer using misty states will be better than using the fastest supercomputers around, once the number of gold bars to check gets high enough. The valuable resource that these misty computers can save us, is “number of computational steps”—which in many cases can lead to a staggeringly large savings in the time it takes to get an answer. It is a common misconception that the misty computers will be smaller and operate with a higher speed than regular computers, but in fact we do not expect that at all. The reason we want these misty computers is because, even if their speed of operation is much slower, it is their fundamental logic which is different, and this gives them an unconquerable advantage for certain problems.
Another point to emphasize about the misty computers is that they are much more than just regular computers with some extra fundamental randomness thrown in. In a limited fashion, the Archimedes example shows that: random choices without PETE boxes is not equivalent to PETE boxes. Access to fundamental randomness does make regular computers somewhat more powerful, but they still cannot come remotely close to the power of the misty computers.
Misty computers will be very lucrative, but not because they will help us rob banks. There is a massive worldwide effort to build them because they will vastly outperform our regular computers for certain problems that are major obstacles to technological progress. Examples include calculating accurately the chemical reactions necessary to design important new medicines, or solving the equations that will let us design highly-specialized materials to harvest solar energy better, or speeding up machine-learning so regular computers become more intelligent than ourselves sooner, or … well the list is massive, and I have heard the figure thrown around that over twenty percent of all current supercomputer time is spent solving problems that a misty computer will be able to solve unbelievably more easily and quickly.
However, the really exciting thing is not that misty computers will let us do things we already do a bit faster—rather, it is that they will let us tackle problems that at present we don’t even bother trying on our regular computers since we know they are much too hard.
Yet, while the misty computers will solve some problems much more easily, the set of all “in principle solvable” problems is unaffected by the new possibilities of misty logic. This is another point that is often misunderstood about what the misty computers will and will not be able to do. They will not be able to “compute the uncomputable.” The set of problems they can solve in principle is no bigger than the set of problems we can solve on our current regular computers. How do I know that? Well, above I have given you the full set of rules for how to compute what happens to the misty state as it evolves through the boxes. So you could just sit down with a piece of paper, and draw out the misty states, and work it
out for yourself.
How much paper would you need? If you begin with a problem using seventy balls falling through seventy PETE boxes (and we expect to build much larger misty computers than this) then the number of balls in the combined misty states will be the seventieth term in the doubling sequence: 2, 4, 8, 16, 32, …. Assuming you can draw at most about a thousand balls on a page, you would need so much paper you would be able to completely cover the earth. Use just one more PETE box and your paper stack will be large enough to cover two earths. (And I think I’m sick of drawing black and white balls….)
More sensibly, you would write a program for a regular computer to do the calculation for you, and computers don’t need paper. They can store huge amounts of data in the tiny chunks of matter that make up their memory. As impressive as this is, in the end it only helps a little—even if we turned every atom in the earth into a bit of computer memory, the computer would only be able to “write down” the misty state produced by fewer than 150 PETE boxes.
While there are some clever programming tricks that will optimize things a bit, and reduce the time and memory requirements from these naïve estimates, the upshot is that even using these tricks you would need an absolutely giant regular computer (as big as the universe for even reasonably sized problems) and very, very long amounts of time (more than the age of the universe) to work out what a small misty state computer will be able to somehow do on its own, inside itself, quickly and easily. In theory you would be able to do any computation a misty computer does, but in practice you cannot. Unless, of course, you happen to be The Spectre (who is immortal) during Crisis on Infinite Earths (so you have lots of space)—and if you are then it seems likely you have many problems of inconsistent logic on your mind; best to work on those.
A final common misconception about misty computers is that this huge growth in the number of configurations is “obviously” the source of the extra power of a misty computation. But some caution is required. If you went on a hike with seventy people, each of whom had a “two options” lunch which you threw in a backpack, the total number of potential lunch configurations in the backpack is just as large as the misty state after dropping balls through seventy PETE boxes. Just as for a misty state, when you look inside the backpack, you will only see one of the configurations. Within the mist, however, interference (cancellation) is possible between different configurations that are somehow all “in there” together, and this is not something that can be mimicked by your lunch.
Q is for Quantum Page 4