Exact quantum query complexity for total Boolean functions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We will show that if there exists a quantum query algorithm that exactly computes some total Boolean function f by making T queries, then there is a classical deterministic algorithm A that exactly computes f making O(T^3) queries. The best know bound previously was O(T^4) due to Beals et al.