Interference of the Nonfootball Kind

Interference can occur in both classical and quantum systems. In the classical world we are well acclimatized to thinking of water waves or electromagnetic waves or slinky waves interfering. In the quantum world interference plays a particularly central role, as we learn that we can at best calculate the amplitudes of events and constructive and destructive interference is essential in understanding the speedups of quantum algorithms. The difference between the classical world and the quantum world cannot just be summed up to “interference.” However it is also clear that interference is an essential difference between quantum computers and probabilistic classical computers. So understading interference seems to be an important task for thinking about quantum algorithms.
But when we think about interference in a classical world, my picture is almost always a picture with classical wave equations. Is there a simple computer sciencish model which shows interference which isn’t based on wave equations or some other “physical” wave? Here is one such example.
Consider the quintisential quantum interference experiment. Start a single qubit in the state [tex]$|0rangle$[/tex]. Now if we apply the Hadmard transform [tex]$frac{1}{sqrt{2}}left[ begin{array}{cc} 1 & 1 \ 1 & -1 end{array}right]$[/tex] to this qubit, we now have the state [tex]$frac{1}{sqrt{2}}(|0rangle+|1rangle)$[/tex]. Measurement of this state would then result in 50 percent probability of [tex]$|0rangle$[/tex] and 50 percent probability of [tex]$|1rangle$[/tex]. But suppose, that instead of performing this measurement, we apply another Hadamard. This will result in the state [tex]$|0rangle$[/tex] and measurement will now result in this state with certainty. So this is kind of strange. Suppose that you wanted to replace the above description of the above quantum evolution by a single classical bit which evolves stochastically. So you are looking for an operation which when applied to a bit in the state 0 turns this state into a 50/50 mixture of the states 0 and 1. But applying this operation twice results back in the state 0. You can quickly convince yourself that there is no 2 by 2 stochastic matrix with this property. We cannot replace a single qubit by a single bit if we are to assume that each quantum gate is mapped to a stochastic map on a bit. Of course, what we are seeing here is interference: in the quantum case, the two paths that the qubit takes, one throught [tex]$|0rangle$[/tex] and the other through [tex]$|1rangle$[/tex] interfere in such a way that we end up back in the [tex]$|0rangle$[/tex] state. Since probabilities are always positive, we cannot achieve a similar evolution using stocahstic evolutions on a single bit.
But wait! What if we wanted to model this qubit experiment by a classical experiment in which we replace the qubit by two classical bits. Now what can we do? Here is an idea. We need some randomness. So lets make one of the two classical bits a bit which is a 50/50 mixture of the two states 0 and 1. Now suppose that we use the second bit to represent the state we are measuring. I.e. in the above experiment when we start in the [tex]$|0rangle$[/tex] quantum state, this means starting in the second classical bit in the state 0. Now replace the Hadamard operation in the classical case with a classical operation which swaps the two bits. Certainly if we apply this classical gate once, and measure the second bit we end up in a 50/50 mixture and if we apply the swap twice, since swaping twice is identy, if we measure the second bit it will now be back to 0! So we’ve mimiced the above quantum interference experiment using two classical bits.
Well, coming from the quantum world, you might wonder ah but what about the following experiment. Suppose that you again start your quantum world in the state [tex]$|0rangle$[/tex], apply a Hadamard and then apply a Pauli [tex]$Z=left[begin{array}{cc} 1 & 0 \ 0 & -1 end{array} right]$[/tex] gate. Now, of course, if you make a measurement you again end up in a 50/50 mixture of the states [tex]$|0rangle$[/tex] and [tex]$|1rangle$[/tex]. However, if you forgoe this measurement and apply instead now a Hadmard, you will end up in the state [tex]$|1rangle$[/tex]. So by applying a gate [tex]$Z$[/tex] which does nothing to the probabilities had you measured the system, you’ve changed the state to [tex]$|1rangle[/tex] after the Hadmard. Very strange, but we know that this is nothing more than the effect of changing the phase of one of the states such that what was previously constructive interference becomes destructive interference (and vice versa). The obvious question is whether we can now mimic this using our two classical bits. Of course! We do this by, when we apply the [tex]$Z$[/tex] quantum gate, applying a bit flip to the first bit. Thus in the above experiment we replace Hadamard [tex]$Z$[/tex] Hadamard by swap, bit flip on the first bit, swap. This will, if we start the second bit in 0 produce the final result of 1, as desired, and if we were to measure the system after the first swap or first swap and bit flip on the first bit, a 50/50 mixture as desired.
Can this be extended even further? Yep. First notice that if we look at the group of reversible operations on 2 classical bits, this is nothing more than the permutation group of four objects (the states 00, 01, 10, and 11.) There are 24 elements to this group. Now the Pauli group on a single qubit, if you forget about a global phase, which for a single qubit can have no observable effect, has only four different elements (note that moding out this phase does not produce a group since [tex]$XZ=-ZX$[/tex], so what I’m describing is a set of elements which act in an observable fashion.) The Clifford group elements which are not Pauli group elements themselves acts as the automorphism group on the Pauli group. Indeed it acts, modulo again a global phase, to permute the three nontrivial elements of Pauli group. Thus it is, modulo again a global phase, nothing more than 3!=6 permutations. The total size of the Clifford group, when we mod out the effect of a global phase is 4 times 6 or 24. But that is the size of the permutation group of four objects. Indeed you can work out that because of this, you can mimic exactly the Clifford group gates using the two bit construction detailed above. Kind of cool, no?
So what we’ve got here is a classical model of the Clifford group gates, a set of gates which exhibit interference, but where we have replaced our qubit by two bits. This second replacement doesn’t look much like a classical wave, or at least not one I’m used to. Which is what I was looking for. So interference can be understood classically here. It is nothing more than the fact that we do not measure the full state of the classical system, which can lead to effects which look effectively like constructive and destructive interference. Since we don’t have complete information about the system by just knowing the state of the second bit, we can observe a classic example of quantum interference.
[Those of you who are experts may immediately notice Spekken’s toy model and the Gottesman-Knill theorem. But if you’re an expert why are you reading my silly meandering writings? Get back to work…Carlos!]