$$ \newcommand{\P}{\text{P}} \newcommand{\BQP}{\text{BQP}} \newcommand{\BPP}{\text{BPP}} \newcommand{\PSPACE}{\text{PSPACE}} \newcommand{\SP}{\text{#P}} $$

Breaking News: IBM’s Team Proved Quantum Computers Do ‘Impossible’ Things

Update: See this comment by @quantum_aram. I modified the wording of the post to reflect that this is what I think. As mentioned in the comment, it is wholly possible that there exist people for whom computation means constant-depth computation and problem means relational problem, and for them the result of Bravyi et al. unconditionally shows that quantum computers are better than classical computers.

I really don’t like to rant about the press good results receive because the results themselves are great—but the way traditional press is interpreting this is insane.

Firstly, this is one of those late reactions from the press. (BTW did you know that during the crash of 1929 the ticker tape was hours late!) This paper has been on the arXiv since April 2017 and was the subject of a plenary lecture at QIP 2018.

Secondly, the result is that there exists a relational problem which can be solved by bounded fan-in, bounded fan-out, constant-depth quantum circuits but cannot be solved by bounded fan-in, unbounded fan-out, sub-logarithmic-depth classical circuits. Yes, you heard me right, there is no oracle involved. This is an amazing result!!

But, here are two reasons why I think this result does not constitute a proof that (general) quantum computers are better than (general) classical computers:

  1. It compares constant-depth quantum circuits to sub-logarithmic depth classical circuits
  2. It concerns relational problems

I think a true proof that quantum computers are better than classical computers would need to show that there exists a decision problem that can be decided by bounded-error polynomial-size quantum circuits but cannot be decided by bounded-error polynomial-size classical circuits. Succinctly, $\BQP \supsetneq \BPP$. But, back in 1997, Ethan Bernstein and Umesh Vazirani showed that $\BQP \subseteq \P^\SP$ so a proof of this would also show that $\P \neq \PSPACE$. Going back, this result of Sergey Bravyi, David Gosset, and Robert Koenig takes us many steps toward this holy grail by introducing some brilliant techniques but doesn’t go all the way.

For more on the result I highly recommend Ashley Montanaro’s prespective and the article itself. For a slight improvement of this result and an application to certified randomness expansion, see Matthew Coudron, Jalex Stark, and Thomas Vidick’s super recent article.