[johncolanduoni]

Martinis' group has laid out a plan to build a 49 qubit quantum computer that can solve a problem that is intractable for classical supercomputers with any known algorithm. If they pull it off we'll have the first provisional evidence that we can build quantum computers that can solve a problem classical computers cannot in a reasonable amount of time.

Caveats: it is possible there exists a superior classical algorithm that can solve the problem efficiently enough, and that we just haven't found it yet. It is also still within the realm of possibility that there exists an algorithm that can simulate any quantum computer with only polynomial slowdown, which would show quantum computers are not drastically faster for any problem.