Are We Nuts?
Gil Kalai is one of the top researchers in the world in the area of combinatorics. His blog is one of the best in the universe.
He also has some of the top results of anyone. One measure of excellence is how important not your results are, but how important your conjectures are. He with Jeff Kahn created in 2006 the expectation threshold conjecture which was just solved by Jinyoung Park and Huy Tuan Pham— here.
The fact that open problems are perhaps more important than results will be reflected in the next FOCS 2023. There will be a whole track on open problems. See Amit Sahai, Shubhangi Saraf, and Thomas Vidick who have put together an FAQ about this: This year, FOCS 2023 will include something new: a Conjectures Track, separate from the Main Track. Submissions to the Main Track will be evaluated along similar lines as STOC/FOCS papers typically are, aiming to accept papers that obtain the very best results across all fields of theoretical computer science. Submissions to the new Conjectures Track will be evaluated completely separately from submissions to the Main Track. There is no a priori acceptance quota for either track, or desired number of accepted papers: it will all depend on the quality of submissions only.
Against Quantum Computers
Gil Kalai has argued against quantum computation being a faster type of computation. See his paper here for one example. Or see anti 1 and anti 2.
The New Yorker Magazine
Last month the New Yorker had two articles about math. That’s two more than usual.
The main article was on quantum algorithms by Stephen Witt. He is a reporter and has a degree in 2001 from the University of Chicago in mathematics.
His article features Peter Shor a leader in quantum algorithms—no relationship to Santa—but long time friend.
Witt’s article features other friends of ours such as Scott Aaronson—the owner of the wonderful blog—Shtetl-Optimized. Scott’s post starts: I, Scott confess: this was the first time I felt visceral anger, rather than mere bemusement, over this wormhole affair. Before, I had implicitly assumed: no one was actually hoodwinked by this. No one really, literally believed that this little 9-qubit simulation opened up a wormhole, or helped prove the holographic nature of the real universe, or anything like that. I was wrong.
Quantum Is Weird
Read the New Yorker article, which is a nice popular writeup by Witt. Quantum is tricky, but his article is pretty straightforward.
Witt’s main focus is on the potential to build quantum computers that can solve real problems. The goal is of course to make quantum computers that can handle more and more qubits. Witt says this will make: Quantum physics win the Nobel prizes; Quantum chemistry will write the checks. Tens of billions of dollars are being invested in searching for ways to make such quantum computers. The investments are by existing huge companies as well as new startups.
Quantum Is Powerful?
Witt assumes the usual view that classic computers are weaker than quantum computers. This is likely to be the case; it is the main viewpoint, but it is open. It could be that quantum computers could indeed be efficiently simulated by classic computers. That is still an open problem. See list of blogs on quantum for the main view.
We cannot prove that PSPACE is more powerful than P=POLYTIME. This is believed by most, but it is open. It could be the case that they are equal. If that is true, then Shor’s factoring algorithm is in P and other shocks happen. But it could be true.
Take a look at the recent A Closer Look at Some Recent Proof Compression-Related Claims paper by Michael Chavrimootoo, Ethan Ferland, Erin Gibson, Ashley Wilson. They show that a claimed proof that resolves a related open problem fails. But it could be possible via some other argument. It is interesting that people believe they have an approach to such results—even if their arguments are wrong.
Open Problems
Are we nuts to point out that quantum computers could be no more powerful than classic computers? Are the billions of dollars being spent on quantum computers foolish? What do you think? Should some resources be spent on advances in classic algorithms?
To generalize the question with a more general answer:
Yes, human beings are generally “nuts” for many biological reasons, including that our normal ways of dealing with the world fit the classic definitions of “delusional” (e.g. we are — asleep or awake — working with a set of beliefs between our ears that have only tenuous relationships to “what’s out there?”).
Einstein had a great quote, which also generalizes to this conclusion: “As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.”
Maybe Julian Schwinger’s theorem showing that CPT conservation is equivalent to translation+constant-motion invariance is an exception—?
Wish more people try to reflect upon such humble quotes of Einstein.
I guess we’re a little crazy, but what we really are: biological (self-generated) and brain (self-generated) simulations! We invented mathematics so that we could confront it with reality! 😉
The billions of dollars being spent on quantum computers are not foolish. Either they will work, or our attempts to understand why they don’t work (better than classical computers) will deepen our understanding of (classical computers and) nature (free after S. Aaronson).
Resources be spent on advances in classic algorithms should take into account that the universal serial computer stopped being the best abstraction some years ago. Todays computing architectures are parallel, vectorized, distributed and generally heterogeneous.
Lovely post. Thanks for the very kind words.
There were three possible reactions to Shor’s algorithm.
a) Let’s understand the reason for why quantum computers are unphysical!
b) Let’s build quantum computers! (And see what else they can do.)
c) Let’s show that factoring is in P.
For a short while a) was a common belief, but the discovery of quantum error correction and quantum fault tolerance, and human’s (lovely) optimism-bias, made b) the most widely believed answer.
Various people thought that there might be a polynomial algorithm for factoring; and a few were even directly motivated by the discovery of Shor’s algorithm. Here is Henry Cohn’s take: https://cohn.mit.edu/factoring . Of course the question “what is hard” is meaningful not only for the ultimate turns of event but also for today. I remember that once in a conference in Ra’anana somebody asked a very eminent researcher in cryptography “what do you believe about the hardness of factoring” after some thinking the response was “I believe it is easy”. To the next question “so what is the point in all the cryptosystems that depends on factoring being hard,” Shafi answered: “because factoring is hard now!”
I personally thinks that factoring is hard. I also think that (noiseless) quantum computers are nonphysical, and we had nice debate about it over here a decade ago. Since people have different opinions about factoring, learning the fact that quantum computers can sample according to the values of the permanents of general complex matrix (bosonsampling), reassured me about quantum computers being infeasible. (“You need to be crazy” I thought “to believe that a physical device can sample according to the values of permanents of an arbitrary matrix. (Because computing the permanent is sharp-P complete).)
I don’t have a specific recommendations for the question of spending billions of dollars. (If you consider investing in QC you can read my papers and reconsider if you find my papers conceiving. But regardless of my own view I’d advice keep in mind that it is a high risk endeavor, and of course a particular investment may carry additional risks.) I am personally pleased to see trillion-dollars companies (in computation-related business) invest hundreds of millions in quantum computers, and I also think such investments make sense. (Similarly, I am pleased to see countries invest in quantum science.)
I have a question on too much attention to the factoring problem. Is this because of the cryprography only, or for some other reason?
Why quantum algorithms could not solve graph isomorphism in polynomial time? They (the experts) failed or it is not an interesting problem for the quantum computers?
The factoring problem has an inner structure, you may call it the Abelian hidden subgroup structure. It is a “flat structure” in a certain way. The graph isomorphism problem on the other hand can encode higher order algebraic “groupoid orders”. I would guess that “we” have to come to terms with such higher order stuff ourselves first, before we can expect help from a specific model of computation (like quantum computing).
Finally, the permanent doesn’t seem to have any “known” structure. Therefore, as long as we don’t understand which properties makes it attackable by quantum computing, the suspicion that there is none and that quantum computing is simply unphysical is not unreasonable.
This is a piece of history I would like to record:
First, this comment should be made to the universality-Voronin piece, titled “Riemann Hypothesis — Why So Hard? FEBRUARY 21, 2021”. But it seems to be taken over in some real sense. Apologies for placing it here.
A few words about what is being recorded:
I always have this conviction that I will be able to see a proof by a person (other than me) for RH. I recently did. I will refer to the said claim/proof as PROOF.
As I have all along demonstrated that RH could be proved in the different major branches of mathematics, hinting that it could be short or even a single-word proof. PROOF can be summarized in one single word. We will refer to this single word as KEY.
The text encrypted (shown within the blockquoted) includes the pertinent URL, the person’s name (or pseudonym possibly) and a timestamp (indicating PROOF was made public quite close to and no later than the timestamp). The encryption was done with KEY as key. At an appropriate time in the future, if this record, as well as what is being recorded, does not get suppressed and deleted without a trace, we will be able to confirm.
(Note: the encrypted text was wrapped around, but there is no newline in the actual text string of 44 x 4 = 176 bytes.)
A few words about PROOF:
The person made PROOF a bit complicated. If he/she had not had the added convolution, the idea would have been clearer and the soundness more prominent. His/Her basic idea is just KEY.
Another exposure by the incident is the reason why we can not settle RH. His/Her idea was immediately and smotheringly dismissed.
In addition, I would like to refer to a somewhat relevant piece: https://twitter.com/alexkontorovich/status/1199018641439830021
By the way, “Are we nuts to point out that quantum computers could be no more powerful than classic computers?”
No. (In the sense of computability as well as in the sense of P \subset NP)
— RH
I feel the need for a bit of clarification and specificity.
It is pretty much universal consensus that, in recognizing contribution to mathematics, only idea counts and (techincal) detail is something many can fill in. And our modern day drama seems to tell us that a proof does not need to be perfect nor (does it need to be) complete. As pertaining to PROOF, it can also conveniently be “Grisha Type”.
— RH