Exact quantum algorithms have advantage for almost all Boolean functions

Andris Ambainis, Jozef Gruska, Shenggen Zheng

It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact q…