Re:A query complexity breakthrough
by j2kun on Thursday June 18, 2015 @02:08PM
(#9740516)
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. 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
[2]: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86...