IBM just proved quantum computers can do things impossible for classical ones October 18, 2018 https://thenextweb.com/science/2018...-can-do-things-impossible-for-classical-ones/
The paper seems to be reformatted version of this freely available paper (they moved detailed things to sppl.). Haha, actually not, the author assumed quite restricted q-computer model which will be realized in current (or near-term) tech, this is why it's called "shallow". It appears while some previous studies on the SQCs focused more on quantum speed up w/ both theoretical & physical q-computer architecture, the author focused on what can't be achieved in c-computer w/ so far purely theoretical architecture. Another significance in this study somehow not mentioned in the article is they didn't use oracle, a hypothetical black-box func, but instead used a linear Boolean func in quadratic form so eliminated possibility that the internals of the oracle leads to efficient computation in c-comp. This is another meaning of "unconditional", not just a complexity-theoretic conjectures. So the study showed there's a practical (i.e. can be achieved in quite near future) case q-comp outperforms c-comp even w/out the conjectures or oracle. TBH IDK why this is "a watershed moment" (not trying to belittle it, rather I recognize importance of this kind of theoretical work). I don't feel like this significantly changes the direction of studies in the field - it may be end up getting a somewhat similar position to Ergodic theory in statistical mechanics or provable security in cryptography - but I may be wrong. But, allow me for dirty talk, this will be useful for students to convince officials to give more budget.
