Ordinary computers can beat Google’s quantum computer after all

Science magazine has an article written by Adrian Cho Ordinary computers can beat Google’s quantum computer after all. It is about the remarkable progress in classical simulations of sampling task like those sampling tasks that led to the 2019 Google’s announcement of “quantum supremacy”. I reported about the breakthrough paper of Feng Pan and Pan Zhang in this post and there are updates in the post itself and the comment section about a variety of related works by several groups of researchers.

The very short summary is that by now classical algorithms are ten orders of magnitude faster than those used in the Google paper and hence the speed-up is ten orders of magnitude lower than Google’s fantastic claims. (The Google paper claims that their ultimate task that required 300 seconds for the quantum computer will require 10,000 years on a powerful supercomputers. with the new algorithms the task can be done in a matter of seconds.)

Also regarding the Google supremacy paper, my paper with Yosi Rinott and Tomer Shoham,  Statistical Aspects of the Quantum Supremacy Demonstration, just appeared in “Statistical Science”. (Click on the link for the journal version.) The Google 2019 paper and, more generally, NISQ experiments raise various interesting statistical issues. (In addition, it is important to double check various statistical claims of the paper.) One of our findings is that there is a large gap between the empirical distribution and the Google noise model. I hope to devote some future post to our paper and to some further research we were doing.

The leaking of the Google paper in September 23, 2019 led to huge media and academic attention and many very enthusiastic reactions.  I also wrote here on the blog a few critical posts about the Google claims.

Here is a figure with the price of bitcoin around the time of the Google quantum supremacy (unintended) announcement.

bc666

Posted in Quantum, Updates | Tagged | 2 Comments

Test Your Intuition 50. Two-Player Random Walk; Can You Detect Who Did Not Follow the Rules?

Ruth and Ron start together at the origin and take a walk on the integers. Every day they make a move. They take turns in flipping a coin and they move together right or left according to the outcome. Their coin flips create a simple random walk starting at the origin on the integers.

We know for sure that they we will return to the origin infinitely many times. However, their random walk never comes back to the origin, so we know for sure that one of them did not follow the rules!

Test your intuition: Is it possible to figure out from the walk whether it was Ruth or Ron who did not follow the coin-flipping rule?

RuthRonRW

Posted in Probability, Test your intuition | Tagged , | 12 Comments

ICM 2022. Kevin Buzzard: The Rise of Formalism in Mathematics

LSR-collage2

In this post I would like to report on Kevin Buzzard’s spectacular lecture on moving mathematics toward formal mathematical proofs.  (Here are the slides.) The picture above is based on images from the other spectacular Saturday morning lecture by Laure Saint-Raymond. The issues raised in Laure’s talk regarding fluctuations, atypical behavior, and chaos are rather close to my heart and recent interests.

Let me mention that in ICM2022 discord was used for question and answers (in addition, some of the lectures in front of live audience had a lovely Q/A part), and Kevin’s lecture led to many live questions and questions on discord.

Can we widely formalize and use computer to check mathematical proofs?

Kevin’s lecture gives strong evidence that the answer is yes! Here is an analogy, until a few decades ago typing a paper usually involved handwriting it, giving it to a typist, and then making a few tedious rounds of corrections. This has changed and now most mathematicians type their own papers. It seems quite possible that in a couple of decades mathematicians will write their proofs in a way which allows automatic verification.   

speaker_kevinbuzzard-370x370

Kevin Buzzard !

A demonstration of how it works

Kevin demonstrated a verification of a proof to a theorem in topology asserting that the composition of two continuous functions is continuous. The demonstration was a little quick for me (I don’t know “Lean”) but it looked very convincing. You can see in real time how Lean replaces the term “continuous” with its definition and how the steps of the proofs enter Lean’s “brain”. Following this demonstration Kevin also showed a couple of short-cuts, using so-called “tactics” based on tricks or facts that the program already know. (The second short-cut was based on the theorem already there in the library.) At the end of each proof the program asserts “goals accomplished”  with an emoji of a flower. 

Proving theorems, Kevin said, turns into a nice computer game. Kevin also described the prehistory; indeed the example above could been achieved by systems from the 90s.

What was achieved so far?

This was the main part of Kevin’s lecture and the progress is mind-boggling.

Part 1: Before 2018

2004: A formal proof of the prime number theorem (Avigad et al using “Isabelle/HOL”, not having complex analysis it verified an elementary proof.) In 2009 Harrison verified the complex analysis proof.

2004: Gonthier formally verified the four-color theorem (using “Coq”)

2005: Hales verified the Jordan curve theorem (“Isabelle/HOL”)

2013: Gonthier et al formally verified Feit and Thompson’s odd order theorem

###

2015: Hales and a team found a formalized proof for the Kepler conjecture  (that he and Furgeson had proved in 1998).  Hales’ 2017 lecture on this proof changed Kevin’s life and led him to his work on formal proofs. Hales proposed to create a system capable of “understanding” all statements of theorems published in serious mathematical journals. (Understanding statements is easier than understanding proofs.)

First, Kevin said, one needs to formalize all the statements of undergraduate mathematics. 

###

In 2017 Kevin started a Lean club for undergraduates! They did very well. The lean community (I suppose Lean is used for other things) embraced this project. 

Introduced by Grothendieck in 1960, schemes made understandable to computers by Lean in 2018. (Schemes and especially schemes of line-bundles are needed for understanding Kazhdan’s lecture from the previous post. I personally have a vague understanding of what they are. BTW, the lecture mentions Scott Morrison as a Lean star and I wondered if this is the MathOverflow star by the same name.) 

###

Next, Kevin mentioned the progress related to Scholze’s perfectoid spaces. Earlier, very complicated proofs to simple-to-state theorems were formalized and this was a formalization of very simple theorems on very complex objects. It was also a nice way to learn the definition! 

&&&

Part II after 2018

Lean and even its mathematical library “mathlib” are by now gigantic project and Kevin made it clear that it’s not “his” project but rather that he is one of many, many participants.

2020: The Scholze challenge (we talked about it in this post, and in any case it is way over my head). This is an example of formalizing a very complex proof of a very complex theorem. It eventually led to a somewhat different proof and better understanding of the necessary underlying objects.

2018: A new proof by Gouezel and Shchur for a 2013 theorem by Shchur whose formalization led to finding an error and then correcting it.

2019 the proof of the 2016 cap set conjectures (see this post) was formalized.

2021 Bloom proved that every dense set of integers contains a finite subset where the sum of reciprocals equals 1. The proof  was formalized by Bloom and Bhavik Mehta (including all earlier results the paper relies on and including the circle method).

2019 Apery’s proof of the irrationality of zeta (3) was formalized.

Let me stop here, there were 20-30  more startling successes for which I refer you to the talk itself. Fermat’s last theorem, Poincare’s conjectures in dimensions 4 and 3 and the classification of finite simple groups are still waiting for their turn and of course so are many more less famous proofs. Kevin refers to it as a new era of digitizing mathematics.

Other issues regarding formal mathematical proofs

Did the movement to formal proofs gain enough attention/recognition in the mathematical community?

Kevin complained about this matter (every appearance of ### above) but I tend to disagree with this complaint. Formal proofs did gain a lot of attention and, in any case, the appropriate response if you do not get attention is “to work harder” which incidentally is also (on the nose) the appropriate response if you do get attention. Also, Robert Aumann often says that in science, like in other areas, salesmanship accounts for more than 50% of success, and indeed Kevin mentioned that salesmanship was among the motivations of one of their projects (&&& above).

Are there many cases that in the process of formalization the proof turned out to be wrong?

The lecture mentioned a single case for which the proof was corrected. It will be surprising (perhaps even suspicious) if upon formalization, 99% of proofs turn out to be correct. (And there are interesting issues on what to do with theorems and proofs that we cannot verify formally.)

Are the formal proofs absolutely reliable?

This is something I asked about in discord and it led to interesting comments. (It is related to the previous question.) Kevin mentioned, for example, that initially the proof of the irrationality of zeta (3) proved a different statement.

Are formal proofs useful for teaching mathematics?

Probably, yes! This is an interesting issue worthy of further discussion.

What about combinatorics?

This is also something I asked about over discord. I was referred to the following link:  Combinatorics in lean.

Can we use the formal methods to make the computer understand incomplete mathematical approaches, and vague mathematical ideas? 

I suppose that the answer is positive. This would be a nice project.

Can human proofs be automatically transferred into formal proofs?

This does not seem out of the question, but having such a “compiler” will require also different AI abilities that go well beyond current efforts.

Can computers replace humans in doing mathematics and especially in proving theorems?

Kevin started his lecture by answering “NO” and referring to such a possibility as “science fiction”. The way I see it is that there are various avenues towards computerizing (what we regard now as) the creative process of mathematics including coming up with conjectures, proving theorems, and building theories, and formalizing mathematical theorems and proofs besides its own value can also be regarded as an avenue (among several) in automatizing mathematics.

Kevin asserted that he is not impressed by current successes, but people could equally be unimpressed with formalizing mathematics in 2010, and he mentioned some reasoning coming from AI for why it is difficult (which I could not understand). On the other hand, since he regarded the state of the project as “the beginning of the beginning” it may be the case that Kevin does think about tasks which go beyond “just” formalizing mathematics.

There are various other skeptical voices regarding the possibility of replacing humans with computers in mathematical research, including the famous mathematician Michael Harris who often writes about it, but I am not familiar with the skeptical arguments themselves.

There are many people who are enthusiastic about replacing humans with computers in doing mathematics and few of them even put their careers where their mouth is. Doron Zeilberger (aka, Doron Z. and Dr. Z) is a very famous example. Now, with the next 2026 ICM in Philadelphia, we can say that:

If Doron Z. does not come to the ICM, the ICM comes (pretty close) to Doron Z,

and it will be nice to see various aspects regarding the interface between mathematics and computers represented in ICM 2026.

Regarding the use of computers in major mathematical achievements see these two Math Overflow questions (one, two).

 

Another link from the discussion: Solving (Some) Formal Math Olympiad Problems

Lean

A description of a Lean project in progress. The green ellipses represent completed parts. I am a little worried by the ellipse where it is written “clearly” and also by the one with the title “it is easy to see” 🙂 .

Updates:

1) Doron Zeilberger, a pioneer in using computers for mathematics, wrote a skeptical opinion regarding the formal proof direction https://sites.math.rutgers.edu/~zeilberg/Opinion184.html . Twelve years ago he wrote a similar opinion .   

2) Georges Gonthier, an early hero on formal proofs gave another ICM 2022 lecture: Computer proofs: teaching computers mathematics, and conversely.

Posted in Computer Science and Optimization, ICM2022, Logic and set theory, Mathematics and Computers, Number theory, What is Mathematics | 6 Comments

ICM 2022: Langlands Day

ICM 2022 is running virtually and you can already watch all the videos of past lectures at the IMU You-Tube channel, and probably even if you are not among the 7,000 registered participants you can see them “live” on You-Tube in the assigned date and hour. 

I landed back from Helsinki on Wednesday night and I devoted Thursday to watch lectures, while in later days other tasks and obligations gradually took over part of my time. I plan to catch up during the summer.

The three plenary lectures on Thursday, July 7 were around the Langlands program.

David Kazhdan, Marie-France Vignéras and Frank Calegari.

All three plenary lectures on Thursday were about the Langlands program. The opening lecture by my friend and colleague David Kazhdan proposed, mainly to experts in representation theory, a glance well beyond the horizon. David offered three complementary approaches to a far-reaching extension of the Langlands program where one attempts to replace “global fields” by more general fields. Specifically, David and his collaborators want to extend the unramified Langlands correspondence from fields of rational functions on curves over finite fields to fields of rational functions on curves over local fields. The ICM lecture was rather short, however, David gave two detailed talks at our basic notion seminar and here is the recording of the first lecture

DKBN

David Kazhdan’s lecture in our basic notion seminar

Marie-France Vignéras and Frank Calegari gave wonderful general audience lectures.  Marie-France even advised the experts in the lecture room to consider going somewhere else, and Frank posted his amazing mathematical video on his blog, adding a disclaimer that the target audience for his blog is close to orthogonal to the target audience for his talk. 

 

CalegariFicm

FC2022c

Pictures from Calegari’s lecture: Some computations from Frank Calegari’s lecture may appeal to very large audiences (top left); Later things get more difficult: A recent breakthrough by Ana Caraiani and Peter Scholze (Caraiani also gave an ICM lecture) is mentioned and so is the recent proof of the Hasse-Weil conjecture for surfaces of genus 2!

MFVicm2022d

MFVicm2022aMFVicm2022bMFVicm2022c

Pictures from Marie-France Vignéras’ lecture.

 

Posted in Algebra, ICM2022, Number theory | Tagged , , , | Leave a comment

ICM 2022 awarding ceremonies (1)

fm2022

Hugo Duminil-Copin, June Huh, James Maynard and Maryna Viazovska were awarded the Fields Medal 2022 and Mark Braverman was awarded the Abacus Medal 2022.

I am writing from Helsinki where I attended the meeting of the General Assembly of the IMU and yesterday I took part in the moving award ceremonies of ICM2022 hosted by Aalto University.  This will be the first post about the ICM 2020 award ceremonies.

The opening day of ICM2022 was exciting. Hugo Duminil-Copin, June Huh, James Maynard and Maryna Viazovska were awarded the Fields Medals 2022. Mark Braverman was awarded the Abacus Medal. The event was videotaped and can be found here. Update: The five lectures of the medalists can be found here.

In the ceremony, I gave the laudation for June Huh.  Here are the slides of my talk. The preliminary version of my proceeding paper is here on the IMU site. Please alert me about mistakes in my paper or if you have any suggestions for changes or additions. (I already found that on two occasions I embarrassingly wrote “Brändén” Instead of “Braden”, sorry for that.) Update: Here is a corrected version.

The IMU site contains a lot of material about the Fields medalist and other prize winners. It contains beautiful videos, and preliminary versions of the proceeding papers by the medalists and by those giving the laudations.

Andrei Okounkov wrote four wonderful detailed “popular scientific expositions” (those are available on the IMU site) which provide much scientific background as well as Andrei’s own scientific perspective. It is a great read for wide audience of mathematicians, ranging from  advanced undergraduate students.  Experts will also enjoy Andrei’s perspective.

Svetlana Jitomirskaya was awarded the Ladyzhenskaya Prize in Mathematical Physics (in a ceremony held two days earlier), Barry Mazur was awarded the Chern Medal, Elliott Lieb was awarded the Gauss Prize, and Nikolai Andreev was awarded the Leelavati Prize.

I hope to discuss these awards and some further personal and mathematical reflections in a subsequent post.

Congratulations Hugo, June, James, Maryna, Mark, Svetlana, Barry, Elliott, and Nikolai!

Here on my Blog

Let me give some links to discussions here on the blog on works by laureates.

I wrote about Maryna Viazovska’s amazing breakthrough in the post  A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24, and this additional post Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska: Universal optimality of the E8 and Leech lattices and interpolation formulas.

I reported here in 2009 on the startling solution by Mark Braverman of the Linial-Nisan conjecture.

The story of James Maynard’s startling results and the gap between primes story is described in this post.  In July 2014 we ran at HUJI a beautiful learning seminar on small gaps between primes, where James Maynard gave a series of three lectures. His result on “bounded intervals containing many primes” both strengthened and simplified Yitang Zhang’s earlier amazing result on “bounded intervals containing two primes.”  Maynard developed large chunks of his approach independently from Zhang’s work.

I discussed two results by Hugo Duminil-Copin : After the start of the pandemic but before the war in Ukraine, I had a “cheer-you-up in difficult times” corner and in this post,  to cheer you up,  I wrote about a breakthrough by Hugo Duminil-Copin, Karol Kajetan Kozlowski, Dmitry Krachun, Ioan Manolescu, Mendes Oulamara  (and yet another wonderful result by Hugo Vanneuville and Vincent Tasion). In this 2015 post I wrote about another breakthrough by Hugo Duminil-Copinand Vincent Tasion. (And see this post for a picture of Hugo mentioning KKL and BKKKL.)

And,  of course, I wrote about June Huh several times. Here are a few examples: About Huh’s 2018 ICM talk; ICM 2018 Rio (4): Huh; Balog & Morris; Wormald; about the Mihail-vazirani conjecture  Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids! ; About the early works on the Heron-Rota-Welsh conjecture for representable matroids; and about the full solution of the Heron-Rota-Welsh conjecture by Adiprasito, Huh, and Katz.

In this post we tried to cheer you up with “harmonic polytope”, which came up in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids and were further studied by Federico Ardila and Laura Escobar.

Posted in Academics, Algebra, Applied mathematics, Combinatorics, Computer Science and Optimization, Convexity, Geometry, ICM2022, Probability | 5 Comments

ICM 2022 Virtual Program, Live events, and Dynamics Week in Jerusalem

ICM 2022

Next Tuesday, July 5 2022 will be the opening day of the International Congress of Mathematicians (ICM 2022) that, because of the war in Ukraine, will be fully virtual. Here is the link for the program for ICM 2022 according to days. For those who did not register or who want to hear several parallel talks the organizers promised to release all videotaped lectures shortly after the end of the congress. The IMU Award Ceremony 2022 on 5 July will be streamed live from Helsinki via the IMU’s YouTube channel and Facebook page.

Here is the website of ICM 2022. Here is a very useful webpage of supporting satellite events. One of those events take place at HUJI.

Dynamics week in Jerusalem

Between July 3-8, 2022 we will have a “Dynamics Week” in Jerusalem which will consist of two related but separate conferences at the Mathematics Institute of the Hebrew University. The first conference is  Ergodic Theory and Beyond, July 3-5, emphasizing the connections between ergodic theory and other fields celebrating Benjy Weiss’s 81st birthday (originally planned to celebrate his 80th but then the pandemic happened). The second conference is in person session of the virtual ICM, July 6-8, with speakers mostly (but not only) from the dynamics section.

jer-dynamics

Posted in ICM2022, Updates | Tagged , | Leave a comment

Algorithmic Game Theory: Past, Present, and Future

Noam Nisan is 60HMN

Today, June 26 2022, is the opening day of Algorithmic Game Theory: Past, Present, and Future, a workshop in honor of Noam Nisan’s 60th Birthday. The workshop takes place on June 26-30 2022, at the CS building at The  Hebrew University of Jerusalem. Noam is a long time friend and colleague and I am proud to say that I was his second year linear algebra TA in the late 70s.  Noam is also among the people that suggested to me to start a blog and he opened his own (now collective) blog a short time later. Congratulations, Noam!

Festive conferences also on the occasion of Hagit Attiya and Moni Naor’s birthdays

Two other legendary computer scientists of the same early 1960s vintage also had birthday conferences. 40 Years of Distributed Computing was a workshop celebrating Hagit Attiya’s 60th birthday, and there was a half-secret conference celebrating Moni Naor’s birthday that I could not find on the internet. Congratulations Hagit and Moni!

10 new members to the Israel Academy of Sciences and humanities

I was happy to learn last week (English) about ten newly elected members, five women and five men,  to the Israel Academy of Sciences and Humanities. Among them, Noam Nisan. Congratulations to all new members, and to the Israeli academy.

Posted in Academics, Economics, Games, Updates | 1 Comment

Richard Stanley: Enumerative and Algebraic Combinatorics in the1960’s and 1970’s

In his comment to the previous post by Igor Pak, Joe Malkevitch referred us to a wonderful paper by Richard Stanley on enumerative and algebraic combinatorics in the 1960’s and 1970’s.

See also this post on Richard’s memories regarding the proof of the upper bound theorem for spheres Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found.

Posted in Combinatorics, What is Mathematics | Tagged | 1 Comment

Igor Pak: How I chose Enumerative Combinatorics

Another great post by Igor Pak

Igor Pak's blog

Apologies for not writing anything for awhile. After Feb 24, the math part of the “” slogan lost a bit of relevance, while the actual events were stupefying to the point when I had nothing to say about the life part. Now that the shock subsided, let me break the silence by telling an old personal story which is neither relevant to anything happening right now nor a lesson to anyone. Sometimes a story is just a story…

My field

As the readers of this blog know, I am a . Not a “proud one”. Just “a combinatorialist”. To paraphrase a military slogan “there are many fields like this one, but this one is mine”. While I’ve been defending my field for years, writing about its struggles, and often defining it, it’s not because this field is more important than others. Rather, because it’s so…

View original post 1,095 more words

Posted in Combinatorics, What is Mathematics | Tagged | 1 Comment

Quantum Computers: A Brief Assessment of Progress in the Past Decade

In this post I give a brief  assessment of progress in the past decade, triggered by a recent article in Forbes Magazine that mentions my view on the matter.

Waging War On Quantum – A Forbes Article by Arthur Herman

Arthur Herman is a popular Historian and a senior fellow at the Hudson Institute. On Forbes Magazine he “comments on quantum computing and AI and American national security”, and his recent Forbes article Waging War on Quantum (thanks, Alexander Vlasov) starts as follows:

Quantum computing will never work. Keeping enough qubits stable long enough to do any significant calculating or processing, is a mathematical impossibility. The whole idea that one day quantum computers will discover new miracle drugs, or crack public encryption systems, is a mirage. Even worse, it’s a hoax.

That’s been the message from so-called quantum skeptics for a decade or more, including physicists like Gil Kalai of Hebrew University and Mikhail Dyakonov of the University of Montepellier—all in spite of the fact that quantum computers have continued to grow in sophistication and qubit power. Most experts now agree it’s not a question if a large-scale quantum will emerge that can break into public encryption systems using Shor’s algorithm, but when.”

The first paragraph gives a reasonable description of my views, however I never referred to the whole idea of quantum computing as a hoax. Regarding the second paragraph, it is indeed correct that quantum computers have continued to grow in sophistication and qubit power, however my theory (based on a computational complexity argument) is that progress for reducing the error rate will reach a wall and that recent progress merely approaches this limit. Let me elaborate a little on the development of the past decade as I see it.

Before moving to my assessment I would like to note that Arthur Herman’s offers an outrageous conclusion to his article. He suggests that skepticism of quantum computers (and of the company IonQ) puts the skeptics’ countries at risk. In my opinion, the militant rhetoric of the title and of the conclusion is very inappropriate.

Assessment of progress in the past decade

The past quantum computing decade is characterized both by notable progress, adjustment of expectations, larger investments, much enthusiasm, and some hype. The overall picture is unclear and might be clearer 5-10 years from now.

The following picture (click to enlarge) describes the shift in the community view over the last decade (as I see it).

2010-2020d

On the left you can see David DiVincenzo’s famous 7-steps road map to quantum computers. DiVincenzo put forward these steps in his 2000 paper  The physical implementation of quantum computation,  and the above picture on the left is a graphic description of these steps in a 2013 review paper by Michel Devoret and Rob Schoelkopf.  The caption under the Figure asserts that “Superconducting qubits are the only solid-state implementation at the third stage, and they now aim at reaching the fourth stage (green arrow). In the domain of atomic physics and quantum optics, the third stage had been previously attained by trapped ions and by Rydberg atoms. No implementation has yet reached the fourth stage, where a logical qubit can be stored, via error correction, for a time substantially longer than the decoherence time of its physical qubit components.” The fourth step “logical memory with (substantial) longer lifetime than physical qubits” looked to many like a near term goal ten years ago.

One important development of the last ten years was to introduce building NISQ computers and achieving “quantum supremacy” (and related tasks like high “quantum volume”) as an intermediate goal towards DiVincenzo’s step four. (See the picture on the right.) Of course, there is nothing wrong with setting intermediate goals, we do it all the time and this can be very fruitful.

For me, from the skeptical point of view, these intermediate goals were an opportunity, allowing me to present a clear computational theoretic argument for why “quantum supremacy” is out of reach and to connect the problem with the theory of noise-sensitivity and noise-stability and with Fourier methods that I and my colleagues developed in the 90s.

Adding the intermediate goal of quantum supremacy also represented a much slower time-table than what people previously anticipated. For example, nine years ago in 2013  John Martinis gave a lecture at QSTART,  the opening conference of our HUJI quantum science center. At that time, John expected to have the ability of building distance-3 and distance-5 surface codes within a few years and the tasks of demonstrating logical gates and of logical qubits with 10^{-15} error rates some years later. John also mentioned the ability to control 20 qubits within one month (to this Ray Laflamme commented that it is going to be a long month). All these targets are today still out of reach. It is undisputed that considerably lower noise rates are required even for achieving distance-3 surface codes and it is still not possible to have good control of 20-qubit (and perhaps even 10-qubit) quantum computation.

Of course, John Martinis himself was the leader of the Google efforts towards “quantum supremacy” which are now being carefully evaluated, and his vision and technology from 2013 was important for the Sycamore NISQ experiments. Let me mention that Google’s fantastic “quantum supremacy” claims were largely (but not fully) refuted.

There was a similar level of optimism from various other researchers. It was expected that coherence time would increase by a factor of ten every three years and there was a proposed “double exponential law” prediction for the classical computational power required to simulate quantum devices as time proceeds.  I personally don’t regard these specific claims as hype but rather as (at times, over-the-top) reasoned optimism, but both the reasoning and the predictions themselves should carefully be examined.

NISQ computers are interesting, and they allow interesting quantum physics experiments. Herman asserts that “quantum hybrid systems are making the qubit revolution something that’s happening now, not just a distant dream” and this echoes hopes of several researchers in academia and industry. My analysis asserts that NISQ computers are, from the computational complexity perspective, primitive classical computational devices with inherent chaotic behavior, and therefore, I don’t see how hybrid systems and the interface with conventional computers would turn them into useful computational devices. (They can still be useful for quantum physics experimentation.)

Let me repeat: slower progress than anticipated is very common, setting new intermediate goals is both common and welcome. By themselves they do not imply that the target of “large-scale quantum computers that can break into public encryption systems using Shor’s algorithm” is unrealistic, and indeed many experts in the field believe that it is a matter of time for this ultimate goal to be reached. My view is different, I try to explain my argument to other experts, and to offer experimental predictions and theoretical implications. There are good reasons to hope that the matter will be tested experimentally in the years to come, but my assessment is that the experimental picture from the past decade is not clear.

IonQ, trapped ion quantum computation, and Elon Musk

Herman’s article was triggered by a 183-page document written by a group called “Scorpion Capital.” The document attacks Maryland-based quantum computer company IonQ and among various concerns it also briefly mentions my and Michel Dyakonov’s positions about quantum computers.  I myself share the common view that ion-trap methods for quantum computers form a major avenue and that Chris Monroe (a co-founder of IonQ) is a major player in this direction. I don’t know much about IonQ’s specific efforts, but I would expect that large scale investment is required to put ion-trap methods to test and I personally would like to see it being tested. So I would be quite pleased to see Elon Musk deciding to buy IonQ or the Israeli trapped ion QC company of Roee Ozeri (or both) 🙂 and to make  trapped ion technology his quantum computing signature. Incidentally, the comment section of my 2018 Quanta Magazine interview presented an interesting exchange between Monroe and me (starting here).

A few more remarks:

1) Herman’s article raises several other interesting issues like when (and if) is the appropriate time to transfer to “post quantum cryptography” protocols.

2) There are a few researchers skeptical of quantum computers that actually conduct research and write papers (and books) about it. (There are others that regard the idea as absurd nonsense of absolutely no interest.) A notable researcher who wrote several important papers in the skeptical direction since the late 90s is Robert Alicki from the University of Gdansk.

3) Here is Herman’s crazy conclusion: “No one is saying the Scorpion Capital short-sellers are in Chinese pay, or that skeptics like Dyakonov and Kalai are knowingly putting their countries at risk. But waging war on the U.S. quantum industry can have serious consequences, unless quantum companies and labs show that they are not intimidated, and reassure the public that the quantum future doesn’t rest on hype but significant achievements—achievements that will make our country and our world safer, stronger, and more confident about our future as a whole.”

4) I changed the title to reflect the main topic of the post.

Update 2 (June 6, 2022):

When (and if) is the right time to transfer to post quantum cryptography?

Continue reading

Posted in Quantum | Tagged , | 12 Comments