Partial Boolean functions with exact quantum 1-query complexity

Guoliang Xu, Daowen Qiu

We provide two sufficient and necessary conditions to characterize any $n$-bit partial Boolean function with exact quantum 1-query complexity. Using the first characterization, we…