# 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.”

## Two Qubits

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.

## Decoherence

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.

## Practical Butterflies?

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.

## Open Problems

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]

“It seems silly to posit a quadratic expansion on top of an exponential explosion just for juxtaposing two n-bit strings that don’t even interact.”

But keep in mind that this is also true for classical probability distributions: the tensor product corresponds to the joint distribution you get for two independent variables.

Regarding decoherence: the easiest way to think of it is in terms of losing phase information. If we have a state $(1/\sqrt{2}) (|0> + e^{i \theta} |1>)$, but if theta becomes random because of interactions with the environment, then this becomes a classical mixture of |0> and |1>. It’s easiest to see this in terms of the density matrix $\rho$: randomizing theta zeroes out $\rho$’s off-diagonal entries, leaving a purely classical distribution (the completely mixed state).

Cris, thanks. On the first, that’s true, but the quantum wave still strikes me as more of a single entity than the classical distribution(s). Not sure on your second point from a non-physics vantage; anyway it plays into why I was surprised by Carroll’s pulling it off speaking mainly in terms of pure states of only two qubits.

I would urge you not to think about the density matrix as a “physics vantage” 🙂 it’s by far the easiest way to represent combinations of classical uncertainty and quantum superposition. I don’t know of a cleaner formalism to express something which is, say, (|0>+|1>)/sqrt(2) with probability 1/2, and (|0>-|1>)/sqrt(2) with probability 1/2. It also lets us see that this is the same thing as a thing which is |0> with probability 1/2 and |1> with probability 1/2 (or with any other two orthogonal basis vectors in the mixture). And it lets us see a continuum of states ranging from this completely mixed state to pure states.

Keep in mind also that the density matrix has been used very successfully in CS; for instance, in Ambainis’ lower bound on Grover’s algorithm, namely that sqrt(n) queries are necessary. He used the decay of the off-diagonal entries as a simple measure of entanglement: the computer can’t answer the question until it becomes sufficiently entangled with the oracle.

OK—maybe we’ll invite a guest post on density matrices 🙂

Incidentally, situations where ε is non-negligible while ε² is negligible were used by David Mumford and John Tate in their Alexander Grothendieck memorial to motivate Grothendieck’s embrace of

nilpotentelements.The eps vs eps^2 thing comes up a lot in physics, specifically in wave mechanics. The energy density of a wave is proportional to the square of its amplitude, which can be used to explain things like Grover’s algorithm and

https://en.wikipedia.org/wiki/Elitzur%E2%80%93Vaidman_bomb_tester

What do you mean by pervasive entanglement?

Hi, Aram—thanks first for the examples. I picked up “pervasive” from Vlatko Vedral’s 2011 Scientific American article where the rock salt experiment by Aeppli et al. really struck me. The import to me is: a macroscopic system where entanglement is not mandated by its description or our knowledge of how it was produced, in which we detect different dynamics from what we’d find if it were absent. The term is also used in this blog poll by John Preskill to define the scale of decoherence by which the classical world emerges (in one response option). Whenever people speak of tangible effects of entanglements stemming from the Big Bang/inflation/whatever-before, that’s included.

I should clarify that my angle doesn’t have to involve “entanglement”: it’s about detecting different “digital dynamics” between environments that can be made truly-random or compressible. But on reading Gil’s paper in Jan. 2007 right after discovering the chess phenomenon I perceived a connection. Another example of what I mean by “naiveness” in the post is that by some measures, a GHZ state has just 1 unit of entanglement for all m, whereas under my intended connection it subtracts m-1 bits of information.

To answer Alex V below, I can quote Carroll again on page 280 (one sentence shortened): “Here’s why holography is important: It means that spacetime is not fundamental. [We] typically think [in terms of] locality. Holography says that we can’t really do that, in principle—there are subtle correlations between things that happen at different locations, which cut down on our freedom to specify a configuration of stuff through space.”

In next paragraph he gave even more simple explanation “The holographic principle says that the universe is like that, on a fundamental level: Everything you think is happening in three-dimensional space is secretly encoded in a two-dimensional surface’s worth of information.” But how to reduce exponential quantum computing space into polynomial one?

In his recent book

, mathematician Michael Harris — a FIelds medalist whose thesis advisor was David Mumford — directs readers toward the natural next step: from the 3+1 dimensions of spacetime, to the 2+1 dimensions of a holographic boundary, to a countable set of points on algebraic spaces in whichMathematics Without Apologies: Portrait of a Problematic Vocation“It remains only to fill in the details” (to borrow Pauli’s pithy phrase) … albeit with modern-day quantum simulation codes as our guiding avatars … these ideas are good news for today’s young researchers.

CorrectionMichael Harris’Mathematics Without Apologies, names David Mumford as “one of my former teachers”, however Harris’ doctoral advisor was Barry Mazur … both Mumford and Mazur are outstanding teachers, needless to say.In regard to Ken’s point, David Mumford has posted a longer (unredacted) version of his and Tate’s

NatureGrothendieck Memorial as an essayCan one explain schemes to biologists?. This extended essay is accompanied by reader comments that are plenty interesting too.In regard to Aram’s point, it is a 21st century Great Truth that ε vs ε^2 arise naturally in the theory of decoherent dynamics, albeit with ε^2

notnegligible, via the Ito/Stratonovich calculus associated to quantum Lindblad processes (see as a primer, Carlton Caves’ on-line notes “Completely positive maps, positive maps, and the Lindblad form”).Further references relating to categoric ε-topics would be welcomed by me and many …

… especially references that respect Lawvere’s friendly maxim!

I often met references to http://en.wikipedia.org/wiki/Holographic_algorithm trying to “compress” some quantum computing models (i.e. effectively simulate them by classical computer), but still did not guess, how such “holography” could be related to “compression”

Dear Professor, I have “known better” this paper can be the solution of P versus NP:

https://hal.archives-ouvertes.fr/hal-01139624

and pdf in

https://hal.archives-ouvertes.fr/hal-01139624/document

Indeed, in that work I proved that:

$POLYLOGTIME \neq NLOGTIME$

in a trivial way. Next, I proved that:

If $P = NP$, then $POLYLOGTIME = NLOGTIME$.

in a trivial way too. From that result we can see $P \neq NP$.

For that reason I’m quite assure there are big chances that my proof were correct. Certainly, I’m truly convinced, even though I have failed several times with other intents.

Regards..

Frank, you need to show that there is no reversibility in GF(2).

Namely, the identity gate is one-way if NOT gate is one-way in GF(2).

This seems to be trivial:

https://unitambo.wordpress.com/2015/04/01/one-way-bijection-over-gf2/

if we succeed in cascading two controlled-NOT gates to implement a permutation operation, |1 0> –>|1 1> provokes a spontaneous symmetry breaking. This is exactly the Higgs mechanism. This is exactly Levin’s one-way bijection…this is exactly P versus NP problem.

http://www.researchgate.net/publication/274083310_A_plain_proof_that_Levin%27s_combinatorial_function_is_one-way%28draft%29

Here’s news of broad interest to readers of weblogs

Gödel’s Lost Letter, and in particular a fine learning-opportunity for students:There’s plenty more material on the LogiQ Program Proposer’s Day announcement page.

Readers of Michael Harris’ book and/or weblog

Mathematics Without Apologies(as they are both titled) will appreciate that IARPA is designating stable logical qubits as anavatar(in Harris’ phrase) for catalyzing advances in our general understanding of noise, decoherence, and entropy.ConclusionThephysicalprocess of removing von Neumann entropy from systems of qubits/qudits can be appreciated as a mathematicalavatar— in Michael Harris’ phrase — for the computational algorithms that (heuristically) are so marvelously effective in removing Boltzmann entropy from atoms/molecules in large-scale quantum simulation software … sufficient to compose (F)foundations for the $120M/5yr investment by the Swiss-based pharmaceutical corporation Sanofi in the Portland-based quantum simulation corporation Schrödinger.Hopefully at least

someEast Coast quantum cognoscenti will attempt/report on this fine workshop!