Exact quantum query complexity of ${\mathrm{EXACT}}_{\mathrm{k},\mathrm{l}}^{\mathrm{n}}$

Andris Ambainis, Jānis Iraids, Daniel Nagaj

In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ inp…