## Wednesday, 19 February 2014

### A note on quantum superposition

Quantum computing is commonly described as the means of harnessing the laws of quantum mechanics to process information, usually for the purpose of doing certain calculations faster than what you can achieve with conventional computers.

A typical computer operates on binary digits, or bits, of information, which is a sequence of zeros and ones encoded by electrical signals. A calculation is performed using a circuit of transistors designed to switch the signals on and off in a particular way, so that the final bit values determine the result.  The list of specific steps needed for handling bits in any such calculation is called an algorithm.

In contrast,  a quantum computer encodes information in quantum bits, or qubits. Computation with qubits is different from computation with bits because quantum systems can be prepared and controlled in ways that can not be achieved with signals that represent bits. Quantum algorithms describe ways in which qubits can be manipulated so that the correct measurement yields the desired outcome of a calculation with high probability.

It is a characteristic feature of quantum theory that measurements in general do not have definite outcomes. Rather, what we have is a list of probabilities for each possible outcome. This begs the question, can't you just use randomized bits to generate the same kind of probabilities? You can't and part of the reason lies in the differences between a probabilistic bit and a quantum superposition.

Consider a coin. When flipped it can come up heads or tails. If we represent heads by $H$ and tails by $T$, then we can represent the state of a coin by its probability to land heads or tails. Suppose we believe we have a fair coin with the same chance of landing heads or tails. The state $C$ that we assign to the coin is then $C = \frac{1}{2} H + \frac{1}{2} T$.

Now consider an electron. You might recall from your chemistry classes that electrons have a property called spin, which can be up and down, and pair of such spins are required to fill in orbitals in an atom. In any case, spin is a quantum property of an electron that is an example of a qubit. We can assign a quantum state to the electron that describes the probability of measuring it in a up or down orientation.

Let $|u\rangle$ denote the state of an electron with spin pointing up and $|d\rangle$ for spin pointing down. An example of a state the has equal chance of being measured with the electron spin pointing up or down is  $|+\rangle = \frac{1}{\sqrt{2}} \left( |u\rangle + |d \rangle \right)$.

If we think of $|u\rangle$ and $|d\rangle$ as the quantum versions of $H$ and $T$, then we see that one main difference between bit states and qubit states is the fact that the numbers that appear in quantum states are not probabilities but rather probability amplitudes.  In general, these amplitudes are complex numbers whose absolute values when squared correspond to probabilities.

Since quantum states use complex numbers, there are many states that describe an electron that has equal chance of being found with the spin up or down. Another such example would be the state $|-\rangle = \frac{1}{\sqrt{2}} \left( |u\rangle - |d \rangle \right)$. We can easily check this since $\left( \frac{1}{\sqrt{2}} \right)^2 = \frac{1}{2}$ .

In experiments, we verify the probabilities by first preparing many electrons in the same state and then performing identical spin measurements on each electron. The relative frequency of the each outcome provides an estimate of the probabilities.

 Qubit states as arrows directed toward points on a sphere starting from its center.

The picture of a qubit provided by the spin of an electron is actually quite useful because just as up and down can point to any orientation in 3-dimensional space, the same holds for a qubit. In geometric terms, we would say that the set of all possible states for a qubit corresponds to points on a sphere, or since we are considering the direction of electron spin, to arrows that go from the center of the sphere.

Imagine that sphere of qubit states to be labeled geographically like a globe. We can call state $|u\rangle$ the arrow pointing towards the north pole and $|d\rangle$ will be the one pointing towards the south pole. Furthermore, we can choose the state $|u\rangle$ to be the direction along the equator pointing towards the prime meridian, and the state $|-\rangle$ would be the pointing directly opposite that. Any direction lying on the equator would be a superposition state with the same probability of being measured in $|u\rangle$ or $|d\rangle$ but distinct directions will involve different complex numbers.

One other thing to note from picturing qubit states as forming a sphere is that oppositely directed points, such as $|u\rangle$ and $|d\rangle$, or $|+\rangle$ and $|-\rangle$ , correspond to states that can be perfectly distinguished by measurement. What this means is that if we are promised that the electron has been prepared with spin state $|u\rangle$ or $|d\rangle$, then we can perform the measurement "$|u\rangle$ or $|d\rangle$" to determine which state it is. Formally, we would say the 2 states are orthogonal and any such pair of states define a projective measurement.

What happens if we have an electron in state $|u\rangle$ and perform a "$|+\rangle$ or $|-\rangle$" measurement on it? To see what we get, observe that we can write $|u\rangle = \frac{1}{\sqrt{2}} \left( |+\rangle + |-\rangle \right)$ so a "$|+\rangle$ or $|-\rangle$" measurement  will yield  $|+\rangle$ or $|-\rangle$ with the same probability. We see that the 2 pairs of states $A = |u\rangle,|d\rangle$ and $B = |+\rangle,|-\rangle$  lead to a mirror situation of equal probabilities if we prepare a state from one pair and perform a measurement from the other pair.

This means that we have an uncertainty principle between the properties "$|u\rangle$ or $|d\rangle$" and "$|+\rangle$ or $|-\rangle$", since knowing we have a state that belongs to pair $A$ means are totally uncertain of the outcome when we measure using the pair $B$, and vice-versa.  This is in fact a qubit version of the well-known uncertainty principle often mentioned with regard to position and momentum of a quantum particle.

Is it possible to prepare electron spins that behave like a fair coin? The answer is yes and this requires we prepare a probabilistic mixture instead of a superposition. For instance, we can have a device that randomly prepares electrons with spin up or down with equal probability, in which case the state is given by $M = \frac{1}{2} \left( |u\rangle\langle u| + |d \rangle \langle d| \right)$, using a notation similar to what is often used by physicists.

At this point, it is worth mentioning that $|u\rangle\langle u|$ describes the same state as $|u\rangle$, but mathematically $|u\rangle$ would be expressed by a column vector while $|u\rangle\langle u|$ would be the corresponding matrix given by "multiplying" the column vector $|u\rangle$ with the row vector $\langle u|$. Also, it might be useful to note that terms that involve vectors for the same state, such as  $|u\rangle\langle u|$ or $|d\rangle\langle d|$ correspond to diagonal entries of a matrix.

The state $M$ is different from the state $|+\rangle$ and one simple way to show this is to compare matrices. Working it out, we get $|+\rangle\langle +| = \frac{1}{2} \left( |u \rangle \langle u| + |d \rangle \langle d| + |u \rangle \langle d| + |d \rangle \langle u| \right)$So we get cross-terms or off-diagonal entries for the matrix representing state $|+\rangle$ that we don't have with the state $M$.

Going back to the picture of qubit states in terms of a sphere, mixtures such as $M$ would be shown as arrow directed toward points in the interior of the sphere. The state $M$ itself is actually just be just a point, the center of the sphere. In fact, it is the unique state representing an equal mixture of any pair of orthogonal states, that is, oppositely directed points on the sphere. For example, we could have written $M = \frac{1}{2} \left( |+\rangle\langle +| + |-\rangle \langle -| \right)$.

This also tells us how we can differentiate between the states $M$ and $|+\rangle$. For any measurement we choose, $M$ will always give equal probabilities for the two states for that measurement. On the other hand, $|+\rangle$ will give different probabilities for different measurements, like for "$|u\rangle$ or  $|d\rangle$" we get probability 1/2 for either state but for "$|+\rangle$ or  $|-\rangle$" it will always come out $|+\rangle$.

The main lesson here is that quantum superpositions allow us to generate probabilities with qubits that would not be possible with bits, and this follows closely from the fact for a qubit, the set of all states form a ball (if mixtures are included) while for a random bit, we only have a number that tells you the probability of a zero (since if $\Pr[0] = x$, then $\Pr[1] = 1-x$).