Is HQCA Possible? A conversation with Michael Brooks

Here is a short email interview from April 2021 with Michael Brooks from “New Scientist”.

Dear Professor Kalai, I’m writing a short feature for New Scientist magazine on the theme “Will we ever have a useful quantum computer?”. I’m aware of your work on the problems with noise, and your position that error correction won’t be possible.

This is correct. My analysis asserts that quality error correction won’t be possible and that even the easier target of HQCA (huge quantum computational advantage) won’t be possible. Here is a link to my new paper that you may find useful. It refers to recent developments: the Google Sycamore experiment and HQCA claims are discussed in Sections 6 and 7, and there is a new Section 9 regarding the very recent developments.

I was wondering whether anything you’ve seen – demonstrations or arguments – in the last few months have done anything to change your mind, or whether you are now more convinced than ever that we won’t ever see truly useful (beyond doing science) quantum computing? 

Well, I think that my theory is rather strong but not ironclad. As for the level of my conviction, it does not change often, but roughly speaking there were three stages to my research (and level of conviction):

1) 2005-2013.   What I did was (in hindsight) exploring consequences of the failure of quantum fault tolerance and, on the way, some mistakes in the logic of firmly believing that quantum computers could be built. But, as I often said at that time, I did not think my work then gave a reason for people to change their a priori beliefs.

2) 2013-2019.  Following my work with Guy Kindler I saw a clear scientific argument for why quantum computers will fail. (We first considered the special case of boson sampling and later I extended it in  greater generality.) Since that time, I regard my argument to be strong enough to change people a priori beliefs, and my level of conviction went up as well. But, as I said, it is not an ironclad argument.

3) 2019 – onward.  The experimental claims by Google and later by a group from Hefei, China would, if correct, refute my argument. So, naturally, this casts some doubts also in my mind. However, there are good technical reasons to doubt the fantastic claims by the Hefei group, and on that matter actually my 2014 paper with Kindler comes to play. The situation with the Google experiment is more delicate, but there are reasons to doubt their experimental claims as well.

As for a priori beliefs: In my view the situation is that it is hard to believe that quantum computers are not possible, but it is even harder to believe that quantum computers are possible 🙂 . So much experimental and theoretical research is needed before humankind will crack this puzzle.

Also, I was wondering if the retraction of the main paper about creating Majorana fermions ( kills topological computing’s hopes of getting us there?

No, the retraction of a single paper does not kill at all topological computing’s hopes. In fact, the researchers who found the mistake are hopeful that a successful experiment of that kind is possible and are also hopeful regarding further experimental steps towards topological quantum computing.

My general argument does extend to topological quantum computing and asserts that stable topological qubits are not possible.

Thanks for your interest and best wishes,  Gil Kalai

Additional comments: The (very nice) article appeared in August 2021 and (accurately) refers to my position: “Gil Kalai, a mathematician at the Hebrew University of Jerusalem in Israel, argued that the basic noise level in a quantum computer will always be too high, no matter how many qubits are available. ‘My analysis says that correcting quality errors will not be possible.’ ” The article quotes also Sabrina Maniscalco from the University of Helsinki in Finland who said: “Finding a cure for the effect of environmental noise is not only, in my opinion, a technological problem, but more conceptual and fundamental. I would say that I am optimistic, rather than confident”.

My debate with Aram Harrow over GLL started ten years ago. A lot has happened in these ten years! (Here is a comment from the debate on my assessment of the situation at that time.)

The researchers who took on themselves the thankless task of putting the Microsoft Majorana claims under scrutiny and found the mistakes are Sergey Frolov and Vincent Mourik. (See also Frolov’s commentary in “Nature” and this article in “Quanta Magazine”.) They drew important conclusions for the need of sharing raw data and other experimental details for such experiments.

For more details:  on my view regarding quantum computers see The Argument Against Quantum Computers – A Very Short Introduction (December 2020); and on Google’s supremacy experiment see Gil’s Collegial Quantum Supremacy Skepticism FAQ (November 2019).

This entry was posted in Computer Science and Optimization, Quantum and tagged , , , , , . Bookmark the permalink.

1 Response to Is HQCA Possible? A conversation with Michael Brooks

  1. Bhupinder Singh Anand says:

    Dear Professor Kalai,

    Please permit me to offer some foundational support for your thesis:

    1. By its very definition, any computational problem that can be solved by a classical computer can also be solved by a quantum computer. Conversely, any problem that can be solved by a quantum computer can also be solved by a classical computer.

    However, in the just submitted paper [An22c], I have shown that, and why, the Boolean Satisfiability Problem is not Turing-computable; hence uncomputable by any deterministic, non-deterministic, or even quantum (presumed based essentially on David Deutsch’s definition of a quantum Turing-machine) computer.

    2. Moreover, as I detail in my book [An21] (Section 4.B.c), such computability is, prima facie, what is implicitly appealed to in the 2019 claim (by a 78-member team of Google researchers) to have successfully reached the threshold of quantum supremacy by building a:

    `… high-fidelity processor capable of running quantum algorithms in an exponentially large computational space …’.

    Kind regards,


    [An21] … 2021. The Significance of Evidence-based Reasoning in Mathematics, Mathematics Education, Philosophy, and the Natural Sciences. Second edition, 2022 (Forthcoming). Limited First (Print) Edition archived at PhilPapers.

    [An22c] … 2022. Two non-classical interpretations of Goedel’s ‘formally’ unprovable, but ‘numeral-wise’ provable, PA-formula [(Ax)R(x)]: Why the Boolean Satisfiability Problem is not always decidable algorithmically in polynomial time. Submitted to the Journal of Applied Non-Classical Logics.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s