Yes. They refuted two conjectures 1. From 1998 [1] that the biggest gap in this model between quantum and classical was quadratic. (they got quartic) 2. From

Yes. They refuted two conjectures 1. From 1998 [1] that the biggest gap in this model between quantum and classical was quadratic. (they got quartic) 2. From 1984 [2] that the biggest randomized/classical gap was something like N^0.75 (they got quadratic) The reason I call these "major" is perhaps not exciting to people outside of academia: smart people tried to do better than [1] and [2] but couldn't for > 10 years. These works definitely deepen our theoretical understanding of the differences between quantum/randomized/classical computing. But you have to take it with the grain of salt that a major breakthrough is relative to the incentives and motivations of academic researchers. [1]: http://arxiv.org/abs/quant-ph/9802049 http://arxiv.org/abs/quant-ph/9802049 [2]: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86...