Seeing complicated larger-scale patterns arise from very simple rules for smaller patterns is neat, but perhaps not a shock to anyone who has dived a coral reef or watched bees work or crystals grow. I suggest to you, however, that a moment’s reflection on the essentially unbounded potential of our computerized experiences puts into perspective the much more limited scope of examples of this kind from nature. Moreover, there is a really rather beautiful fact about these small-scale computer rules: as intimated above, they capture primal concepts of logical thinking.
Logic from the motion of matter
If we replace black and white states of a physical material with our ethereal mental notions of “true” and “false,” then these simple computer rules capture all the pertinent rules of logical reasoning. The simplest example is that if something is NOT-true it is false, and we have already encountered the NOT box which negates “true” (a black ball) by changing it to “false” (a white ball) and vice versa.
For the next simplest example of logical reasoning, we need the CCNOT box, which we first saw constructed by stacking a CNOT, a CSWAP and another CNOT:
(In the Summary of Part I is a diagram recalling how every box works in case you find it difficult to remember them).
The CCNOT box’s logical specialty is AND: If two statements are true, we can say “statement 1 AND statement 2 is true” but not otherwise. The CCNOT box computes the AND of the first two balls as follows: if we input a white ball into the third hole, then it emerges black (i.e. true) if and only if both ball 1 and ball 2 are black (i.e. true). This matches/computes the logical notion of “and” perfectly.
Another simple logical construction is that if one or the other or both of two statements are true we can say “statement 1 OR statement 2 is true.” The CCNOT— with a black ball input into the third hole, and NOT boxes placed above the first and second holes—will also compute the OR of balls 1 and 2 onto the third ball. That is, the third ball will emerge black if either, or both, of the first two balls are black.
Slightly more complicated constructions give us ways of computing crucial logical elements like “IF statement 1 is true THEN statement 2 is true.” Almost everything we ever try to explain or discuss or argue about is built from applying these sorts of basic logical constructions to facts/assertions/propositions we take to be fundamentally (or self-evidently) true or false.
We have very briefly seen then that both our (dumb?) computers and our (intelligent?) logical thought processes share a common set of fundamental rules, rules that can be captured by simple motions of matter such as balls passing through the computer-rules boxes. The power of computers that can make use of misty states by incorporating the PETE box is precisely that they go beyond our standard logic. They bring a radically new element into the computers—a radically new logical alternative that is not a natural part of our reasoning. As exciting as this is, it makes it very tricky for us humans to comprehend, encumbered as we are to think “computer-logically.”
Mist through computer-rules boxes
Once we allow the strange logic of the PETE boxes—or equivalently the strange possibility of creating misty states—into our computers, then our whole description of a computation changes dramatically. Computers operating without PETE boxes I will refer to as “regular.”
Without any PETE boxes, a regular computer made from balls is always in a single physical configuration of black and white balls. This configuration evolves to a single new configuration as the balls drop through boxes obeying the computer rules of logic. Given the input configuration of ball colors we can readily deduce the output configuration by applying the computer rules.
So far the only misty states we have considered were comprised of a single ball, but it is possible to create multi-ball misty states. The first step to understanding misty computation is to learn what happens when we use the computer-rules boxes with multiple balls in a misty state. To determine how they transform, we work out independently how each configuration within the mist transforms, and add the output into a combined final mist. Here are some examples of how misty states of two or three balls are transformed when they pass through a few of the computer-rules boxes:
There are several things to note in these three examples. In the first, there are two configurations of two balls in the mist. I have indicated with dotted arrows that it is ball 1 of each of the configurations that drops through the NOT box. Ball 2 from each configuration drops through the “pipe” on the right (not indicated with arrows). That is, you take each of the two input configurations WB and BB (where “B” and “W” mean black and white) in the mist and act the NOT on the first ball to find the output misty state. I drew in the pipe, which does nothing to the second ball, to re-emphasize that no ball should be observed in transit or else the mistiness will be lost.
Now look at the misty state that is entering the CNOT box in the second example. In this mist there is also a BB and a WB configuration, but listed in different order to the first example. As mentioned previously, the ordering of the configurations is irrelevant, so this input misty state is exactly the same as the one in the first example. In this second example I have drawn arrows to indicate the path of both of the two balls within the second configuration; similar paths are taken by the two balls in the first configuration.
While the ordering of configurations (separated by commas) within the mist is up to you to choose, it is not the case that the ordering of the balls within each configuration is irrelevant. A WB configuration means the first ball is white, the second black, and this is not the same as the configuration BW. When we have multiple balls in a mist we always know which ball is which—this is the first (e.g. plastic) ball, this is the second (e.g. metal) one, and so on.
The third example shows three balls dropping through a CSWAP box. The CSWAP only affects the ball colors if the first (control) ball is black; if it is, then it swaps the colors of the second and third (target) balls. Remember it swaps the colors, not the balls themselves. In this example, this only changes the second of the four configurations within the original mist.
We see from these examples that passing a mist through any of the boxes obeying the computer rules does not change the total number of different configurations within a mist—it changes only the colors within the configurations that make up the input mist. Things are very different once the PETE box enters the picture.
Mist through both computer-rules and PETE boxes
Recall that every time a ball goes through a PETE box you split it into some mist. If a ball is already within a mist when you do this, then it splits up within the mist into more mist, potentially interfering (i.e., the negative configurations cancel with positive configurations). Here is an example to give you a picture to keep in mind. Don’t worry at this stage if it’s all a bit foggy and you can’t follow the evolution through exactly; although if you can, that’s great—you then can understand the rest of this book no problem:
Within the text I will use square brackets to denote “edges of the mist,” so the input mist in this example can be written [WW,WB,BW,–BB]. In this example, the first ball goes through the PETE box and splits into a mist of two configurations, [W,B] or [W,–B], while the second ball, which goes through a NOT box, does not split. Note that we then “expand out” the possible configurations. So [W,B]B becomes WB,BB for example. This procedure is explained in more detail in the next section.
In this particular example, if we observed the two balls prior to them dropping through the PETE and NOT boxes we would find any of the possible combinations of black and white with equal likelihood. After they come out the bottom we will only ever observe the balls to have opposite colors—the configurations with BB and WW were destroyed by interference. In the output mist, the configurations WB and BW are each repeated twice. This would be physically indistinguishable from a mist containing BW and WB each just once, since in both cases you have equal likelihood of seeing either color configuration, but I leave in the
repetitions for pedagogical reasons to do with calculations we make later in the book.
Can you work out for yourself what the output mist would be if the input mist was [WW,WB,BW,BB]—that is, if there was no negative-sign label on the BB configuration of the initial misty state? You should find that one of the balls will always be a single color, while the other might be found either black or white. Note that it is only configurations of ball colors that can be destroyed by interference, not the balls themselves—if you ever find yourself with a mist containing no balls at all, or more balls than entered the boxes, then something has gone wrong in your calculation.
At any time in the middle of a misty computation, we may choose to look at the color of a single ball. In Part II, I will give the precise rule for how the misty state changes when we do this, as it is generally considered very strange and disconcerting. For the moment, however, imagine a computer which operates via a mist cascading down through many stacked boxes until, at the very bottom, we observe the color of all the balls. The outcome will be a random one of the configurations which remains in the mist (i.e., was not destroyed by interference). If all configurations remaining are repeated the same number of times (as in the example just given), then every configuration which remains in the mist is equally likely. I will explain the case of misty states where some configurations are repeated more often than others when we need it much later. At this stage the most important takeaway message is that, just as for a single ball, repeated configurations within multi-ball mists will interfere if one of the copies has a negative-sign label and the other one does not.
Collisions within a fog
The last important ingredient we need to understand about the misty states before we can see a concrete example of a computer enhanced via PETE boxes, is this: What happens when we bring together, or combine together, sets of balls—each of which are already in a misty state? How do we describe the larger mist that encompasses them all? Here are some examples from which you can try and work out the rule:
Can you see the pattern? The rule is that when you combine two separate mists you match up every configuration of balls in the first mist with every configuration from the second one and simply append those from the second mist onto those of the first, making sure to keep track which ball is which.
As the ordering of balls within a configuration matters, we must keep the mists all in the right order. In the third example, you can start by combining the first two mists, then combine the resultant mist with the third one, to yield the eight configurations you can see. Writing this third example out in detail:
[W,B][WW,BB][W,–B]
is the same as
[WWW,WBB,BWW,BBB][W,–B]
which is the same as
[WWWW,–WWWB,WBBW,–WBBB,BWWW,–BWWB,BBBW,–BBBB]
As you might imagine, the number of configurations can grow rapidly—every time you bring in a new mist containing two configurations, you double the total number in the combined mist. In the figure, the combined mists contain two, four, and eight configurations; continuing to bring in new mists each containing two configurations would keep on doubling the total: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,… and these numbers grow very fast.
Interestingly, we see in the above figure that a negative-sign label applies to a configuration and not to a particular ball. That is, if you are appending one configuration to another and one of the configurations has a negative-sign label, you can put the negative-sign label on the whole joint configuration. For example, combining WW with –BB yields –WWBB. You do not need to keep track of which particular ball, or even which of the two configurations, the negative-sign originated from—it is a holistic property of the combined configuration. This is similar to when we do math of the form:
2 x (–3) = –(2 x 3).
If you are appending two configurations that both have a negative-sign label, then, as we have seen already, the two negative-sign labels become a positive (i.e., no label). For example, combining –WW with –BB yields WWBB.
Although it sounds like combining mists is a physical process (grabbing the outputs of some boxes and smashing them together) in fact it is not. It is more like a bookkeeping device. It is completely optional if the balls you are combining are never going to both go through a box like the CNOT, for which they have to interact somehow. That is, if we have two balls in their own mists at widely separate locations we could keep them in their own mists, or we can choose to write down the combined mist. It is only strictly necessary to use the combined mist when the two balls are brought together and something happens to them where the color of one is affected by the color of the other.
Good grammar, is essential
A word of warning: a comma makes a big difference. It distinguishes a superposition (which lists different configurations of the same ball or balls), from a combination of mists of completely different balls. Here is a subtle example—compare these two very different scenarios, for which the output mists differ only by a single comma:
On the left we have one ball, which is in a superposition of [W,B] and [W,–B], and by interference it ends up in [W,W]. On the right we have two balls—the first ball is in [W,B], while the second ball is in [W,–B]; combining these misty states yields the two-ball mist depicted.
Lunchtime lesson
Should we find the rule about combining mists strange? In fact, it is pretty natural. Imagine you are going on a hike with two friends, and your mother packs you a lunchbox which contains either an orange or an apple. You don’t know which; you only know your lunch options are “O” or “A.” You now meet up with your first friend, whose mother clearly loves him more: she packed him lunch of either a packet of chips and a burger, or some jerky and a slice of pizza. Your friend doesn’t know whether he has “CB” or “JP.” (Yes, I know which lunch you want…concentrate please).
You decide to only carry one backpack between you, and so you put the contents of both lunchboxes into it (without looking). The possible contents of the backpack are now OCB,OJP,ACB,AJP.
Finally, you meet up with the second friend. Her mother packed her a lunch which consists of either lettuce “L” or a tomato “T.” And you thought you had it bad. After combining her lunch (still without looking) into the backpack, the possible contents you would all agree are now OCBL,OCBT,OJPL,OJPT,ACBL,ACBT,AJPL,AJPT. Note that, analogous to misty states of balls, the order I have listed the possible lunch configurations is irrelevant to the description of the backpack contents. But, sadly for you, the order of each possible foodstuff within any configuration is important—the first letter always refers to your particular lunch, for example.
Compare the eight possible backpack contents to the final example in the previous figure. The configurations match up if you do the following: identify the physically distinct alternatives of the first ball (white/black) with the physically distinct alternatives of your fruit (orange/apple). Similarly, identify white/black of the second ball with chips/jerky, of the third ball with burger/pizza, and of the fourth ball with lettuce/tomato:
I described combining the lunches as a physical process—tipping the contents into a backpack without looking. But what if I had just said, “You each keep your own lunch; just list all the possible lunch combinations”? The list you would make would still be OCBL,OCBT,OJPL,OJPT,ACBL,ACBT,AJPL,AJPT. No “interaction between the foodstuffs” is required for the combined list to be the correct description of the full set of possible lunches. If your lunches were never to interact then it would be your choice whether to use the combined list or just list them separately. Imagine, however, tomatoes had the magical ability to convert an apple into an orange and vice versa. It then makes a difference whether the lunches get mixed together or not, because for something to happen (the killer tomato to attack your fruit) the foods would need to be in the same location (the backpack). The description of the (potential) ensuing mess—depending as it does on whether your friend actually has been packed a tomato—would first
necessitate listing the combined contents. We could then describe the action of the (possible) tomato on the fruit much like a CNOT gate acting on the lunch list. This is all very similar to the case for the balls, where the combining of two misty states is not a physical process per se; it is, however a necessary description once the balls interact via one of the multi-ball boxes and we change a color of one ball in the mist dependent on the color of another.
As yummy as this whole lunchbox analogy is, there are limitations—there is no such thing as a “negative-sign-labelled tomato,” for example. Moreover, we already proved (by stacking two PETE boxes) that there is no way to think of the misty state of a single ball as “the ball really is either black or white”; whereas the contents of your lunch box can be understood as “the fruit really is either an orange or an apple.” But in terms of understanding how the configurations within separate misty states combine to make a larger misty state, it works perfectly.
Misty computation can be very lucrative
We are now in a position where I can finally give you a concrete example of how the addition of PETE boxes to a computation can be a huge advantage. This example is a little contrived, but it exhibits all the core principles that underpin the computational power of the PETE boxes. (We will incorporate misty possibilities into computers of the future to do much more interesting things than this.)
Q is for Quantum Page 3