Mathematicians Create Algorithm So Complex No Computer Can Use It...Yet

Quantum computers, which would rely on quantum mechanical concepts like superposition and entanglement to perform operations of unimaginable complexity, remain a pipe dream. But physicists have nevertheless come up with an algorithm that only quantum computers could use.

The newest algorithm, developed by Aram W. Harrow of the University of Bristol in England and Avinatan Hassidim and Seth Lloyd of MIT, tackles linear equations, which is something many students run across in high school or college. An example of such an expression is 3x + 4y = 12, with the variables and the constants on each side of the equation. Although it's relatively easy to solve an expression with only two unknown values, it is another matter entirely to solve systems with billions of unknown values.

Such scenarios are hardly unusual; weather scenarios frequently involve just that many variables and equations. These so-called "N by N" systems, which have N linear equations and N unknown values, can be solved relatively easy with current algorithms, but time is a factor. Say it takes a computer one second to solve one linear equation. If the system has a billion variables, then it will take a billion seconds to figure out every value. That's almost 32 years.

Harrow, Hassidim, and Lloyd's algorithm cuts down on time dramatically by using quantum superpositions. In classical, binary computing, each bit of data can exist either as a 0 or 1. Quantum bits, or qubits, can be 0, 1, or both values at the same time. In turn, two qubits can be two 0's, two 1's, a 0 and a 1, or any superposition of these combinations. That may be a bit difficult to fully grasp - I'll freely admit it makes my head hurt - but the upshot is that the possible combinations of qubits increases exponentially, allowing for huge increases in computing efficiency.

In the case of this particular algorithm, the amount of time it takes to solve "N by N" systems is linked not to the value of N but to the number of digits in N. That means, if we returned to the previous example, it would take just nine seconds to solve that system rather than a billion. (This is because 1,000,000,000 has nine more digits than 1.) Obviously, this all remains theoretical, but it's just a question of waiting for the computer science to catch up to the mathematics.

Meanwhile, in other math news, a French computer scientist has calculated pi to a record 2.7 trillion digits, smashing the old record of 2.6 trillion. One can only imagine what unimaginable feats of pi calculation of which quantum computers might be capable. 2.8 trillion? Perhaps even 2.9 trillion? Who knows, or dares to dream...?

[Scientific American]