Bits: From bits to vectors · Math of Quantum

In 1937 a 21-year-old MIT student, Claude Shannon, showed in his master's thesis that the relay circuits of telephone exchanges obey the algebra George Boole had invented in 1854 to formalize logic. Every computer since then manipulates bits, quantities that are either 0 or 1, with logic gates. To understand what is new about quantum computing we first have to look at the classical bit with different eyes: as a vector.

Boolean circuits

A gate takes bits and returns bits: $NOT (x) = 1 - x$ , $AND (x, y) = x y$ , $NAND (x, y) = 1 - x y$ . A circuit wires gates together, and computes a function $f : {0, 1}^{n} \to {0, 1}^{m}$ . A single type of gate is enough to build all of them.

Theorem (universality of NAND)

Every Boolean function $f : {0, 1}^{n} \to {0, 1}$ can be computed by a circuit made only of NAND gates.

Proof

Write $f$ in disjunctive normal form: an OR, over the inputs $a$ with $f (a) = 1$ , of the AND of literals $x_{i}$ or $\neg x_{i}$ that is true only at $a$ . So NOT, AND and OR suffice. And each of them is made of NANDs: $\neg x = NAND (x, x)$ , $x \land y = \neg NAND (x, y)$ , $x \lor y = NAND (\neg x, \neg y)$ (De Morgan).

The proof hides a warning that will matter later: the normal form can have exponentially many terms. Being able to compute a function says nothing about computing it efficiently. Whether quantum computers can compute efficiently what classical ones cannot is the question running through this whole site.

Information is physical

An AND gate destroys information: from the output 0 you cannot tell whether the input was 00, 01 or 10. In 1961 Rolf Landauer, at IBM, showed that this has an unavoidable physical price.

Principle (Landauer, 1961)

Erasing one bit of information in an environment at temperature $T$ dissipates at least

E \geq k_{B} T \ln 2

of heat, where $k_{B}$ is Boltzmann's constant (about $3 \times 10^{- 21}$ joules at room temperature).

In 1973 Charles Bennett showed that this cost is not inevitable: every computation can be done reversibly, without erasing anything, by keeping enough extra bits and “uncomputing” the intermediate results at the end. In 1980 Tommaso Toffoli found the gate that makes it practical.

Theorem (reversible universality; Toffoli, 1980)

The Toffoli gate $T (a, b, c) = (a, b, c \oplus a b)$ is reversible (it is its own inverse) and, with auxiliary bits fixed to 0 or 1, every Boolean function can be computed by a circuit of Toffoli gates.

Proof

Applying $T$ twice gives $c \oplus a b \oplus a b = c$ , so $T$ is its own inverse. With $c = 1$ the third output is $1 \oplus a b = NAND (a, b)$ , and with $b = 1, c = 0$ it copies $a$ (fan-out). By the universality of NAND, every circuit can be simulated.

This detail is crucial: as we will see, the evolution of a quantum system is always reversible. Toffoli's theorem guarantees that a quantum computer can do at least everything a classical one does.

Bits as vectors

Now the change of perspective. Represent the bit 0 by the vector $| 0 ⟩ = (\binom{1}{0})$ and the bit 1 by $| 1 ⟩ = (\binom{0}{1})$ (the notation $| \cdot ⟩$ , due to Dirac, will reappear constantly). Then NOT is a matrix:

X = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), X | 0 ⟩ = | 1 ⟩, X | 1 ⟩ = | 0 ⟩ .

With $n$ bits there are $2^{n}$ possible configurations, and each one is a basis vector of a space of dimension $2^{n}$ . A deterministic reversible circuit is a permutation matrix that shuffles those basis vectors. It sounds like an extravagant way of describing something simple, until we add randomness.

Probabilistic bits

A coin in the air is a bit we do not know. We describe it with a probability vector $𝐩 = (p_{0}, p_{1})$ , with $p_{i} \geq 0$ and $p_{0} + p_{1} = 1$ . In other words, a vector with non-negative entries and 1-norm equal to 1: $‖ 𝐩 ‖_{1} = | p_{0} | + | p_{1} | = 1$ . Random operations are matrices too.

Proposition (stochastic matrices)

A matrix $S$ maps every probability vector to a probability vector if and only if it is stochastic: non-negative entries and each column summing to 1.

Proof

Applying $S$ to the basis vector $𝐞_{j}$ gives column $j$ , which must be a probability vector. Conversely, $S 𝐩$ is a convex combination of the columns, which are probability vectors, and the set of probability vectors is convex.

A stochastic matrix can only mix: it takes points of the segment $p_{0} + p_{1} = 1$ towards its interior and, unless it is a permutation, cannot be undone without losing the guarantee of non-negativity. Uncertainty grows; it never shrinks. Is there something smoother, which allows us to go from 0 to 1 continuously and reversibly? Here is the first surprise.

Proposition (NOT has no stochastic square root)

There is no stochastic $2 \times 2$ matrix $S$ such that $S^{2} = X$ .

Proof

Write $S = (\begin{matrix} a & b \\ 1 - a & 1 - b \end{matrix})$ with $a, b \in [0, 1]$ . The top-left entry of $S^{2}$ is $a^{2} + b (1 - a)$ , which must be 0. Both terms are non-negative, so $a = 0$ and $b = 0$ . But then $S = (\begin{matrix} 0 & 0 \\ 1 & 1 \end{matrix})$ and $S^{2} = S \neq X$ .

With the 2-norm the story is different. If instead of probabilities we use vectors $(α, β)$ with $α^{2} + β^{2} = 1$ , a 45° rotation applied twice is a 90° rotation, which takes $| 0 ⟩$ to $| 1 ⟩$ . This is not an accident: of all the ways of measuring length, only one allows continuous reversible transformations.

Theorem (isometries of

ℓ_{p}

)

Let $n \geq 2$ and $p \geq 1$ with $p \neq 2$ . Every linear map $A : ℝ^{n} \to ℝ^{n}$ that preserves the norm $‖ 𝐱 ‖_{p} = {(\sum_{i} | x_{i} |^{p})}^{1 / p}$ is a signed permutation matrix. For $p = 2$ , on the other hand, the isometries are all the orthogonal matrices (all the rotations and reflections), a continuous family.

The same slider, two worlds. Left: a probabilistic bit (1-norm) to which we apply a “partial flip” stochastic matrix twice. Right: a vector of 2-norm 1 to which we apply a rotation twice. At

t = 0.5

the classical bit ends at 50/50, and that information is lost forever; the vector ends exactly at

| 1 ⟩

: it is a square root of NOT. Dashed lines show the unit “circle” of each norm.

Quantum mechanics is, at its mathematical core, what you get by taking that step: describe the state of a bit by a vector of 2-norm 1, with entries that may be negative and even complex. Those entries are not probabilities but amplitudes, and the probabilities are their squared moduli. That is the qubit.

References

C. E. Shannon (1938). “A Symbolic Analysis of Relay and Switching Circuits”. Transactions of the AIEE, 57(12).
R. Landauer (1961). “Irreversibility and Heat Generation in the Computing Process”. IBM Journal of Research and Development, 5(3).
C. H. Bennett (1973). “Logical Reversibility of Computation”. IBM Journal of Research and Development, 17(6).
T. Toffoli (1980). “Reversible Computing”. ICALP, LNCS 85.
S. Aaronson (2013). Quantum Computing Since Democritus. Cambridge University Press.

§Boolean circuits

§Information is physical

§Bits as vectors

§Probabilistic bits

§References

Boolean circuits

Information is physical

Bits as vectors

Probabilistic bits

References