A Quantum Two-Finger Exercise
More mileage than expected from a little example
Cropped from World Science Festival source
Sean Carroll is a cosmologist in the Department of Physics at Caltech. He also maintains a blog, “Preposterous Universe,” and writes books promoting the public understanding of science. I have recently been enjoying his 2010 book From Eternity to Here: The Quest for the Ultimate Theory of Time.
Today—yes, Carroll would agree that there is a today—I would like to share an interpretation of a little quantum computing example that occurred to me while reading his book.
As befits a book about how much of physics is time-reversible, I’ve been reading it in reverse order of chapters. From my own scientific knowledge and reading of similar books I figured I knew the run-up material to his conclusions and speculations. Now I’m working backward to fill some gaps in my knowledge and highlight how he supported those speculations I query. I’ve been pleased to find freshness in his coverage even of well-traveled topics, and this extends to his chapter on quantum basics.
In a popular science book one tries to maximize mileage from simple examples but must heed the dictum ascribed to Albert Einstein to “make everything as simple as possible, but not simpler.” I didn’t think that quantum decoherence could be adequately illustrated with just two elements, but the reliable Carroll does so. Since this augments an example that Dick and I use in our quantum algorithms textbook, I thought we’d share it.
Briefly on Carroll’s Book
Since Carroll does not claim his answer based on papers with Jennifer Chen in 2004-05 does anything more than illustrate how an “ultimate theory” could work, I don’t think it’s “spoiling” to mention it here. His blog’s two regular graphics are the equation defining entropy on Ludwig Boltzmann’s tombstone in Vienna and this poster based on his book:
The similar diagram in his book identifies the waist as a point of lowest entropy for the entire cosmos. ‘Baby universes’ branch off in funnels in both (or one could say all) directions of time. We are in one of them, inflating out from our Big Bang, and while that was a state of incredibly low entropy within our branch, it is but a blip in a grand system that is able to increase its entropy without limit.
I would have liked to see more in the book on how this squares with the “BGV” conditions under which general relativity requires an expanding universe to have a boundary in the past, and how their model relates to the “all-or-nothing argument” covered in our post two years ago on Jim Holt’s book Why Does the World Exist? Why should the lowest entropy have some particular nonzero finite value—that is, why, if the waistline is to be labeled some kind of origin for the whole multiversal shebang? These elements are of course subservient to quantum theory in whichever theory of quantum gravity proves to reconcile best with relativity and observation.
Carroll has addressed much of this on his blog, in particular within this post a year ago on an origins/theology debate. That’s one thing blogs are good for, and he supplies many links including this long critique with much on BGV. But leaving everything aside, let’s think about systems with just two quantum elements that give binary classical values when observed. Carroll calls them “Mr. Dog” and “Miss Kitty,” whereas I’ll use other animals toward further conceptual associations.
Quantum Coordinates and Classical Indexing
In quantum computation, Boolean strings of bits are coded via qubits. The qubits are represented via orthogonal basis vectors in the vector space where . The standard quantum indexing scheme enumerates in lexicographical order as
Labeling these strings , the rule is that is encoded by the standard basis vector
with the lone in the -th position. Any linear combination is allowed as a quantum pure state provided . Measuring entirely then yields the output with probability . In particular, measuring yields with certainty.
This scheme telescopes for in that for for any binary strings and , the basis vector for their concatenation is given by the tensor product of and . Tensor product can be visualized first in the case of matrices and of arbitrary sizes. If
If is a matrix, then becomes an matrix, but it could also be regarded as a higher-dimensional object. Two vectors in column form are just the case . We can still visualize that the second vector is getting multiplied in block form by entries of the first vector. The indexing scheme kicks off with:
Then we obtain:
and so on for , , and .
Just as concatenation of strings is a basic operation apart from indexing notation, so too with tensor product. When , so that and have length , our representation of the tensor product involves -many indices. It seems silly to posit a quadratic expansion on top of an exponential explosion just for juxtaposing two -bit strings that don’t even interact, but the classical notation does this. Since we will limit to two qubits we don’t mind: , so . We think of as quantum coordinates and as classical indices for the same system.
Matrices and Mazes
Quantum operations on qubits are represented by matrices that are unitary, meaning that multiplied by its conjugate transpose gives the identity. The Hadamard matrix
is not only unitary but also self-adjoint: . It works on one qubit and maps to , which we abbreviate as , and maps to or for short.
We can interpret each entry as the transition amplitude of going from to . Since we are using column vectors the “from” is a column and the “to” is a row. Then is like a maze where each column point of entry allows either row as an exit, but the path that enters at and exits at picks up a amplitude along the way.
Think of as coming in “like a lamb” and as “like a lion.” Then (divided by ) represents the saying:
March comes in like a lion and goes out like a lamb.
Whereas, represents this winter’s actuality of coming in and going out like a lion. Let us call going lion-to-lamb or lamb-to-lion a flip, lamb-to-lamb a flap, and lion-to-lion a flop.
Both inputs and encounter amplitude for a flip, which translates to 50% probability in a measurement. The state gives equal amplitude to “lamb” or “lion” as outcomes, hence probability 50% each of observing them. The state gives different signs (speaking more generally, different phases) to the outcomes but still the same 50%-50% probabilities.
We might think that following with another operation would preserve the even chance of doing a flip, but instead it zeroes it. Multiplying gives because both off-diagonal entries sum a and a (divided by ). For the comes from the history of a flap then a flip, while the comes from a flip then a flop. The components flap-flip and flip-flop interfere, leaving no way the composed operations can accomplish a flip. If you come in as a lion then the actions flip-flap and flop-flip would individually make you a lamb, but they likewise interfere, leaving no option but to go out as a lion.
Put another way, applying to leaves a deterministic outcome of “lamb.” The coherence of the superposed state makes this possible. Likewise, applying to entails “lion.”
Now let’s introduce our second qubit and describe it as a butterfly, with meaning its wings are open and meaning closed. Here is an operation on two qubits:
This is a permutation matrix that swaps and but leaves and fixed. Viewed as a maze it routes column entrances to row exits with no choice, no meeting of corridors, and so executes a deterministic operation. In our system of lamb/lion and open/closed it says that March being a lamb leaves the butterfly undisturbed, but “lion” makes it shift its wings. So inversion is controlled by the component of the first qubit, hence the name CNOT for “Controlled NOT.”
Just by dint of juxtaposing the second qubit, we change the brute matrix notation for the Hadamard operation on our first qubit to:
Now equals the identity matrix, so we still have interference on the first qubit. But suppose we perform and then CNOT instead. Viewed as a quantum circuit going left to right it looks like this:
But since we are composing right-to-left on column vectors, the matrix for the combined operation is
On argument it yields . This state—call it —cannot be written as a tensor product of two one-qubit states. This means is entangled. In our terms it means the butterfly’s wings are open if and only if March is like a lamb; in case of lion they are shut. But if we only care about lamb-versus-lion we still have the same amplitudes and 50-50 split that we had with the one-qubit state . On argument the circuit entangles and instead.
Suppose we forgot about the butterfly and tried the same trick of applying once more to . We might expect to get “lamb” again, but what we get is:
This state is also entangled but gives equal probability to all outcomes. To the holder of the first qubit it works the same as a classical coin flip between “lamb” and “lion.” Indeed if we trace out the unseen butterfly, yields a mixed state that presents a classical distribution on , and applying to that creates no interference. Indeed, there are no cancellations at all in the entire matrix computation:
This is diagrammed by the following two-qubit quantum circuit:
This example shows two other fine points. First, the “copy-uncompute” trick (see Fig. 3 here) fails markedly when the value at the control of the CNOT gate is a superposition that is not close to a basis state. The entanglement involved in attempting to copy it via the CNOT destroys the interference needed to “uncompute” the first qubit back to , despite being its own inverse. Thus decoherence does not involve any “collapse” into classical behavior, but makes it emerge from unseen entanglements.
Second, if we run the circuit on the input state then we get which is fixed by CNOT, so the final gives back again. At no time was there any entanglement. Hence the entangling action of a quantum circuit is not invariant under the input being separable nor under choice of basis, though perhaps some algebraic-geometric measure of its entangling “potential” can be.
I had previously pictured ‘decoherence’ in terms of many little entanglements with the environment. What happens if the entanglement with our butterfly is minor? Let be a possible starting state for the butterfly, and consider the state
with chosen to normalize. Then
The probability of observing (“lion”) on the first qubit is just , regardless of . This practically negligible deviation can be interpreted in two different ways:
- Coherence to high-order precision can be achieved even in the presence of non-negligible entanglement—before even mentioning quantum error-correcting codes and their recent possible cosmological significance.
- That our experiments record coherence to 15-place precision and more does not prevent there being some non-negligible amount of “pervasive” entanglement.
To continue the “butterflies” metaphor, pervasive could entail entanglement with millions of them. The question is whether this would collectively drive up beyond what is compatible with experimental results. Perhaps it wouldn’t; I’m not conversant enough with the models to guess. But I have a fresh angle that was brought again to mind by an association Carroll makes between information and the holographic principle (page 281):
[It] seems to be telling us that some things just can’t happen, that the information needed to encode the world is dramatically compressible.
If our environment is highly compressible, would this manifest as pervasive entanglement? Here are two naive thoughts. The first is that the maximally entangled state subtracts one bit of information from a two-bit system, likewise the related state . The naiveness is that the local computation , as we have seen, restores having equal-weight outcomes in the standard basis—so the idea is not local-invariant and prefers a basis. Yet it is possible that cross-cutting -entanglements could embody a large information deficit in any (natural) basis. The second naive thought is that states like might contribute even amounts to certain statistical measures in large-block fashion, so as to skew expectations of (non-)uniformity that assume full independence.
Neither thought is new—related ones have been raised in connection with cosmological problems and theories discussed in Carroll’s book, though apparently without traction as yet. What my “Digital Butterflies” post brings is a digital arena in which the information content of the environment can be varied and its dynamical effects studied. The environment stems from about 50,000 bits that initialize a tabulation hashing scheme employed by all major chess programs. Many programs generate the 50,000 bits pseudorandomly, though one could just drop them in from a truly random source since they are fixed. Perhaps the hash-table dependent effects observed in the post can inform these issues, and also work toward the “grail” of developing a practical distinguisher of general pseudorandomness.
How far can quantum computation help understand issues in cosmology?
Update 5/17/15: This 4/28 article in Quanta magazine by Jennifer Ouellette—Carroll’s wife—covers the “MERA” proposal and others attempting to derive space-time from entanglements. We have not had time to study this.
[added point to end of “Decoherence” section; two minor typo fixes]