Usually I restrict myself to physics on this blog.  Not because I don’t love and adore pure math, but mostly because news from this field leaves most readers in about the same state as captured in this comic.

Take the recent proof of the ABC conjecture, for instance.  By all accounts, Shinichi Mochizuki,  the mathematician who came up with it, is brilliant.  Unfortunately, that means that even experts close to his field have a  hard time following and validating the proof that spans several arcane areas and four pre-print papers.

But I make an exception for the recent news about a new way to solve linear equations (proposed by Prasad Raghavendra). Everybody learned in school how to solve via Gauss elimination, which might be the most ubiquitous math skill after simple arithmetic.  There have been some algorithms developed to improve on this method, but it is still extremely cool that there is a new algorithm for such a fundamental mathematical problem with such widespread applications.

And because this concerns an algorithm, there is even pseudo and real code to play with.

What is especially interesting about this new method is that it employs randomness (a resource that has been shown many times to allow for more efficient algorithms).  But there is a catch:  This approach is only applicable for linear equation systems over finite fields (so applying this to QC simulation won’t work).  Fields are defined as Rings (i.e. commutative groups that have a two binary operations such as addition and multiplication).

This finite field constraint seems again to push this onto a more esoteric plane, but fortunately these structured sets are anything but.  This becomes clear when looking at the simplest finite field that just consists of two members 0 and 1:  Just add the logical operations AND and XOR – et voila – if you’ve been exposed to bit-wise coding you’re intimately familiar with the smallest finite field GF(2). GF stands for Galois Field, another name for the same thing.  (The number denotes how many elements the field has i.e. its cardinality).

It shouldn’t come as a surprise that finite fields find application in coding theory and cryptography. There are also two connections to the main topic of this blog: The obvious one is that any randomized algorithm can benefit from the precursors of all Quantum Information devices i.e. quantum noise generators (you can buy one here, but if you need true randomness and cannot afford one of these, then this service might be for you).

The second connection is more subtle and interesting.  Just as for any other calculation device, large universal gate based quantum computers can only become feasible if there are robust error correction mechanisms in place to deal with inevitable random noise. One of the earliest quantum error correction schemes was published by the veritable Peter Shor.  Turns out the basis for “stabilizer codes” that fix the error for a single qbit are again the Pauli operators, which in turn map to GF(4).  This can be generalized to GF(q) for non-binary systems. So it seems this new algorithm could very well find application in this area. A somewhat ironic twist if a randomized algorithm should turn out to be an efficient tool to deploy in correcting random qbit errors.