[Math] On mathematical arguments against Quantum computing

computability-theorycomputational complexitylo.logicquantum-computationreference-request

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some even built toy models for a quantum computer in the lab. For instance, see IBM's 50-qubit quantum computer.

However, some scientists are not that optimistic when it comes to the predicted potential advantages of quantum computers in comparison with the classical ones. They believe there are theoretical obstacles and fundamental limitations that significantly reduce the efficiency of quantum computing.

One mathematical argument against quantum computing (and the only one that I am aware of) is based on the Gil Kalai's idea concerning the sensitivity of the quantum computation process to noise, which he believes may essentially affect the computational efficiency of quantum computers.

Question. I look for some references on similar theoretical (rather than practical) mathematical arguments against quantum computing — if there are any. Papers and lectures on potential theoretical flaws of quantum computing as a concept are welcome.

Remark. The theoretical arguments against quantum computing may remind the so-called Goedelian arguments against the artificial intelligence, particularly the famous Lucas-Penrose's idea based on the Goedel's incompleteness theorems. Maybe there could be some connections (and common flaws) between these two subjects, particularly when one considers the recent innovations in QAI such as the Quantum Artificial Intelligence Lab.

Best Answer

Here are some references and following them a short answer.

A good reference for the current situation to start with is John Preskill's recent paper "Quantum Computing in the NISQ era and beyond" NISQ stands for "Noisy Intermediate Scale Quantum" and it is a very useful notion coined by Preskill who also coined the notion of "quantum supremacy" - the ability of quantum computers to perform certain computational tasks hundreds orders of magnitude better than classical computers. The crucial theoretical and experimental issue is to understand quantum devices in the NISQ regime.

As for my papers: The two mathematical theorems on which the argument against quantum computers is largely based, are from my paper Gaussian Noise Sensitivity and BosonSampling with Guy Kindler; In my ICM 2018 paper Three Puzzles on Mathematics, Computation, and Games the feasibility of quantum computers is the third puzzle (Sections 1.3, 1.4 and 4) and it is also related to the Benjamini-Kalai-Schramm notions of noise-stability and noise-sensitivity which is discussed in the second puzzle (Sections 1.2, 3). Another good source is my 2016 paper from the Notices of the AMS "The quantum computer puzzle" and its arxive extended version.

On the practical side, these works give clear predictions (see e.g. my ICM paper) for what we can expect from NISQ devices and, in particular, from quantum computers with 10-80 qubits that many try to build. Those predictions are sharply different from what experimentalists hope to achieve.

On the theoretical side we have a good argument for Scott Aaronson's point number 9. (This argument does not rely on error-correlation.) We also have a clear difference between classical and quantum computing, namely why the argument against quantum computing does not apply to classical computing.

My earlier work from 2006-2012 (See e.g. this paper) indeed studied correlation of errors. These works suggest that in the NISQ regime errors for a pair of entangled qubits will have substantial positive correlation. This is another interesting prediction for current and future NISQ devices. This is part of the theoretical picture because the value of the "fault tolerance threshold" in Scott's point 9 depends on such correlation.