Optimal one-shot quantum algorithm for EQUALITY and AND

Andris Ambainis, Janis Iraids

We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to \{0,1\}$ on an input $x\in\{0,…