Exact quantum query complexity for total Boolean functions
Abstract
Description
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.
5 pages, corrected grammar, some comments added
5 pages, corrected grammar, some comments added