Congrats Avi and Laci on the Abel Prize

Dorit Aharonov is a researcher in quantum computation. She was a Ph.D. student of Michael Ben-Or and Avi Wigderson. Her 1999 thesis, entitled “Noisy Quantum Computation,” included her role with Ben-Or as one of several superposed groups who discovered the quantum fault tolerance threshold theorem.

Today Ken and I wish to send our congratulations to Avi and Laci—László Lovász—on winning the 2021 Abel Prize.

The prize citation is:

For their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.

Genealogy

You might wonder why we are talking about Aharonov? She was a student of Avi and he was a student of mine—see this for more details. I am proud of Avi for his terrific results and also for his great students. I guess Aharonov is a grand-student of mine.

Lovász and Ken’s advisor, Dominic Welsh of Oxford, partnered with Dominic’s student Magnus Bordewich and Michael Freedman of Microsoft on a 2005 paper titled, “Approximate counting and quantum computation.” The paper translates criteria for approximating the Jones polynomial into simulations of quantum circuits. It references how topological quantum field theory (TQFT) implicitly embodies a quantum algorithm that meets the criteria, hence showing that the Jones approximation problem is complete for in a suitable promise-problem sense.

The genealogy of the Jones polynomial is that it was discovered by Vaughan Jones. Aharonov, with Jones and his student Zeph Landau, wrote a 2009 paper that makes the quantum algorithm for approximating the Jones polynomial explicit. To quote the converse of a statement in their abstract, removing the dependence on TQFT makes the algorithm “accessible to computer scientists.”

Aharonov’s work thus represents the mixing of elements of classical mathematics and computing theory (including quantum, i.e. non-classical, computing) that this year’s Abel Prize recognizes. Mixing is indeed the word, since results on the mixing rates of Markov chains by Lovász and many others undergird some of this work. This is true even more directly of a notable paper by her with Andris Ambainis, Julia Kempe, and Umesh Vazirani on quantum walks.

More Quantum

When we hosted the 2012 debate between Gil Kalai and Aram Harrow on the feasibility of large-scale quantum computing, Gil led off with the following photo of the physicist Robert Alicki, Ben-Or, Aharonov, and himself, which was taken in Jerusalem in 2005.

Aharonov wrote an influential long survey in 1998 titled “Quantum Computation,” which grew out of her thesis and is sometimes confused with it. Ken and I owe a small debt to diagrams she used in the survey, for which she in turn alluded to Richard Feynman’s path integrals and their visualizations:

We expanded on this kind of diagram in our textbook on quantum computing with MIT Press, whose second edition is scheduled to appear next month.

Abel Prize and Lower Bounds

Whereas the Fields Medals are awarded only every four years, the Abel Prize is annual. It commemorates the Norwegian mathematician Niels Abel. Although it has been awarded only since 2003, it was originally proposed in 1899 expressly as a counterpart to the Nobel Prizes—and fell through only because of the 1905 separation of Sweden and Norway. We most recently covered the 2019 prize going to Karen Uhlenbeck.

Abel of course is the mathematician who gave his name to abelian groups and much else. About his short life of twenty-seven years, Charles Hermite said:

Abel has left mathematicians enough to keep them busy for five hundred years.

What we note is that Abel’s most famous result is a lower bound type result. He showed the impossibility of solving the general quintic equation in radicals. Finding clever identities, clever inequities, clever algorithms is hard. But not as hard as showing that something cannot be done.

Abel’s result is perhaps like proving today, in the 21st century, a lower bound on the complexity of some concrete problem. Some of Avi’s and also Laci’s best work has been directed toward this quest: Prove some non-trivial lower bound. Avi has worked on numerous approaches, including the fusion method in 1993. Although its lack of breakthroughs has caused jibes about “cold fusion,” Avi noted the following in a recent talk at the Simons Institute:

I will review (and hope to revive) a collection of old works, which suggest obtaining circuit lower bounds by “fusing” many correct computations (of a circuit too small) into an incorrect computation.

In a couple of models, this viewpoint led to (slight) superlinear lower bounds, which nonetheless have not been improved upon for 25 years.

We hope that the Abel Prize award will promote efforts to achieve not-so-slightly super-linear lower bounds on circuit size, running time, algebraic size, quantum effort, anything like that…

Open Problems

We also tip our hat to others who have reported on the Abel Prize, including some of our fellow bloggers: Gil Kalai here, Scott Aaronson here, Lance Fortnow and Bill Gasarch here, plus Kevin Hartnett for Quanta here.