Comments on Two Recent Theoretical Quantum Computing Research Papers



Two theoretical quantum computing papers have been recently published that have received some notice in the popular press.  We would like to comment on them because although they are interesting from a theoretical standpoint, they have minimal impact on any quantum computing commercialization activities that are underway.

The first paper is by Urmila Mahadev from University of California, Berkeley.  She has found a way to perform verification that a quantum algorithm running on a quantum computer is performing correctly for those problems that are too large for a classical computer to process.  Her solution is quite unique because it makes use of a classical encryption algorithm called Learning With Errors (LWE) that was originally developed for post-quantum encryption applications. Post-quantum encryption algorithms are classical algorithms that cannot be broken with a quantum computer because they don’t rely upon factoring large numbers.  For more details you can read her arXiv paper here and a article on the research written in Quanta Magazine here.

The second paper is titled “Quantum advantage with shallow circuits” written by scientists from IBM Research, University of Waterloo’s Institute for Quantum Computing, and the Technical University of Munich.  These researchers have developed a theoretical proof that for certain problems showing that the number of steps needed to solve the problem with a quantum computer was independent of the problem size whereas the number of steps would grow logarithmically with the size on a classical computer. This advantage has been widely assumed by quantum researchers for many years, but now this paper provides a formal proof.  For more details on this, you can view the IBM blog article describing this research or you can view the abstract of the paper in Science magazine (full text if you have a subscription) here.

It is important to reiterate that these papers are theoretical analyses.  As such, they represent significant progress in the theory of quantum computing.  But it may be many years, if ever, that the algorithms outlined in these papers are run on a real quantum computer.  Some articles in the popular press may mislead one to assume that these algorithms are already running on a quantum computer and that the magic milestone of quantum advantage has been reached. But before we declare anything like that we would want to see that success was achieved on a real quantum machine and not a simulation or a theoretical analysis.