Complex Projective 4-Space

In the usual ‘circuit model’ of quantum computation, we have a fixed number of qubits, {q₁, q₂, …, q_n}, and allow quantum gates to act on these qubits. The diagram below shows a Toffoli gate on the left, and an equivalent circuit of simpler gates on the right:

These diagrams represent qubits as horizontal lines (so there are 3 qubits in the circuit above), and the operations are applied from left to right. The circuit has 6 controlled-NOT gates (each acting on an ordered pair of qubits) and 9 single-qubit gates (4 T-gates, 3 inverse T-gates, and 2 Hadamard gates).

Whereas the internal state of a classical computer with n bits of memory can be described by a length-n vector of binary values, a quantum computer with n qubits of memory requires a length-(2^n) vector of complex numbers. A k-qubit gate is a unitary linear map described by a (2^k)-by-(2^k) matrix of complex numbers.

Importantly, it’s the exponential increase in the dimension of this vector (from n to 2^n), and not the involvement of complex numbers, which makes quantum computers [believed to be] able to solve more problems [in polynomial time] than is possible with a mere classical computer. To see this is the case, note that a (2^k)-by-(2^k) matrix of complex numbers can be emulated by a (2^(k+1))-by-(2^(k+1)) matrix of real numbers. Specifically, replace each complex entry with a real 2-by-2 block:

Consequently, a k-qubit complex gate can be emulated with a (k+1)-qubit real gate.

Indeed, it’s possible to restrict to not only real entries, but even to dyadic rational entries. Specifically, the most common universal set of logic gates {T, H, CNOT} consists of matrices whose entries belong to the ring where ζ is a primitive eighth root of unity. A similar trick means we can work over the ring of dyadic rationals instead, at the cost of just two extra qubits:

This is helpful for simulation in software: all finite values representable as IEEE 754 floating point numbers are dyadic rationals, and a partial converse is true: all dyadic rationals with numerator and denominator less than some bound (2^53 for double-precision and 2^24 for single-precision) are representable as IEEE 754 floating point numbers.

A universal pair of 3-qubit dyadic rational gates

Consider the Toffoli gate (left) and a new gate that I’m going to call the ‘XHH’ gate (it’s simply a tensor product of a Pauli X-gate and two Hadamard gates, all acting on separate qubits):

In an n-qubit circuit, each of these gates yields n(n – 1)(n – 2)/2 different matrices depending on the choice of qubits on which it acts, so this set expands to n(n – 1)(n – 2) matrices in total. Then we have the following universality theorem:

When n >= 4, the group generated by these matrices is a dense subgroup of the complete rotation group SO(2^n).

This is the best that we could hope for: when tensored by (n – 3) copies of the 2-by-2 identity matrix, these gates yield orthogonal matrices of determinant 1. It means that any special orthogonal gate can be approximated arbitrarily closely (in a number of gates polylogarithmic in the required precision, by the Solovay-Kitaev theorem), which (together with the above discussion of emulating complex unitary gates with real orthogonal gates) yields universal quantum computation.

An eight-dimensional surprise

More interesting is what happens when n = 3: the gates do not form a dense subgroup of O(8) as we might expect from extrapolating this result downwards (and noting that the Toffoli matrix has determinant -1, so the matrices lie in O(8) instead of SO(8) when n = 3).

Rather, they form a finite group of order 696729600.

This number should be familiar from the last post, because it’s the order of the E8 Weyl group. Every entry of every matrix in this group is not only dyadic rational, but in fact an integer multiple of 1/4. Inter alia, this finite group contains the familiar single-qubit Pauli gates X and Z, as well as the two-qubit CNOT gate.

Orthogonal projection of the 8-dimensional E8 root system into its 2-dimensional Coxeter plane, drawn by J. G. Moxness. The symmetry group of this set of 240 points is the aforementioned E8 Weyl group of order 696729600.

Given a starting state where all qubits are off (so the vector is (1, 0, 0, 0, 0, 0, 0, 0)), by applying these two gates in various combinations it is possible to reach any of 2160 different vectors (specifically, rescaled copies of the 2160 vectors in the second shell of the E8 lattice). If we instead began with an equal superposition of the eight computational basis states, there would be 240 reachable vectors — the root lattice vectors illustrated in the picture above! Again, the numbers 240 and 2160 should be very familiar from the previous article.

(Vectors that are related by scalar multiplication are identified as the same quantum state, so antipodal pairs of vectors in the previous paragraph correspond to the same quantum state. Consequently, there are only 1080 distinct quantum states reachable from the all-off quantum state, or 120 distinct quantum states reachable from the )

Before I found the set {Toffoli, XHH}, I tried the deceptively similar pair {Toffoli, ZHH}. To my surprise, the program I used to compute the group generated by those elements had an order of 2903040 — significantly smaller than the 696729600-element group I had expected! This is the Weyl group of E7, and in this case we get the smaller subgroup because all six matrices fix the vector (1, 1, 1, -1, 1, -1, -1, -1) and therefore only act nontrivially on its seven-dimensional orthogonal complement. Fortunately, the set {Toffoli, XHH} does not have a fixed vector and generates the full Weyl group of E8.

Unanswered questions

The {Toffoli, ZHH} construction of the E7 Weyl group demonstrates that we can realise the origin-preserving isometry group of a 7-dimensional lattice, even though 7 is not a power of two. An even more beautiful and exceptional lattice than the E8 lattice is the 24-dimensional Leech lattice, whose origin-preserving symmetry group is the Conway group Co0. Is there an elegant set of matrices which generate a group isomorphic to Co0 and have a simple description in terms of quantum gates?

The first nonempty shell of the Leech lattice consists of 196560 points, as opposed to the 240 points in the first shell of the E8 lattice. David Madore has plotted some beautiful projections of this set — they’re as close as possible to being analogous to the Petrie projection of the E8 root system shown above, except inasmuch as Co0 is not a Coxeter group and therefore it’s unclear which plane (if any!) is analogous to the Coxeter plane.

1, 240, 2160, 6720, 17520, 30240, 60480, 82560, 140400, …

These terms count the number of points at distance from the origin in the E8 lattice, a highly symmetric arrangement of points which Maryna Viazovska recently (in 2016) proved is the densest way to pack spheres in 8-dimensional space.

Even more recently, Warren D. Smith noticed a rather exceptional numerical coincidence — the sum of the first three terms in this sequence is a perfect fourth power:

1 + 240 + 2160 = 2401 = 7^4

Is this merely a coincidence? To begin with, we’ll look at the E8 lattice through a different lens: as a subset not of , but of complex (alas, not projective) 4-space, . Specifically, recall the Eisenstein integers, the ring of complex numbers generated by a cube root of unity:

These points have been 3-coloured according to whether the Eisenstein integer is congruent (modulo ) to 0, +1, or −1. The E8 lattice is then concisely expressible as the set of points (w, x, y, z) where:

• each coordinate is an Eisenstein integer;
• the colours of the four coordinates form a codeword in the tetracode.

The tetracode is a 2-dimensional subspace of the 4-dimensional vector space . A point belongs to the tetracode if and only if w = y − x = z − y = x − z. Equivalently, the coordinates are of the form (d, a, a + d, a − d).

The real E8 lattice has a symmetry group of order 696729600; this complex E8 lattice has more structure (complex scalar multiplication) which reduces the symmetry group to order 155520. This extra structure is what we need to explain Warren’s coincidence.

Now that we have defined the E8 lattice as a complex 4-dimensional lattice, consider scalar multiplication by 3 + ω. Returning to an 8-dimensional real viewpoint, this linear map corresponds to composing a rotation by a scaling by sqrt(7), and therefore has a determinant of sqrt(7)^8 = 2401. The image of the E8 lattice under this map is a sublattice, geometrically similar to the original E8 lattice, and the Voronoi cells induced by this sublattice each consist of 2401 points from the original lattice (namely one central point, surrounded by an inner shell of 240 points and an outer shell of 2160 points).

Linear subspaces and positional number systems

If we sum the first three terms of the theta series of the E6 lattice, 1 + 72 + 270, we get exactly 7^3. And similarly for the D4 lattice, 1 + 24 + 24 = 7^2. For the A2 (hexagonal) lattice, we have 1 + 0 + 6 = 7^1. These correspond to taking 3-, 2-, and 1-dimensional (complex) linear subspaces of the Voronoi partition described above.

The latter is particularly easy to describe: every Eisenstein integer z can be uniquely expressed in the form (3 + ω)q + r, where q is an Eisenstein integer and r belongs to the set {0, 1, ω, ω², −1, −ω, −ω²} consisting of zero together with the sixth roots of unity. We can decompose q in the same manner, and continue recursively; this is tantamount to writing an Eisenstein integer in a positional number system with radix 3 + ω and the seven digits {0, 1, ω, ω², −1, −ω, −ω²}.

If we allow digits after the ‘decimal point’, we can express any complex number in this positional number system. The set of numbers which ’round to zero’ after discarding the digits after the decimal point form the Gosper island, a self-similar set with a fractal boundary:

There are two different principal cube roots of unity, and each one yields a different (albeit isomorphic) positional number system for complex numbers.

The Hurwitz integral quaternions form a scaled copy of the D4 lattice, and we similarly obtain a positional number system for the quaternions with radix 3 + ω and 49 different digits: the Hurwitz integral quaternions with squared norm at most 2. There are 8 principal cube-roots of unity, and each one determines a positional number system for quaternions. It’s worth commenting that this isn’t the only nice* number system for integral quaternions: radix-(2 + i) with 25 digits (the Hurwitz integers of norm at most 1) also works.

*where ‘nice’ is defined to mean that the digit set consists of all integers with norm <= r for some value of r.

Finally, the Cayley integer octonions form a scaled copy of the E8 lattice, and there are 56 principal cube-roots of unity. Any one of these results in a positional number system for the octonions (which is well-defined despite the non-associativity of the octonions, since any pair of octonions together generate an associative algebra) with radix 3 + ω and 2401 different digits: the integer octonions with squared norm at most 2. We’ll call this number system ‘Warrenary’ after its discoverer. Unlike in the real, complex, and quaternionic cases, Warrenary is the unique positional number system for the octonions satisfying the aforementioned niceness property.

There is no analogue in six dimensions: normed division algebras only exist in dimensions 1, 2, 4, and 8, so there is no positional number system corresponding to the recursive nesting of E6 lattices.

Disappointingly, there appears not to be any similarly elegant lattice nestings for higher-dimensional lattices beyond D4, E6 and E8, such as the 24-dimensional Leech lattice (in particular, no early initial segment of the theta series yields a perfect 12th power as its sum). As such, the recursive nesting of E8 lattices is quite exceptional indeed.

Further reading

The integral quaternions and octonions have many other fascinating and elegant properties, including analogues of unique prime factorisation, which are explained in the book On Quaternions and Octonions by Derek Smith and the late, great John Conway (1937 — 2020).

Positional number systems for the real and complex numbers are described in the Seminumerical Algorithms volume of Donald Knuth’s The Art of Computer Programming.

In a previous article, an announcement was made of a complex self-replicating machine (known as the 0E0P metacell) in a simple 2-state cellular automaton. In the interim between then and now, Thomas Cabaret has prepared a most illuminating video* explaining the method with which the machine copies itself:

Note: the video is in French; recently, Dave Greene added an English translation of the subtitles.

* the video is part of Cabaret’s Passe-Science series. You may enjoy some of his other videos, including an explanation of the P vs NP problem and a reduction of Boolean satisfiability to the 3-colourability of planar graphs.

Anachronistic self-propagation

In related news, Michael Simkin recently created a wonderfully anachronistic self-propagator entitled Remini: it uses the same single-channel/slow-salvo construction mechanism as the 0E0P metacell, but it is built from oscillatory components instead of static ones. That is to say, it implements modern ideas using components available in the 1970s.

The project involved slmake together with a suite of additional tools developed by Simkin. There isn’t a video of this machine self-replicating, so you’d need to download a program such as Golly in order to watch it running.

Further reading

For further reading, I recommend (in order):

• The wiki entry (under construction) for the 0E0P metacell;
• An article unveiling various simpler examples of self-constructing circuitry;
• The slmake repository;
• A tutorial on effective use of slmake;
• A challenge thread proposing another contraption, that no-one has yet built. This would require the use of slmake followed by some ‘DNA-splicing’ to interleave the construction recipe with extra operations.

The Box-Müller transform is a method of transforming pairs of independent uniform distributions to pairs of independent standard Gaussians. Specifically, if U and V are independent uniform [0, 1], then define the following:

• ρ = sqrt(–2 log(U))
• θ = 2π V
• X = ρ cos(θ)
• Y = ρ sin(θ)

Then it follows that X and Y are independent standard Gaussian distributions. On a computer, where independent uniform distributions are easy to sample (using a pseudo-random number generator), this enables one to produce Gaussian samples.

As the joint probability density function of a pair of independent uniform distributions is shaped like a box, it is thus entirely reasonable to coin the term ‘Müller’ to refer to the shape of the joint probability density function of a pair of independent standard Gaussians.

What about the reverse direction?

It transpires that it’s even easier to manufacture a uniform distribution from a collection of independent standard Gaussian distributions. In particular, if W, X, Y, and Z are independent standard Gaussians, then we can produce a uniform distribution using a rational function:

The boring way to prove this is to note that this is the ratio of an exponential distribution over the sum of itself and another independent identically-distributed exponential distribution. But is there a deeper reason? Observing that the function is homogeneous of degree 0, it is equivalent to the following claim:

Take a random point on the unit sphere in 4-dimensional space (according to its Haar measure), and orthogonally project onto a 2-dimensional linear subspace. Then the squared length of the projection is uniformly distributed in the interval [0, 1].

This has a very natural interpretation in quantum theory (which seems to be a special case of a theorem by Bill Wootters, according to this article by Scott Aaronson arguing why quantum theory is more elegant over the complex numbers as opposed to the reals or quaternions):

Take a random qubit. The probability p of measuring zero in the computational basis is uniformly distributed in the interval [0, 1].

Discarding the irrelevant phase factor, qubits can be viewed as elements of S² rather than S³. (This quotient map is the Hopf fibration, whose discrete analogues we discussed earlier). Here’s a picture of the Bloch sphere, taken from my 2014 essay on quantum computation:

Bloch sphere and explanation thereof

Then, the observation reduces to the following result first proved by Archimedes:

Take a random point on the unit sphere (in 3-dimensional space). Its z-coordinate is uniformly distributed.

Equivalently, if you take any slice containing a sphere and its bounding cylinder, the areas of the curved surfaces agree precisely:

There are certainly more applications of Archimedes’ theorem on the 2-sphere, such as the problem mentioned at the beginning of Poncelet’s Porism: the Socratic Dialogue. But what about the statement involving the 3-sphere (i.e. the preimage of Archimedes’ theorem under the Hopf fibration), or the construction of a uniform distribution from four independent standard Gaussians?

Whilst not quite as close as the proofs of the ternary Goldbach conjecture and bounded gaps between primes, there has been a quick succession of two important and somewhat complementary breakthroughs on the computational complexity of integer multiplication:

• Afshani, Freksen, Kamma, and Larsen proved a lower bound of Ω(n log n) on the circuit complexity of integer multiplication, conditional on a conjecture in network coding.
• Harvey and van der Hoeven published an algorithm for large integer multiplication, establishing an unconditional upper bound of O(n log n). This is only marginally faster than the O(n log n log log n) Schönhage–Strassen algorithm, overtaking it only for unimaginably large numbers, but is of great theoretical interest because it coincides with the conjectural lower bound. (The authors also showed that the same complexity can be achieved by a multi-tape Turing machine.)

Essentially all modern integer multiplication algorithms are recursive in nature, and the computational complexity depends on the number of levels of recursion together with computational complexity of each level. To summarise:

In practice, it is common to mix-and-match these algorithms: using FFT-based algorithms (typically Schönhage–Strassen) near the root of the recursion, and switching to Toom-Cook at lower levels, before finally falling back on hardware multiplication at the leaves. This new Harvey–Hoeven algorithm is only suitable for really large integers, and switches to older algorithms (in the manner described) for numbers with fewer than 2^(1729^12) binary digits.

A refinement of the algorithm reduces that to 2^(9^12) = 2^282429536481 binary digits, but that is still much much larger than any number that could be practically stored, even storing one digit per atom in the observable universe.