Something intriguing happened last week. A paper about quantum computing by a Google researcher making a startling claim appeared on a Nasa website – and then disappeared shortly afterwards. Conspiracy theorists immediately suspected that something sinister involving the National Security Agency was afoot. Spiritualists thought that it confirmed what they’ve always suspected about quantum phenomena. (It was, as one wag put it to me, a clear case of “Schrödinger’s Paper”.) Adherents of the cock-up theory of history (this columnist included) concluded that someone had just pushed the “publish” button prematurely, a suspicion apparently confirmed later by stories that the paper was intended for a major scientific journal before being published on the web.
Why was the elusive paper’s claim startling? It was because – according to the Financial Times – it asserted that a quantum computer built by Google could perform a calculation “in three minutes and 20 seconds that would take today’s most advanced classical computer … approximately 10,000 years”. As someone once said of the book of Genesis, this would be “important if true”. A more mischievous thought was: how would the researchers check that the quantum machine’s calculation was correct?
A quantum computer is one that harnesses phenomena from quantum physics, the study of the behaviour of subatomic particles, which is one of the most arcane specialisms known to humankind. We all inhabit – and intuitively understand – a world governed by Newtonian physics – which explains the behaviour of tangible things such as billiard balls, planets and falling apples. But it turns out that Newton’s laws don’t apply to subatomic particles; quantum theory evolved to explain what goes on in that strange space. The polite term for what goes on there is “counter-intuitive”. The less polite term is “weird”. In certain situations, for example, quantum theory says that one subatomic particle’s behaviour is bound up with that of another, even if the second one is on the other side of the galaxy. This is known as “entanglement”. Another principle is that a particle can be in two different states at the same time – as with Schrödinger’s imaginary cat, who was both alive and dead at the same time. This is known in the jargon as “superposition”.
Superposition is at the heart of quantum computing. Ordinary computers work with bits that can be either on or off – coded as zero or one. But quantum computers work with qubits, which can have a value of 0, 1 or both! Thus two qubits can represent four states simultaneously (00, 01, 10, 11) – which apparently means that 100 qubits can represent 1.3 quadrillion quadrillion states. This means that a quantum computer would be much faster and efficient at some kinds of computation than would be a classic computer, which has to chunter along with bits that are only on or off – and it explains why the mysterious Google machine might represent a working model of “quantum supremacy” in action.
Why might this be important? Because the security of our networked world depends on public-key cryptography – the encryption that protects communications, bank accounts and other sensitive data. At the core of this approach is the fact that factoring very large numbers takes a long time. In 2016, for example, it took several hundred computers two years to crack a message encrypted with a key that was 768 bits long. The same process for material encrypted with a 1,024-bit key would take 1,000 times longer, and cracking anything encrypted with the current highest standard 4,096-bit key would possibly outlast the presence of life on earth. So our security depends on the speed of computers.
In principle, industrial-scale quantum computers could make a mockery of all this – but that’s in theory. In practice, quantum supremacy is still a long way off, as Scott Aaronson, a leading academic in the field, points out in a post on his blog. There are, he says, two big obstacles. The first is that a quantum machine capable of tackling current encryption methods would need several thousand logical qubits: “With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today. I don’t think anyone is close to that, and we have no idea how long it will take”.
The second caveat is that quantum machines would be able to crack some codes but not all possible codes. The public-key codes that would be vulnerable happen to be the ones we use to secure online transactions and to protect data. But private-key encryption will probably still be invulnerable. And researchers have been working on new types of public-key crypto that no one knows how to break – even in principle – after two decades of trying.
When the Google paper does emerge, it will be interesting for all kinds of reasons – not least as evidence that the researchers have actually built a working 53-qubit machine. But as a harbinger of crypto-apocalypse it’s likely to be a disappointment. At best, it’ll be a proof of concept; at worst, it’ll be the canary in the crypto-mine.