Скрытая строка Бернштейна — Вазирани

В задаче Бернштейна — Вазирани доступен оракул для булевой функции $f:\{0,1\}^n\to\{0,1\}$. Известно, что существует строка $s\in\{0,1\}^n$, для которой при любом $x$ выполнено $f(x)=s\cdot x\bmod2$. Требуется найти $s$.

(a) Предложите детерминированный алгоритм с $n$ запросами.

(b) Докажите, что любому классическому алгоритму, в том числе рандомизированному, требуется $\Omega(n)$ запросов.

(c) Постройте квантовый алгоритм с единственным запросом. Подсказка. Вентили Адамара.