Teapot supremacy

No, this is not another timely post about the British Royal family.

It’s about Richard Borcherds’ “teapot test” for quantum computers.



A lot of money is being thrown at the quantum computing hype, causing people to leave academia for quantum computing firms. A recent example (hitting the press even in Belgium) being the move of Bob Coecke from Oxford University to Cambridge Quantum Computing.

Sure, quantum computing is an enticing idea, and we have fantastic quantum algorithms such as Shor’s factorisation algorithm and Grover’s search algorithm.

The (engineering) problem is building quantum computers with a large enough number of qubits, which is very difficult due to quantum decoherence. To an outsider it may appear that the number of qubits in a working quantum computer is growing at best linearly, if not logarithmic, in sharp contrast to Moore’s law for classical computers, stating that the number of transistors in an integrated circuit doubles every two years.

Quantum computing evangelists assure us that this is nonsense, and that we should replace Moore’s law by Neven’s law claiming that the computing power of quantum computers will grow not just exponentially, but doubly exponentially!

What is behind these exaggerated claims?

In 2015 the NSA released a policy statement on the need for post-quantum cryptography. In the paper “A riddle wrapped in an enigma”, Neil Koblitz and Alfred Menezes carefully examined NSA’s possible strategies behind this assertion.

Can the NSA break PQC? Can the NSA break RSA? Does the NSA believes that RSA-3072 is much more quantum-resistant than ECC-256 and even ECC-384?, and so on.

Perhaps the most plausible of all explanations is this one : the NSA is using a diversion strategy aimed at Russia and China.

Suppose that the NSA believes that, although a large-scale quantum computer might eventually be built, it will be hugely expensive. From a cost standpoint it will be less analogous to Alan Turing’s bombe than to the Manhattan Project or the Apollo program, and it will be within the capabilities of only a small number of nation-states and huge corporations.

Suppose also that, in thinking about the somewhat adversarial relationship that still exists between the U.S. and both China and Russia, especially in the area of cybersecurity, the NSA asked itself “How did we win the Cold War? The main strategy was to goad the Soviet Union into an arms race that it could not afford, essentially bankrupting it. Their GNP was so much less than ours, what was a minor set-back for our economy was a major disaster for theirs. It was a great strategy. Let’s try it again.”

This brings us to the claim of quantum supremacy, that is, demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time.

In 2019, Google claimed “to have reached quantum supremacy with an array of 54 qubits out of which 53 were functional, which were used to perform a series of operations in 200 seconds that would take a supercomputer about 10,000 years to complete”. In December 2020, a group based in USTC reached quantum supremacy by implementing a type of Boson sampling on 76 photons with their photonic quantum computer. They stated that to generate the number of samples the quantum computer generates in 20 seconds, a classical supercomputer would require 600 million years of computation.

Richard Borcherds rants against the type of problems used to claim quantum ‘supremacy’. He proposes the ‘teapot problem’ which a teapot can solve instantaneously, but will be impossibly hard for classical (and even quantum) computers. That is, any teapot achieves ‘teapot supremacy’ over classical and quantum computers!

Another point of contention are the ‘real-life applications’ quantum computers are said to be used for. Probably he is referring to Volkswagen’s plan for traffic optimization with a D-Wave quantum computer in Lisbon.

“You could give these guys a time machine and all they’d use it for was going back to watch some episodes of some soap opera they missed”

Enjoy!

We sit in our ivory towers and think

I’m on vacation, and re-reading two ‘metabiographies’:

Philippe Douroux : Alexandre Grothendieck : Sur les traces du dernier génie des mathématiques

and

Siobhan Roberts : Genius At Play: The Curious Mind of John Horton Conway



.

Siobhan Roberts’ book is absolutely brilliant! I’m reading it for the n-th time, first on Kindle, then hardcopy, and now I’m just flicking through its pages, whenever I want to put a smile on my face.

So, here’s today’s gem of a Conway quote (on page 150):

Pure mathematicians usually don’t found companies and deal with the world in an aggressive way. We sit in our ivory towers and think.

(Conway complains his words were taken out of context, in an article
featuring Stephen Wolfram.)

If only university administrations worldwide would accept the ‘sitting in an ivory tower and think’-bit as the job description, and evaluation criterium, for their pure mathematicians.

Sadly… they prefer managers to thinkers.

This reminds me of another brilliant text, perhaps not receiving the attention it deserves:

Daniel J. Woodhouse : An open letter to the mathematical community.

Woodhouse offers a reaction to the ‘neoliberal upper management and bloated administration’ of universities:

Within the sphere of pure mathematics — the oldest and most successful of humanity’s intellectual endeavors — I believe our best chance at preserving the integrity and dignity of our tradition is to return to our Pythagorean roots. We should become a cult.

How?

Let us seclude ourselves in mountain caves and daub mysterious equations in blood across rock-faces to ward off outsiders. Let us embrace our most impenetrable mathematical texts as sacred and requiring divinely distributed revelation.

Why?

I am convinced that the current system has dulled our understanding of the value we offer through our instruction. Modern mathematical techniques are the foundation of modern science, medicine, and technology, and we should be the literal, rather than metaphorical, high priests of this temple. Only by withholding our insights will we be able to reassert the intrinsic worth of our knowledge.

I hope these few paragraphs have wetted your appetite to read the manifesto in full, and then take action!

in praise of libraries

I’m back in Antwerp for over a week now, and finally got hold of our copy of Shimura’s “Introduction to the arithmetic theory of automorphic functions”.

The sad story of disappearing libraries at our university, and possibly elsewhere (everywhere?).

Over 20 years ago our maths department shared a building with the language departments, as well as a library.

The ground floor was taken up by languages, science books were in the cellar. There were years I spend more time on the ground floor than in the maths section.

I must have read most of the Dutch novels published between 1980 and 2000. For some time I could even pass as a Joyce-scholar, at least to those interested in a tiny part of Finnegans Wake.

All that changed when they united the three different branches of Antwerp university and we had to move to another campus.

We were separated from the language departments (they moved to the center of town) and, sadly, also from their library.

On the positive side, we moved to a nice building with a gorgeous library. And, an added bonus, it was on the same floor as my office. To kill an hour it was fun to stroll over to the library and spend some time between books and journals.

Then, some years ago, they closed down the maths-library and moved a tiny fraction of it to the science-library (located at a different campus).

Administration argued that too few people visited the library to keep it open.

But more important, they needed the space to create what they call a ‘study landscape’: a lounge where students can hang out, having enough power outlets for all their computers and smartphones.

So, the maths-library had to go for a place where, during term, students can recharge their phones, and during examination periods like now, students can sit together to study.

It seems that millennials need to have visual confirmation that their fellow students are also offline.

Today even the science-library is transformed into such a study-landscape, and only a handful of math-books remain on the shelves (well-hidden behind another door).

For the few odd ones, like me, who still want to browse through a book occasionally, you have to request for it online.

A few days later you get an email saying that your request is granted (they make it sound as if this is a huge favour), and then they need some more days to get the book from the storehouse and deliver it (sometimes randomly) to one of the few remaining university libraries, sorry, study landscapes…

Smullyan and the President’s sanity

Smullyan found himself in a very strange country indeed!

All the inhabitants of this country are completely truthful – they always tell you honestly what they believe, but the trouble is that about half of the population are totally mad, and all their beliefs are wrong!

The other half are totally sane and accurate in their judgments, all their beliefs are correct.

Smullyan felt honoured to be invited by the Presidential couple.

The President was the only one who said anything, and what he said was:

“My wife once said that I believe that she believes I am mad.”

What can be deduced about the President’s sanity, and that of his wife?

Reference: This is a minor adaptation of Problem 4.5 in Raymond Smullyan‘s book Logical Labyrinths.

Brancusi’s advice : avoid vampires

My one and only resolution for 2018: ban vampires from my life!

Here’s the story.

In the 1920’s, Montparnasse was at the heart of the intellectual and artistic life in Paris because studios and cafés were inexpensive.

Artists including Picasso, Matisse, Zadkine, Modigliani, Dali, Chagall, Miro, and the Romanian sculptor Constantin Brancusi all lived there.

You’ll find many photographs of Picasso in the company of others (here center, with Modigliani and Salmon), but … not with Brancusi.

From A Life of Picasso: The Triumphant Years, 1917-1932 (Vol 3) by John Richardson:

“Brancusi disapproved of one of of Picasso’s fundamental characteristics—one that was all too familiar to the latter’s fellow artists and friends—his habit of making off not so much with their ideas as with their energy. “Picasso is a cannibal,” Brancusi said. He had a point. After a pleasurable day in Picasso’s company, those present were apt to end up suffering from collective nervous exhaustion. Picasso had made off with their energy and would go off to his studio and spend all night living off it. Brancusi hailed from vampire country and knew about such things, and he was not going to have his energy or the fruits of his energy appropriated by Picasso.”

I learned this story via Austin Kleon who made this video about it:


Show Your Work! Episode 1: Vampires from Austin Kleon on Vimeo.