Author Archives: apgoucher

4-input 2-output Boolean circuits

In 2005, Donald Knuth determined the minimum cost required to implement each of the 2^32 different 5-input 1-output Boolean functions as a circuit composed entirely of: 2-input gates (there are 16 of these), each of which has cost 1; 1-input … Continue reading

Posted in Boolean optimisation | 2 Comments

That group of order 348364800

In nested lattices, we talked about the E8 lattice and its order-696729600 group of origin-preserving symmetries. In minimalistic quantum computation, we saw that this group of 8-by-8 real orthogonal matrices is generated by a set of matrices which are easily … Continue reading

Posted in Uncategorized | 3 Comments

More quantum gates and lattices

The previous post ended with unanswered questions about describing the Conway group, Co0, in terms of quantum gates with dyadic rational coefficients. It turned out to be easier than expected, although the construction is much more complicated than the counterpart … Continue reading

Posted in Uncategorized | 1 Comment

Minimalistic quantum computation

In the usual ‘circuit model’ of quantum computation, we have a fixed number of qubits, {q1, q2, …, qn}, and allow quantum gates to act on these qubits. The diagram below shows a Toffoli gate on the left, and an … Continue reading

Posted in Uncategorized | 10 Comments

Nested lattices

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 … Continue reading

Posted in Uncategorized | 3 Comments

Self-replicator caught on video

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 … Continue reading

Posted in Uncategorized | 10 Comments

Five-input Boolean circuits

Over the past few weeks, I’ve been investigating Boolean optimisation. That is to say, given some circuit of logic gates that implements a particular n-input m-output function, find a more efficient circuit that implements the same function. In practical applications, … Continue reading

Posted in Boolean optimisation | 3 Comments

(W^2 + X^2) / (W^2 + X^2 + Y^2 + Z^2)

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 … Continue reading

Posted in Uncategorized | 2 Comments

Complexity of integer multiplication almost solved

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, … Continue reading

Posted in Uncategorized | Leave a comment

Fully self-directed replication

A new form of artificial life has been born — and there are no doubts that it directs its own self-replication: So, what exactly is happening? At 0:06, the organism begins to sequentially construct four identical copies of itself. At … Continue reading

Posted in Uncategorized | 17 Comments