{\huge A Quantum Two-Finger Exercise}
More mileage than expected from a little example \vspace{.1in}
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 $latex {S = k\log W}&fg=000000$ defining entropy on Ludwig Boltzmann's tombstone in Vienna and this poster based on his book:
\includegraphics[width=1in]{FETH-poster-sm}
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---or at least 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? Squaring all this is 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 we use other animals toward further conceptual associations.
Quantum Coordinates and Classical Indexing
In quantum computation, Boolean strings of $latex {n}&fg=000000$ bits are coded via $latex {n}&fg=000000$ qubits. The qubits are represented via orthogonal basis vectors in the vector space $latex {\mathbb{C}^N}&fg=000000$ where $latex {N = 2^n}&fg=000000$. The standard quantum indexing scheme enumerates $latex {\{0,1\}^n}&fg=000000$ in lexicographical order as
$latex \displaystyle 0^n,0^{n-1}1,0^{n-2}10,\dots,1^{n-1}0,1^n. &fg=000000$
Labeling these strings $latex {x_1,\dots,x_N}&fg=000000$, the rule is that $latex {x_i}&fg=000000$ is encoded by the standard basis vector$latex \displaystyle e_{x_i} = e_i = [0,0,0,\dots,0,1,0,0,\dots,0]^T &fg=000000$
with the lone $latex {1}&fg=000000$ in the $latex {i}&fg=000000$-th position. Any linear combination $latex {\vec{a} = \sum_{i=1}^N a_i e_i}&fg=000000$ is allowed as a quantum pure state provided $latex {\sum_i |a_i|^2 = 1}&fg=000000$. Measuring $latex {\vec{a}}&fg=000000$ entirely then yields the output $latex {x_i}&fg=000000$ with probability $latex {|a_i|^2}&fg=000000$. In particular, measuring $latex {e_i}&fg=000000$ yields $latex {x_i}&fg=000000$ with certainty.This scheme telescopes for $latex {n = 0,1,2,3,\dots}&fg=000000$ in that for for any binary strings $latex {x}&fg=000000$ and $latex {y}&fg=000000$, the basis vector $latex {e_{xy}}&fg=000000$ for their concatenation is given by the tensor product of $latex {e_x}&fg=000000$ and $latex {e_y}&fg=000000$. Tensor product can be visualized first in the case of matrices $latex {A}&fg=000000$ and $latex {B}&fg=000000$ of arbitrary sizes. If
$latex \displaystyle A = \begin{bmatrix} a_{1,1} & \cdots & a_{1,n}\\ \vdots & \ddots & \vdots\\ a_{m,1} & \cdots & a_{m,n} \end{bmatrix},\quad\text{then}\quad A \otimes B = \begin{bmatrix} a_{1,1}B & \cdots & a_{1,n}B\\ \vdots & \ddots & \vdots\\ a_{m,1}B & \cdots & a_{m,n}B \end{bmatrix}. &fg=000000$
If $latex {B}&fg=000000$ is a $latex {p \times q}&fg=000000$ matrix, then $latex {A \otimes B}&fg=000000$ becomes an $latex {mp \times nq}&fg=000000$ matrix, but it could also be regarded as a higher-dimensional $latex {m \times n \times p \times q}&fg=000000$ object. Two vectors in column form are just the case $latex {p = q = 1}&fg=000000$. 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:$latex \displaystyle \begin{array}{rcl} e_{\lambda} &=& \begin{bmatrix} \,1\, \end{bmatrix}\\ e_0 &=& \begin{bmatrix} 1 \\ 0 \end{bmatrix}\\ e_1 &=& \begin{bmatrix} 0 \\ 1 \end{bmatrix}. \end{array} &fg=000000$
Then we obtain:$latex \displaystyle \begin{array}{rcl} e_{00} &=& e_0 \otimes e_0 = \begin{bmatrix}1\cdot\begin{bmatrix}1 \\ 0\end{bmatrix}\\ 0\cdot\begin{bmatrix}1 \\ 0\end{bmatrix} \end{bmatrix} = \begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix}, \end{array} &fg=000000$
and so on for $latex {e_{01} = e_0 \otimes e_1 = [0,1,0,0]^T}&fg=000000$, $latex {e_{10} = e_1 \otimes e_0 = [0,0,1,0]^T}&fg=000000$, and $latex {e_{11} = e_1 \otimes e_1 = [0,0,0,1]^T}&fg=000000$.Just as concatenation of strings is a basic operation apart from indexing notation, so too with tensor product. When $latex {|x| = |y| = n}&fg=000000$, so that $latex {e_x}&fg=000000$ and $latex {e_y}&fg=000000$ have length $latex {N = 2^n}&fg=000000$, our representation of the tensor product involves $latex {N^2}&fg=000000$-many indices. It seems silly to posit a quadratic expansion on top of an exponential explosion just for juxtaposing two $latex {n}&fg=000000$-bit strings that don't even interact, but the classical notation does this. Since we will limit to two qubits we don't mind: $latex {n = 2}&fg=000000$, so $latex {N = 4}&fg=000000$. We think of $latex {1\dots n}&fg=000000$ as quantum coordinates and $latex {1\dots N}&fg=000000$ as classical indices for the same system.
Matrices and Mazes
Quantum operations on $latex {n}&fg=000000$ qubits are represented by $latex {N \times N}&fg=000000$ matrices $latex {A}&fg=000000$ that are unitary, meaning that $latex {A}&fg=000000$ multiplied by its conjugate transpose $latex {A^*}&fg=000000$ gives the identity. The Hadamard matrix
$latex \displaystyle H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} &fg=000000$
is not only unitary but also self-adjoint: $latex {H^* = H}&fg=000000$. It works on one qubit and maps $latex {e_0}&fg=000000$ to $latex {\frac{1}{\sqrt{2}}(e_0 + e_1)}&fg=000000$, which we abbreviate as $latex {e_+}&fg=000000$, and maps $latex {e_1}&fg=000000$ to $latex {\frac{1}{\sqrt{2}}(e_0 - e_1)}&fg=000000$ or $latex {e_-}&fg=000000$ for short. We can interpret each entry $latex {H[i,j]}&fg=000000$ as the transition amplitude of going from $latex {e_i}&fg=000000$ to $latex {e_j}&fg=000000$. Since we are using column vectors the ``from'' is a column and the ``to'' is a row. Then $latex {H}&fg=000000$ is like a maze where each column point of entry allows either row as an exit, but the path that enters at 2 and exits at 2 picks up a $latex {-1/\sqrt{2}}&fg=000000$ amplitude along the way.Think of $latex {e_0}&fg=000000$ as coming in ``like a lamb'' and $latex {e_1}&fg=000000$ as ``like a lion.'' Then $latex {H[1,2] = 1}&fg=000000$ represents the saying:
March comes in like a lion and goes out like a lamb.
Whereas, $latex {H[2,2] = -1}&fg=000000$ 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 $latex {e_0}&fg=000000$ and $latex {e_1}&fg=000000$ encounter amplitude $latex {1/\sqrt{2}}&fg=000000$ for a flip, which translates to 50% probability in a measurement. The state $latex {H e_0 = e_+}&fg=000000$ gives equal amplitude to ``lamb'' or ``lion'' as outcomes, hence probability 50% each of observing them. The state $latex {H e_1 = e_-}&fg=000000$ 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 $latex {H}&fg=000000$ operation would preserve the even chance of ``flipping,'' but instead it zeroes it. Multiplying $latex {H\cdot H}&fg=000000$ gives $latex {I}&fg=000000$ because both off-diagonal entries sum a $latex {+1}&fg=000000$ and a $latex {-1}&fg=000000$ (divided by $latex {2}&fg=000000$). For $latex {H^2[1,2]}&fg=000000$ the $latex {+1}&fg=000000$ comes from the history of a flap then a flip, while the $latex {-1}&fg=000000$ comes from a flip then a flop. The components flap-flip and flip-flop interfere. 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 $latex {H}&fg=000000$ to $latex {e_+}&fg=000000$ leaves a deterministic outcome of ``lamb.'' The coherence of the superposed state $latex {e_+}&fg=000000$ makes this possible. Likewise, applying $latex {H}&fg=000000$ to $latex {e_-}&fg=000000$ entails ``lion.''
Two Qubits
Now let's introduce our second qubit and describe it as a butterfly, with $latex {e_0}&fg=000000$ meaning its wings are open and $latex {e_1}&fg=000000$ meaning closed. Here is an operation on two qubits:
$latex \displaystyle CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} &fg=000000$
This is a permutation matrix that swaps $latex {x_3 = 10}&fg=000000$ and $latex {x_4 = 11}&fg=000000$ but leaves $latex {x_1 = 00}&fg=000000$ and $latex {x_2 = 01}&fg=000000$ 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, the Hadamard operation on our first qubit changes its notation to
$latex \displaystyle H_1 = H \otimes I = \left[\begin{array}{c|c} 1\cdot I & 1\cdot I\\ \text{------} & \text{------}\\ 1\cdot I & -1\cdot I \end{array}\right] = \begin{bmatrix} 1 & \;\,0 & 1 & 0\\ 0 & \;\,1 & 0 & 1\\ 1 & \;\,0 & -1 & 0\\ 0 & \;\,1 & 0 & -1 \end{bmatrix}. &fg=000000$
Now $latex {H_1\cdot H_1}&fg=000000$ equals the $latex {4 \times 4}&fg=000000$ identity matrix, so we still have interference on the first qubit. But suppose we perform $latex {H_1}&fg=000000$ and then CNOT instead. Viewed as a quantum circuit going left to right it looks like this:
\includegraphics[width=2in]{HCNOT.png}
But since we are composing right-to-left on column vectors, the matrix for the combined operation is
$latex \displaystyle CNOT\cdot H_1 = \begin{bmatrix} 1 & \;\,0 & 1 & 0\\ 0 & \;\,1 & 0 & 1\\ 0 & \;\,1 & 0 & -1\\ 1 & \;\,0 & -1 & 0 \end{bmatrix}. &fg=000000$
On argument $latex {e_{00}}&fg=000000$ it yields $latex {\frac{1}{\sqrt{2}}(e_{00} + e_{11})}&fg=000000$. This state---call it $latex {f_+}&fg=000000$---cannot be written as a tensor product of two one-qubit states. This means $latex {\phi}&fg=000000$ 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 $latex {e_+}&fg=000000$. On argument $latex {e_{01}}&fg=000000$ the circuit entangles $latex {e_{01}}&fg=000000$ and $latex {e_{10}}&fg=000000$ instead.
Decoherence
Suppose we forgot about the butterfly and tried the same trick of applying $latex {H_1}&fg=000000$ once more to $latex {f_+}&fg=000000$. We might expect to get ``lamb'' again, but what we get is:
$latex \displaystyle H_1 f_+ = \frac{1}{2} \begin{bmatrix} 1 & \;\,0 & 1 & 0\\ 0 & \;\,1 & 0 & 1\\ 1 & \;\,0 & -1 & 0\\ 0 & \;\,1 & 0 & -1 \end{bmatrix} \; \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ -1 \end{bmatrix}. &fg=000000$
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, $latex {f_+}&fg=000000$ yields a mixed state that presents a classical $latex {(\frac{1}{2},\frac{1}{2})}&fg=000000$ distribution on $latex {(e_0,e_1)}&fg=000000$, and applying $latex {H}&fg=000000$ to that creates no interference. Indeed, there are no cancellations at all in the entire $latex {4 \times 4}&fg=000000$ matrix computation:$latex \displaystyle \frac{1}{2} \begin{bmatrix} 1 &\; 0 & 1 &\! 0\\ 0 &\; 1 & 0 &\! 1\\ 1 &\; 0 & -{1} &\! 0\\ 0 &\; 1 & 0 &\! -{1} \end{bmatrix} \begin{bmatrix} 1 &\;\, 0 &\;\, 0 &\;\, 0\\ 0 &\;\, 1 &\;\, 0 &\;\, 0\\ 0 &\;\, 0 &\;\, 0 &\;\, 1\\ 0 &\;\, 0 &\;\, 1 &\;\, 0 \end{bmatrix} \begin{bmatrix} 1 &\; 0 & 1 &\! \!0\\ 0 &\; 1 & 0 &\! \!1\\ 1 &\; 0 & -{1} &\! \!0\\ 0 &\; 1 & 0 &\! \!-{1} \end{bmatrix} = \frac{1}{2} \begin{bmatrix} \!1 &\!\! 1 &\!\! 1 &\!\! -{1}\\ \!1 &\!\! 1 &\!\! -{1} &\!\! 1\\ \!1 &\!\! -{1} &\!\! 1 &\!\! 1\\ \!-{1} &\!\! 1 &\!\! 1 &\!\! 1 \end{bmatrix}. &fg=000000$
This is diagrammed by the following two-qubit quantum circuit:
\includegraphics[width=2.5in]{HCNOTH.png}
Incidentally, this exemplifies how the ``copy-uncompute'' trick (see Fig. 3 here) fails 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 $latex {e_0}&fg=000000$, despite $latex {H_1}&fg=000000$ being its own inverse. Thus decoherence does not involve any ``collapse'' into classical behavior, but makes it emerge from unseen entanglements.
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, as represented by the state
$latex \displaystyle \phi = \epsilon f_+ + \sqrt{1 - \epsilon^2}(e_+ \otimes B) = \frac{1}{\sqrt{2}}\begin{bmatrix} \epsilon + a\sqrt{1-\epsilon^2} \\ b\sqrt{1 - \epsilon^2} \\ a\sqrt{1 - \epsilon^2} \\ \epsilon + b\sqrt{1 - \epsilon^2} \end{bmatrix} &fg=000000$
for some arbitrary state $latex {B = ae_0 + be_1}&fg=000000$ of the butterfly? Then$latex \displaystyle H_1 \phi = \frac{1}{2}\begin{bmatrix} \epsilon + a\sqrt{1-\epsilon^2} + a\sqrt{1-\epsilon^2} \\ b\sqrt{1 - \epsilon^2} + \epsilon + b\sqrt{1 - \epsilon^2} \\ \epsilon + a\sqrt{1-\epsilon^2} - a\sqrt{1 - \epsilon^2} \\ b\sqrt{1 - \epsilon^2} - (\epsilon + b\sqrt{1 - \epsilon^2}) \end{bmatrix} = \frac{1}{2}\begin{bmatrix} \epsilon + 2a\sqrt{1 - \epsilon^2} \\ \epsilon + 2b\sqrt{1 - \epsilon^2} \\ \epsilon \\ -\epsilon \end{bmatrix}. &fg=000000$
The probability of observing $latex {1}&fg=000000$ (``lion'') on the first qubit is just $latex {\epsilon^2}&fg=000000$, regardless of $latex {B}&fg=000000$. This practically negligible deviation can be interpreted in two different directions:
To continue the 'butterflies' metaphor, pervasive could entail entanglement with millions of them. The question is whether this would collectively drive up $latex {\epsilon}&fg=000000$ beyond what is compatible with experimental results. Perhaps it wouldn't; I'm not conversant enough with the models to guess. But I have an angle that was brought again to mind by an association Carroll on page 281 makes between information and the holographic principle:
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 appear to us as pervasive entanglement? One can view entanglements such as $latex {f_+}&fg=000000$ as removing one bit of information from a two-bit system. Cross-cutting $latex {\epsilon}&fg=000000$-entanglements could carry a large information deficit. If they behave like $latex {(e_{10} + e_{01})/\sqrt{2}}&fg=000000$ by dint of contributing even amounts to certain statistical measures, can they answer problems of observed uniformity for which other theories discussed in Carroll's book were devised?
None of these musings is new and some are under definite clouds. My ``Digital Butterflies'' post, however, describes a compressible background used by chess programs via tabulation hashing. This provides a digital arena that might help explore behaviors that inform these questions, toward the ``grail'' of developing a practical distinguisher of general pseudorandomness.
Open Problems
How far can quantum computation help understand issues in cosmology?