Proof that Quantum Computers Outperform Classical Computers

(TechCrunch) Sergey Bravyi of IBM Research, David Gosset of the University of Waterloo’s Institute for Quantum Computing and Robert König of the Institute for Advanced Study and Zentrum Mathematik, Technische Universität München have published a paper proving that a quantum computer with a fixed circuit depth is able to outperform a classical computer that’s tackling the same problem because the classical computer will require the circuit depth to grow larger, while it can stay constant for the quantum computer.
The question the researchers here asked was if constant-depth quantum circuits can solve a computational problem that constant-depth classical circuits cannot? The researchers showed that even a shallow quantum computer can easily outperform a classical computer in solving this problem.