Predicting Predictions For the 20s

Gödel’s Lost Letter and P=NP 2020-01-21

Before the reveal on January 22

Writer homepage source

Claire Cameron is the senior science editor at an online publication called Inverse. She has written an incomplete article titled, “The 2020s: 20 science and tech predictions for the new decade.” She has posted 12 of the predictions, but the top 8 will be revealed on Wednesday, January 22.

Today we offer a game of predicting: what will she predict? We also make some predictions for this year, including some that have already come true—the best kind.

Here are her 12 predictions. See if you can guess her other 8:

20. In the 2020s, human-level A.I. will arrive and finally pass the Turing test.
19. In the 2020s, tiny biosensors could make a 911 phone call from Mars.
18. Hyperloop, Elon Musk’s vacuum-sealed transit system, may get a speed boost.
17. In the 2020s, we will have a real Robot Olympics. (And it’ll be a lot cooler than the regular Olympics.)
16. A woeful prediction: Air pollution levels will remain constant in the ’20s.
15. Solar panels will continue to decline in price in the 2020s.
14. Humans return to the Moon.
13. Killer robots may roam the Earth. (That is, autonomous weapons will become reality.)
12. We’re gonna live a whole lot longer. (The linked description muses about 1,000-year lifespans beginning this decade.)
11. If you hope to see a self-driving car this decade, keep dreaming.
10. We’ll witness CRISPR gene-editing trials on humans.
9. We’ll be doing experiments on lab-grown brains.

There are already some clear big ones: yes to the Turing test and long lifespans and gene+brain editing but nix to self-driving cars. There may be some logical entailments, e.g., if 11 is false—so that self-driving cars are released—does that make 13 true?

None of these predictions is out-of-the-blue: they all connect to initiatives already underway. So there should be some basis for inferring the missing eight. Quantum computing is one obvious area. Reviewing last year’s predictions will bring us there.

Last Year’s Predictions

We made 5 perennial predictions and 5 new ones:

No circuit lower bound of ${1000n}$ or better will be proved for ${\mathrm{SAT}}$ . Check.
A “provably” secure crypto-system will be broken. No need to check—happens all the time.
At least five claims that ${\mathsf{P} = \mathsf{NP}}$ and five that ${\mathsf{P} \neq \mathsf{NP}}$ will be made. The ${\mathsf{P}}$ versus ${\mathsf{NP}}$ claims page has stopped being updated, but we can just count from comments on this blog.
A computer scientist will win a Nobel Prize. Again, not close—unless you count how vital lithium-ion batteries are to laptop computers. Two physicists won for discovering exoplanets in Earth-Sun type contexts, a question we retired last year.
A Clay problem will be solved, or at least notable progress made. A year ago we said this did not happen in 2018, but now for 2019 we’ll say yes based on a paper by Michael Griffin, Ken Ono, Larry Rolen, and Don Zagier (GORZ), which we covered here with progress on the Riemann Hypothesis.

The GORZ paper was #1 on this list of “The 10 Biggest Math Breakthroughs of 2019” by Popular Mechanics. We also covered the list’s #2, #3 (in one subsection), #4 (with a followup), and #10 items—not too bad.

The five non-perennial predictions from last year were:

Deep learning methods will be found able to solve integer factoring. This will place current cryptography is trouble. We had guessed a followup to this or this, but we do not see one from 2019.
Deep learning methods will be found to help prove that factoring is hard. See above. Instead, there was this (or see this).
The lines between heuristically solvable and really hard problems will become clearer—or more simply, SAT-solvers will hit a wall. Well hey, the best papers in the program for the SAT 2019 conference in Lisbon included this by Nikhil Vyas and Ryan Williams. It refutes a “super-strong ETH” statement for random ${k}$ -SAT instances with a fixed clause-to-variable ratio. So we guess a wall got broken thru instead.
An algorithm originating in a theoretical model will be enshrined in law. The Supreme Court cases on gerrymandering which we thought could do this instead nixed the algorithmic model—for now. Differential privacy was formally adopted for the 2020 Census, but apparently at the level of memoranda pursuant to the long-existing Title 13 rather than to new legislation.
Quantum supremacy will be proved—finally. This needs its own subsection to evaluate.

Quantum Supremacy

Last year, if we had written “claimed” or even “achieved,” we would now say bingo. But writing “proved” sets a higher standard. To judge from this and this, it appears the Google-led team is upping their qubit count from 53 to 57 in order to shore up their quantum supremacy claim.

However, we look back at what we called the “three planks” of a quantum supremacy claim:

Build a physical device capable of a nontrivial sampling task.
Prove that it gains advantage over known classical approaches.
Prove that comparable classical hardware cannot gain such advantage.

We don’t think IBM’s 2.5-day simulation that would run on the Summit supercomputer is “comparable hardware” enough to count as a “known classical approach.” So we claim part credit even with the “proved” wording based on plank 2 surviving IBM’s challenge and any other as far as we know. There is still our friend Gil Kalai’s now-detailed critique of the modeling that the Google team’s analysis leans on.

The level of plank 2 is what we meant a year ago anyway. See how we flip things in our last prediction below. Incidentally, in regard to the argument over the terms quantum “supremacy” and “advantage,” we stand by the different definitions toward the end of our predictions post a year ago.

Five Predictions for 2020

For our five predictions—besides the five perennial ones—we start with something easy:

The power of multiple quantum entangled provers will be resolved, with repercussions for other areas of mathematics.

This isn’t a total gimme: the proof could be wrong. The idea and connections, however, already seem clear.

Resolving the Sunflower Conjecture will run up against mainstream complexity theory issues.

This may be more a stretch. We note this new paper by Anup Rao simplifying some aspects of the proof of last year’s advance on the problem by Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Sunflower bounds are known to impact some complexity problems that seem more specialized, but neither paper mentions widening the contingencies. But talking about “mainstream” complexity:

A previously overlooked contingency involving two pairs of complexity classes will be found that can be taught in an intro theory course. We mean something like ${\mathsf{\#P = P \implies PSPACE = X}}$ , where of course we don’t know what ${\mathsf{X}}$ is.
The fourth-power upper bound given by Hao Huang’s proof of the Sensitivity Conjecture will be improved to ${bs(f) = o(s(f)^4)}$ but not to ${bs(f) = o(s(f)^{4-\delta})}$ for any fixed ${\delta > 0}$ .

We don’t have a concrete reason to think this, only the thought that if this were false in either direction then that might have been found already in the half-year since Huang’s paper. We note this survey from two weeks ago.

Now to get back to quantum. Instead of refining what we wrote a year ago, we do the opposite:

The statistical test underlying the quantum supremacy claim will not be tied to a mainstream complexity collapse.

That is, the coming year will not see a result of the form: if polynomial-sized classical hardware can achieve the same statistical separation as modeled for the quantum hardware (under either the linear or logarithmic “cross-entropy benchmark”) then counting and hence the polynomial hierarchy collapses to ${\Sigma_3^p \cap \Pi_3^p}$ . Thus we expect to still be talking about all this a year from now.

A Poem

Talking about talking about quantum supremacy, I wrote a short poem on its larger significances:

‘It From Bit’ we once proclaimed, but now the Bit has bit the dust from whizzing quantum chips that gamed coherence to evade the trust that the Word drove creation’s hour: Mother Nature fully lexical. Why don’t our brains then have this power? It is a status most perplexical.

The import of the polynomial-time Church-Turing thesis is that symbolic computation, our brains, our computing devices whose programs execute at the level of machine language, and natural processes on which any computing device can be based, are equivalent under broad notions of efficiency not just in computability. If this fails, then we can ask a question like the one about illusions quoted at the end of last week’s post on ${\mathsf{P = NP}}$ : why would so many smart people have had the illusion that the universe is based on classical information? This may have quick answers: the theory of quantum information wasn’t yet appreciated; it shares many similarities with classical information theory; classical information remains in the picture. Note that the Simons initiative It From Qubit has existed for some time.

But then comes a second question. Richard Dawkins speaks for many biologists in underscoring that the major open issues in the genesis of life concern the processing of information to build complex structures. If nature affords capability ${X}$ to this processing, one would expect complex biological structures—in particular, our brains—to evolve to avail it. Well, Roger Penrose spearheaded the effort to show that our brains employ distinctive quantum processes, but the physical side of his argument has been blunted by evidence. It could be that “quantum advantage” is not a life advantage. The classical falling-short of our grey matter would still be curious.

Open Problems

What are your predictions for 2020? What are your meta-predictions for the coming decade—that is, which 8 predictions do you think Claire Cameron will post on Wednesday? It may help you to know that last month she wrote a science article on the movie Cats.

[added note about It From Qubit]