But Quantum!

What can quantum computing 𝘳𝘦𝘢𝘭𝘭𝘺 achieve?

At last [Ptaclusp] IIa said, ‘What does “quantum” mean anyway?’
IIb shrugged. ‘It means add another nought,’ he said.     
‘Oh,’ said IIa, ‘is that all?’               
        — Terry Pratchett, Pyramids

Faithful readers will know that I really, really, really like the writing of Terry Pratchett. I firmly believe that he was given less credit than was his due, simply because he infused his writing with humour. I still cherish the stories of how writers of ‘serious literature’ glowered over their sparsely-attended book signings, while Pterry’s fans queued around the block.

Nobody—and I mean nobody, not even current US politicians—deserves piss-taking more than the vast majority of people who use the word ‘quantum’ in apparently serious conversation, especially if they are ‘popular scientists’. So let’s have a gander at some fairly recent ‘quantum claims’. We’ll find out that most are absurd. Needless to say, this post will be liberally sprinkled with Pratchettisms.

Physicists create a wormhole!!!!!

“Five exclamation marks, the sure sign of an insane mind.” ― Terry Pratchett, Reaper Man

A few years ago, the news media were full of headlines like that shown above. The paper was titled Traversable wormhole dynamics on a quantum processor. The quotes went ballistic:

“It looks like a duck, it walks like a duck, it quacks like a duck. So that’s what we can say at this point - that we have something that in terms of the properties we look at, it looks like a wormhole,” Lykken said.

Here’s Reuters:

It was a “baby wormhole,” according to Caltech physicist Maria Spiropulu.

The good news is that you too can duplicate their experiment at home, today (!!!!!) And you don’t even need physical materials. After some failed attempts using Ideogram,¹ I faithfully replicated their experiment using nothing more than Google Nanobanana, producing an identical copy of their experiment—shown at the start of this post.

Yep. They didn’t make an actual wormhole. They effectively drew a crappy picture of a wormhole, and made outrageous claims instead. Surprisingly, the original paper was published in the prestigious journal Nature. Naturally, they obscured their actions using scientific near-gibberish. Read the paper if you don’t believe me. Here’s an evaluation by Peter Woit, who actually understands the maths and the physics involved:

The claim that “Physicists Create a Wormhole” is just complete bullshit, with the huge campaign to mislead the public about this a disgrace, highly unhelpful for the credibility of physics research in particular and science in general.

Shame on Joe Lykken and Maria Spiropulu. But that was just a warm-up.

Spin

Granny Weatherwax wouldn’t know what a pattern of quantum inevitability was if she found it eating her dinner. If you mentioned the words ‘paradigm of space-time’ to her she’d just say ‘What?’ But that didn’t mean she was ignorant. It just meant that she didn’t have truck with words, especially gibberish. — Terry Pratchett, Witches Abroad.

Some background is needed for our next outrageous display. Quite a bit of background. Some of it, quantum. Ready? Qubits are the quantum analogue of a bit (binary digit, 0 or 1) in traditional computing.

The second concept here is ‘quantum superiority’ aka ‘quantum advantage’. Let’s take an example. Some commonly used security is based on how difficult it is to factor large semiprimes. A semiprime is two prime numbers multiplied together. Fortunately for cryptographers, it’s bloody difficult to get out those two primes, once you’ve done the multiplication. So knowledge of two, large, secret primes can be used for public key cryptography.

Bloody difficult, that is, unless we can implement Shor’s algorithm, which allows us to shovel that big semiprime into a quantum computer, and almost instantaneously get out the original primes! The best conventional computer would take pretty much forever on the same task. Quantum superiority. The catch, of course, is that the best we’ve done so far with quantum computers is to factorise 15. There’s a lot of noise, and you need lots of qubits. Now for our next concept …

A spin glass is to a magnet what a piece of glass is to a crystal. In a magnet, all of the tiny little magnetic domains are lined up neatly. The spin glass is made up of misaligned components. It’s difficult to work out how to set these up so that you have a lowest energy configuration (LEC). You can’t just set everything in line and say “Done” because of the higgledy-piggledy internal properties.

Spin glasses are real materials, but the LEC of a spin glass is a traditionally hard computational problem. Ernst Ising solved it for his PhD in 1924, but this was in one dimension.

Ninety-nine years later, D-Wave computing published an article (in Nature, again, Bob!!!!) Here’s what they said:

We extract critical exponents that clearly distinguish quantum annealing from the slower stochastic dynamics of analogous Monte Carlo algorithms, providing both theoretical and experimental support for large-scale quantum simulation and a scaling advantage in energy optimization.

Again, the headlines went crazy. Again, not so fast! They solved the problem millions of times faster than a classical computer would, but there are some issues. The main one is that this has no relevance in the real world. There are some fiddly little details.

Remember Shor’s algorithm above? It turns out that if your fancy quantum machine can use ‘4-spin operators’, then you can factor a large semiprime like RSA-230 using just 4893 perfect qubits.² If, like the D-wave machine you only have ‘2-spin’, you need 148,776 qubits! D-wave set up an artificial problem. Their machine is a real-world cripple.

Echoes

‘It’s very hard to talk quantum using a language originally designed to tell other monkeys where the ripe fruit is.’ —Terry Pratchett, Night Watch

And just last year, Google announced—wait for it—quantum advantage. Again, no … wait … for the first time, ‘verifiably’³ they have claimed quantum advantage, “running 13,000 [times] faster than the best classical supercomputer.”⁴ You’ll never guess where this was published. Yep. Nature. They also simulate a toluene molecule.

There are a few teensy little problems with their claims. The first is that they made similar claims in 2019, but that claim was rapidly supplanted by classical algorithms that can perform as fast. James Whitfield from Dartmouth College is skeptical that they’re suddenly going to solve an actual, economically viable problem. Dries Sels from NYU points out there’s potential for a new, better, classical algorithm to supplant their efforts once more.

But there’s a more basic problem here that people seem to be assiduously ignoring. One that cuts at the very base of the funding of a lot of quantum programs.

Undercut

Greebo had spent an irritating two minutes in that box. Technically, a cat locked in a box may be alive or it may be dead. You never know until you look. In fact, the mere act of opening the box will determine the state of the cat, although in this case there were three determinate states the cat could be in: these being Alive, Dead, and Bloody Furious.          
    — Terry Pratchett, Lords & Ladies.

Here’s the problem. In 2023, Torsten Hoefler, Thomas Häner, and Matthias Troyer (all experts in the field, recruited by Microsoft) published an article in the Communications of the ACM that teases out the hope from the hype. It’s sobering.

They’re actually rather generous. Even assuming a quantum computer with 10,000 error-corrected qubits and lots of other features we haven’t yet achieved, there are fundamental problems:

1. Input and output (I/O) will be crippling. For example, if you want your quantum machine to interrogate a large database, this will be four orders of magnitude slower than with a traditional computer. You can’t get your data in fast enough!

2. Traditional algorithms will always be faster unless they need to run for weeks or more. This is illustrated in their Figure 1, reproduced above.

Practically, this cuts down the field of relevance to “big compute problems on small amounts of data”. But things are even more constrained. Generally, quantum calculations provide ‘quadratic’ or O(n²) speedup.^⌘ This means that that crossover time is several months! Speedup from quantum computing needs to be O(n³), O(n⁴) or better.

Unfortunately, there don’t seem to be many such tasks, apart from cryptanalysis using Shor’s algorithm, and some fairly specific simulations in chemistry, materials science and quantum physics itself. Pretty much everything else will also run into those I/O issues.

Hoefler and colleagues identify a large number of dead ends. As they put it:

A large range of problem areas with quadratic quantum speedups, such as many current machine learning training approaches, accelerating drug design and protein folding with Grover’s algorithm, speeding up Monte Carlo simulations through quantum walks, as well as more traditional scientific computing simulations including the solution of many non-linear systems of equations, such as fluid dynamics in the turbulent regime, weather, and climate simulations will not achieve quantum advantage with current quantum algorithms in the foreseeable future.

We also conclude that the identified I/O limits constrain the performance of quantum computing for big data problems, unstructured linear systems, and database search based on Grover’s algorithm such that a speedup is unlikely in those cases. Furthermore, Aaronson et al. show that the achievable quantum speedup of unstructured black-box algorithms is limited to O(𝑁⁴). This implies that any algorithm achieving higher speedup must exploit structure in the problem it solves. [my emphasis]

Point the next quantum enthusiast you meet to this refreshing piece of real thinking.

My 2c, Dr Jo.

^{⌘ This symbol is used to indicate posts where I’ve discussed the flagged topic in more detail.}

1. The prompt was:

A photograph of a hand holding a piece of paper that has been folded over so the edges more or less meet up. There is *no* crease at the fold. A standard HB pencil with red and black longitudinal stripes has been thrust through both layers of the paper, and is still present in the resulting hole, inserted about half-way through. Studio lighting.

Nanobanana required some serious extra prompting to get this right. Five times.

2. The answer is 4528450358010492026612439739120166758911246047493700040073956759261590397250
033699357694507193523000343088601688589
× 3968132623150957588532394439049887341769533966621957829426966084093049516953
598120833228447171744337427374763106901

3. Not actually verified. Just verifiable if you have your own state-of-the art quantum computer, cooled to minutely close to absolute zero.

4. No, they didn’t actually use a supercomputer. They just simulated using a supercomputer to check their work.