Постоянная или сбалансированная функция

Дан оракул функции $f:\{0,1\}^n\to\{0,1\}$. Гарантируется, что $f$ либо постоянна, либо сбалансирована: на ровно половине входов она равна 0, а на остальных — 1. Требуется определить, какой из этих двух случаев имеет место. В квантовой постановке из §5.1 оракул — вентиль $B_b$ на $n+1$ кубитах:

$$B_b|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle.$$

Начальное состояние — $|0\rangle^{\otimes n}|1\rangle$; здесь $x$ — двоичная строка длины $n$.