Indexed on: **11 Aug '16**Published on: **21 Jun '16**Published in: **Computational Complexity**

Abstract This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\) -variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\) , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N} \right)}\) for a constant \({c > 0}\) . This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\) : \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N} \right)}\) . In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.AbstractThis paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\) -variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\) , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N} \right)}\) for a constant \({c > 0}\) . This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\) : \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N} \right)}\) . In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor. \({\mathcal{F}}_{N,M}\) \({\mathcal{F}}_{N,M}\) \({N}\) \({N}\) \({M (1\le M \le 2^{N}/2)}\) \({M (1\le M \le 2^{N}/2)}\) \({\mathcal{F}}_{N,M}\) \({\mathcal{F}}_{N,M}\) \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N} \right)}\) \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N} \right)}\) \({c > 0}\) \({c > 0}\) \({\mathcal{F}}_{N,M}\) \({\mathcal{F}}_{N,M}\) \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N} \right)}\) \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N} \right)}\) \({\mathcal{F}}_{N,M}\) \({\mathcal{F}}_{N,M}\) \({\Theta(N)}\) \({\Theta(N)}\)