Yuval Boger interviews mathematician Gil Kalai about his long-standing skepticism regarding scalable quantum computing. Kalai explains two main arguments behind his theory: correlated noise that may defeat quantum error correction and complexity-based limits on NISQ devices achieving quantum supremacy. They discuss experimental claims such as Google’s 2019 result, potential tests of Kalai’s conjectures, and the implications for the future of quantum research. The conversation also explores how Kalai hopes the community will evaluate bold claims and what scientific insights could emerge if quantum computing ultimately fails.
Transcript
Yuval Boger: Hello, Gil. Thank you for joining me today.
Gil Kalai: Hi, hi, Yuval. Nice to be here.
Yuval: Great to have you. So who are you and what do you do?
Gil: So I’m a mathematician. I am a retired professor from the Hebrew University of Jerusalem. Right now I’m a professor of computer science in Reichman University in Herzliya. For many years I also was an adjunct professor at Yale University. So I’m mainly a professor.
Yuval: And how did you get into quantum? Is that because of complexity theory? Is that because of some other reasons?
Gil: I got into quantum in 2005. I think my part was an interest in noise. I did some work already 10 years and 15 years earlier regarding certain models of noise and properties of noise and the notions of noise sensitivity and noise stability. So at some point I thought this might be relevant to quantum computing. I think one trigger for being interested was a lecture that I heard in Yale by Michel Devoret, which was something like “Quantum Computers, Mirage or Dream.” And although both mirage and dream look like things that are not so realistic, the lecture was very enthusiastic and there was not any skeptical aspect [in] it. So I thought maybe it’s a good idea to look at it from a skeptical direction. But this was 2002, so it took me three years to actually try to work seriously on this.
Yuval: I learned of your work because of Scott Aaronson. He often mentions you in presentations. I also spoke with him on a podcast recently. So it seems that your work occupies a small part of his head. And I think every time he says, well, every time there’s a quantum advancement, I think that Gil Kalai’s argument that quantum is not going to work, it becomes less and less plausible. So I’m curious to hear from the source, if you can explain in semi-layperson’s terms, why do you think quantum computers are not going to work or to what extent they’re not going to work?
Gil: Yeah, so actually my theory indeed asserts that quantum computing, quantum computers, is not going to work — and even early milestones towards quantum computers are going to fail. And essentially, I studied [the] two directions. The first direction, which was about seven years from 2005, was trying to build noise models which have some correlation that will fail quantum fault tolerance. I managed to come up with some conjectures about how realistic noise behaves. And these conjectures are fairly speculative. They assume some nasty behavior that will cause quantum error correction and fault tolerance to fail. And eventually you can distill the conjecture to the behavior of entangled pairs of qubits: So you posit that entangled pairs of qubits must have correlated errors. And his was the conjecture, and I studied it and found ways to formulate it rigorously and in the right generality that they will apply. And I think this is a sort of a nice suggestion. I don’t think this, as I said, should change people’s a priori belief [about quantum computers]; this conjecture should be tested experimentally. And I think we reached the time with the advancement of NISQ computers that this conjecture can be tested experimentally and we should see how it goes.
Another line of direction: I told you that I was motivated by my earlier work with [Nati] Linial and [Jeff] Kahn and later with Oded Schramm and Benjamini on noise sensitivity and noise stability. And there were suggestions around 2010,… a little bit later,… to manifest quantum supremacy using intermediate-scale quantum computers. So this was before the term quantum supremacy was coined and before the term NISQ was coined, but this was the [suggestion]. And this indeed looked like a puzzle, whether you can achieve quantum supremacy or large quantum advantage without doing quantum fault tolerance. And I think even the experts didn’t know how it will go. And there, in this direction, I developed a theory, first in a paper with Guy Kindler — which was limited to boson sampling. And this theory does not assume new models of noise, but rather takes the completely standard model that everybody else uses. But our theory used a computational complexity argument to show that NISQ computers cannot achieve quantum supremacy. And then there was another step, which is to show that NISQ computers cannot achieve quantum error correction, either because quantum error correction is a more difficult task and requires a lower rate of noise, or there is also some direct argument.
So all in all, this was an argument that led… — the direct conclusion is that quantum supremacy cannot be reached. And the indirect conclusion was that also quantum error correction of good quality required for quantum computing cannot be reached. And this argued directly on the rate of noise, and it assumed no correlation or nothing special about the noise. So this was another direction. And these were the two directions. I think they give a good argument for why quantum computers cannot work, but this is not an ironclad argument, and it’s very good that people are trying experimentally to advance and to build them. Looking forward, I’m very glad that humanity spent billions of dollars to test my theory, or maybe tens of billions of dollars, and we will see how it goes.
Yuval: How do you feel the theory stands up with some of the recent results, whether it’s random circuit sampling or error correction demonstrations that seem to indicate that errors could be corrected faster than they accumulate and that quantum computers, still in some very limited sense, could do things that classical computers are unable to do?
Gil: Yeah, so the random circuit sampling, starting with the 2019 experiment by Google, directly, if it stands, directly refutes my conjecture. So there are no games about it. If you can achieve quantum supremacy with NISQ systems, then this goes directly against the second direction that I mentioned that is based on this argument with Guy Kindler that says that quantum supremacy cannot be achieved without quantum fault tolerance or error correction. And this actually led to a third line of research, which is also now about six years old, which is to carefully scrutinize experimental claims. And primarily, this claim by the Google team from 2019. And this is another very interesting line of research.
Now, I can come back to this, but I should say that the quantum error correcting codes, they are not strong enough so far to refute my theory, neither in the connection of correlated errors, nor in the connection in [of] the second direction, but they’re certainly is something that I should take note and study carefully — this is some progress that we have to follow. And not only to follow it, we also have to check it very carefully.
Yuval: And I think the same goes to correlated noise. In fact, I think there was a recent Harvard-QuEra paper that said that correlated noise is actually an advantage. It allows us in certain cases in neutral atoms to do fewer rounds of error correction and more efficient algorithms. And so I guess my question is, what experiment would need to be performed to convince you, one way or the other, about the validity of the theory?
Gil: Well, usually it’s not one smashing experiment, but a series of experiments that should also be put together. I’m not familiar actually with this result that correlated errors can be advantageous. It is quite possible. The model that I have, my specific conjecture regarding correlated errors, would cause quantum error correction to fail. So this goes against this study. The point is that if you have a strong correlation between every pair of qubits, this leads to what I call spontaneous or noise synchronization. And this is manifested by bursts of errors which fail the quantum error correction.
Now there was also another experimental fact, that the fidelity estimate came up to be very close to the product of the fidelities of the individual components, and this is a nice fact, or encouraging fact, but it is not directly related to my conjectures about correlated error. So I made specific conjectures. It was not any type of correlation that is bad for the [quantum] computation. And these specific conjectures, I think they can be studied, and even on fairly small circuits, but they need to be studied, so I should wait for that.
Now, when it comes to quantum supremacy experiments, they go directly against my theory, and here we studied very carefully the experiment by Google from 2019. And there are strong indications that this experiment is inconclusive, cannot be trusted to describe the claims, neither about the supremacy nor about the fidelity. So this is our conclusion. We wrote several papers about it. Like other things, this can be studied and tested by the community. But I think there are a lot of results which reflect more of the experimental hopes and enthusiasm rather than the scientific reality. And we have to be careful about it.
Yuval: So today there are dozens of types of quantum computers and they operate, they may give incorrect results, but as a machine, maybe they emit noise, but as a machine, they seem to work. What is the implication if your theory is correct? What does that mean? Does that mean that they’ll never be sufficiently useful to solve real-life problems? What does it mean?
Gil: Well, actually, it’s a very good question, and it goes directly to the heart of my theory. Our theory about noisy intermediate-scale quantum computers is that they represent a very low-level computational complexity class. And this low-level computational complexity class, Guy Kindler and I refer to it as LDP, low-degree polynomials. So this is the type of distribution that can be described by polynomials in the variables of a low degree. I don’t know how familiar you are with the hierarchy of computational complexity. This is a fascinating area. But you can think about P, which is everything that the classical computer can do. Then you can think inside P, you can think about parallel computers, what parallel computers can solve. And inside parallel computers you can think about a very limited class called bounded-depth circuits, which is computers, classical computers, [that] the number of levels of computation is bounded. And inside this class there is our class, which is low-degree polynomials. And this is a very limited class of computational complexity. And everything that people now build belongs to this very low-level computational class.
Of course, if you build a quantum computer and you have a control which is using a classical computer, you can still exploit the power of the classical computer. But the added computation [power] from the quantum computer in everything that is built today is in this low-degree polynomial class. And this means that this will not give you any computational advantage whatsoever. Everything that it gives you can easily be simulated by classical computers. And so theoretically this will not give you an advantage. There is an interesting thing to add, that this very, very low level of computational complexity still allows classical information, classical error correction. So you can ask yourself, if quantum computers cannot work, why is it that classical computers can work? And the reason is that the noisy quantum world still supports the very basic method to get classical information and computation.
Yuval: You mentioned that you are a professor at the Hebrew University, or were a professor at the Hebrew University. This is where I got my bachelor’s degree. And one of the useful things that I learned in getting the physics degree is to take everything to either zero or infinity and sort of see what happens. Your theory talks about noise correlation. So as the noise gets less and less, I mean, today, you know, once upon a time, quantum computers had a 10% chance of an error in a quantum operation. And now it’s a 99% success or 99.9% success, and soon people are talking about five, six, seven, eight, nine nines of success, meaning that the error is getting infinitesimally small.
Gil: Yeah, we can talk about a lot of things…, but I should say [that] my second theory about the NISQ computers tells you very explicitly that the efforts to reduce the noise rate, in particular gate errors, will hit a wall. And it will hit a wall before reaching quantum supremacy. So we can talk about smaller and smaller rates of noise, but we will not see these small rates of noise. The efforts will reach a wall. You know, maybe from time to time there are new guys on the block, some new technology that is behind other technologies and can catch up. But the one consequence of my study is that this idealism of reducing errors as much as we can is imaginary and is a dream, if you want. And actually, if we can reduce errors sufficiently low, we don’t even need quantum error correction. We can run the original algorithms and we can run Shor’s algorithm and if we reduce the error sufficiently low, then we’ll be able to do it. But I think most physicists agree that quantum error correction is needed and my contribution tells us that the level of error needed for quantum fault tolerance will not be reached.
Yuval: You mentioned that governments are investing billions — governments and also non-government organizations are investing billions in quantum computers. If you were advising one of these national programs, what would you advise them to do? Would you advise them, for instance, to scale down the investment and first explore whether errors could indeed be corrected in a sufficiently convincing way before going back to these large investments, or would you suggest something else?
Gil: Ah, this is a nice question because I don’t have to be hypothetical. I can tell you two stories. One was when I was in Yale in, I think 2008 or something like that, and some colleagues of mine told me that there is some concern in the NSF about investment in quantum computing because of some skeptical views. And then I made the statement that I don’t think the skeptical theories at that time are strong enough to change people’s a priori beliefs. And I think the only way to know is to invest and see what are the results.
So later there was another interesting incident. Israel decided to invest, I think, several hundred million shekels every year, or let’s say a hundred million dollars every year, or maybe more, for quantum technology. And the Israeli prime minister announced it in some room full of scientists and diplomats, foreign diplomats. And then a colleague of mine came to Netanyahu, and maybe you know him, Aumann, and he said, you know, I have a colleague that thinks that this is a waste of money and nothing will come out of it. And then a few days later, he saw in the newspaper that Netanyahu said, we decided to invest in quantum computing, and I consulted also with Aumann about it, which is actually correct.
But, okay, so usually I don’t interfere with policymaking. And I was also approached directly. There is a large agreement among scientists that quantum computing is possible. I have my theory and my conjectures that would say that this is impossible. I think it would be very nice that they will be checked carefully. I think also it’s very important that experimental claims will be checked and scrutinized. And I think this is something that everybody should agree. Even if you believe that quantum computers are possible, not every claim by every academic group or commercial group should be taken without careful scrutiny.
But overall, I think the decisions of policymaking should follow the consensus. And you know, if people privately want to consult with me about their investment or their career trajectory, then I’m ready to privately discuss the situation with them. So I welcome investment by…, certainly by companies…, you know, there are companies- trillion-dollar companies, they can certainly afford to take the risk of something which has a lot of risk, and I think we will see how things go based on these efforts.
Yuval: So as we get close to the end of our conversation today, I wanted to ask you, what do you hope the quantum computing community will take from your work, regardless of who ends up being right?
Gil: Okay, this is quite a delicate question, because, you know, as much as we want everything to be nice and friendly, if I’m right, then much of the efforts in the quantum computer community is, I would say, considerably less important than people believe it is. And this is the reality, if I’m right, this is the reality. And I think one thing that I share, I share the enthusiasm for small problems also, especially mathematical problems, because I come from mathematics. So there are many intellectual challenges in this large-scale program. And they are of interest, also in the case that I’m right and the quantum computer cannot be achieved.
I think if I’m correct, this may give some, and here I agree with Scott, this may lead to some major advancement in physics, even beyond quantum computers, about approximations, about perturbations… So There are many areas of physics where there are things that are in tension with the ability to build quantum computers. So usually the common view says… you know, if the time-energy uncertainty principle conflicts with quantum computers, so let’s regard the time-energy uncertainty principle as a misconception. But if quantum computers cannot be achieved, this will reflect back on several problems in physics. Certainly when it comes to new phases of matter and topological quantum computers and Majorana zero modes. So this is a very interesting question in physics, and my theory suggests that these exotic states of matter cannot be created. This has some very interesting applications for physics. But I to be sincere, sure, [If I am correct] a lot of the efforts will reach a dead end.
Let me mention that there is now a possibility that AI will replace mathematicians. And some people are devastated by this fact. And I’m not devastated by this fact. I’m very curious to know what will be the answers to the problems [I care about]. [For] some of the problems, we like to see the answers one way or the other, and if AI can help, so be it. And I think what we do is valuable, both on the scientific and intellectual level, and on the personal level, even if things will not go our way and according to our hopes.
Yuval: And last, I wanted to ask you a hypothetical: If you could have dinner with one of the quantum greats, dead or alive, who would that be?
Gil: Now, I would have liked to have a dinner with Tony Leggett. He just passed away a few days ago, but he expressed ideas which might be somewhat similar to some of my,… they can be of some similarity with my theory, and I missed him only by a short time. There are many…, I think one of the fascinating parts about this project is that I do have the opportunity to have dinners, to have very nice conversations with physicists, with mathematicians from other areas, with computer scientists from other areas, even with philosophers. So on the level of bringing people together, I think it’s quite effective and we will see how things will turn out.
Yuval: Gil, thank you very much for joining me today.
Gil: Okay, my pleasure, Yuval. Nice to meet you.
—
Yuval Boger is the Chief Commercial Officer of QuEra Computing .