The first part of the post is devoted to eight-year anniversary of my 2016 paper. I will go on to describe a recent lecture by Dorit Aharonov and conclude with my toast to Michael Ben-Or.
The Quantum Computer Puzzle, Notices AMS, May 2016.
In the eight years since my Notices AMS paper (with the beautiful drawings by my daughter Neta) “The quantum computer puzzle” appeared, my point of view has been challenged by several experimental attempts for demonstrating quantum advantage and quantum error correction. From what I can discern, my argument still holds as a serious alternative to the prevalent optimistic view regarding quantum computing.
The main experimental challenge to my theory, the fantastic 2019 “quantum supremacy” claim by Google, was largely refuted. Moreover, my Fourier-Hermite analysis (with Guy Kindler) proved valuable in scrutinizing (and largely refuting) another specific claim of “quantum supremacy” via boson sampling. Recently, I applied related Fourier methods (with Rinott and Shoham) for statistical analysis of samples coming from quantum computer experiments.
The crux of the matter lies in understanding quantum computers at the intermediate scale, both theoretically and experimentally. There are various interesting experimental endeavors employing diverse approaches to quantum computing in this direction.
Critically analyzing experimental claims is a vital and engaging aspect of this area. Alongside my collaborators, I endeavor to foster an open and candid technical dialogue with experimentalists, patiently await necessary raw data from experiments, conduct meticulous analyses, and provide detailed technical reports of our findings.
Facebook reminded me of the anniversary (click on the picture for the FB post and comments)
The original summary
Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.
Note that what I refer to as “small-scale” is now commonly called “intermediate-scale”. Here is the link to the original 2016 post about the paper (that also dealt with other matters).
The prevalent optimistic view
Optimism about quantum computers is a source of excitement and hope for many scientists and non-scientists including personal friends and individuals I greatly appreciate. The optimistic view (depicted in Neta’s drawing below) is shared by many members of the quantum computing community. Some attribute the possibility of quantum computing from it being a clear consequence of quantum physics, and others base their optimism mainly on recent experimental advances.
The question if quantum computation is possible is a clear cut important scientific question and naturally I believe that my theory for why quantum computers are inherently impossible will prevail. I find it exciting to understand others’ perspectives and intuitions on this central question, as well as to follow advances in quantum computational complexity and quantum algorithms.
Chinese version
In 2017 my paper appeared also in Chinese.
Dorit Aharonov’s recent lecture in the workshop dedicated to Michael Ben-Or
Dorit Aharonov’s brilliant lecture at the workshop dedicated to Michael Ben-Or described two central quantum tales, and briefly mentioned an additional research direction (open problem) suggested by her in the late 90s. Dorit also briefly mentioned her view on the skeptical efforts (from 16:45) and her beliefs regarding the state of matters today (19:26): She described a discussion from 2005 of Robert Alicki, Dorit, Michael, and me, and praised the skeptical efforts as important. She further asserted that in contrast to the mid 90s when quantum computation was considered the most theoretical part of computer science, at present many groups are approaching going beyond the break-even point for quantum error-correction. (She cited Google, Quantinuum and QuEra as examples.) Referring to the skeptical position and to the picture of Michael, Dorit, Robert and me, Dorit said:
I think that at this point, some of the people in this picture are starting to rethink whether their criticism [is valid]. It seems like reality is very close to prove that they’re wrong.
(Dorit said that maybe she will change her mind as well.)
Snapshots from Dorit’s lecture: The top-left slide is about the threshold theorem (mid-late 90s). The bottom-left slide is about later developments related to the threshold theorem (and the 2005 picture that I mentioned above); The top-right slide is about how a classical computer can test that a quantum computer did what it claimed to do. The 2008 paper of Aharonov, Ben-Or and Elad Eban started an exciting direction, and Dorit mentioned that it was motivated in part by Oded Goldreich and Madhu Sudan’s (skeptical) question about evidence for quantum physics in the high complexity regime. The bottom-right shows Dorit and Tal Rabin during the lecture. Below, Dorit’s question on the physics description of quantum fault tolerance and the transition from quantum to classical physics and her 1999 paper on the transition from the quantum world to the classic world.
A Toast to Michael Ben-Or
Michael Ben Or is a great friend, a great thinker, a great teacher, and a great scientist. Allow me to share our remarkable journey together. Michael and I met when we were 15 in a mathematics course for mathematically inclined high school students and shortly thereafter, we both embarked on our university studies. Following our service in the army, we pursued graduate studies together, and our families became closely intertwined during our time as MIT postdocs. In this picture, you can see our daughters, Abigail and Neta.
In summer 1984 Michael returned to Jerusalem as a faculty member and a year later, I followed suit. Silvio hosted a farewell party for Michael, attended by Avi and Shafi, although Michael himself was delayed by traffic jams on the highway from NYC to Boston.
In 1987 Michael and Nati wrote their influential paper on influences which profoundly impacted my own career trajectory. The year 1988 was the annus mirabilis for the theory of computing in Jerusalem. Michael authored several groundbreaking papers, including the two-prover paper mentioned by Shafi, as well as a seminal work on fault tolerance. It was also in 1988 that Tal Rabin, Michael’s brilliant student, completed her master’s thesis.
Let me move forward to 1995 and to the amazing and immensely important threshold theorem that Michael and Dorit proved. I always admired this breakthrough but only a decade later I also got interested in quantum computing, and specifically in the threshold theorem. I started attending the cozy quantum seminar at HUJI and learned a lot from Michael. Since both Michael and I are shy people the first time I asked Michael explicitly if he thinks that quantum computers are realistic was seven years later during one of the quantum workshops we organized. Michael affirmed that, yes, he is quite confident that quantum computers could be built! (However, Michael confided in me, that his original motivation in pursuing quantum fault tolerance was to prove the opposite theorem.)
During the years both Michael and I were involved in the center of rationality at HUJI and the HUJI Quantum Science Center (perhaps, small island of rationality in our troubled area, or are they?). It was a pleasure to host many quantum information scientists including Charles, John and Umesh in our conferences and international schools.
Here you can see Michael, Dorit, me, and Robert Alicki (one of the few scientists doing quantum computing research in the skeptical direction) in 2005 and seven years later in 2012.
Just a few weeks ago Michael drew my attention to the paper about logical quantum computing, for neutral atom quantum computers that demonstrate quantum error-correction and some rudimentary form of quantum fault tolerance and to a lecture here at the Simon Institute about this breakthrough.
Michael, best wishes for many years of science and friendship.
(The videotaped version was somewhat shorter; in the full version I tried to mention all the speakers of the workshop. It turned out that although Tal Rabin is a decade younger than me she first met Michael before me!)
Combinatorics and more 