I encountered the hidden shift problem as a benchmarking function to test the quantum algorithm outlined in this paper (the problem also features here).
There are two oracle functions $f$, $f'$ : $\mathbb{F}_{2}^{n} \rightarrow \{ \pm 1 \}$ and a hidden shift string $s \in \mathbb{F}_{2}^{n}$. It is promised that $f$ is a bent (maximally non-linear) function, that is, the Hadamard transform of f takes values $ \pm 1$. It is also promised that $f′$ is the shifted version of the Hadamard transform of $f$, that is
$$f'(x \oplus s) = 2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (−1)^{x·y}f(y) \forall x \in \mathbb{F}_{2}^{n} $$
The oracles are diagonal $n$ qubit unitary operators such that $O_{f}|x \rangle = f(x) |x \rangle$ and $O_{f'}|x \rangle = f'(x) |x \rangle$ for all $x \in \mathbb{F}^{n}_{2}$.
It is stated that $|s⟩ = U|0^{n}⟩$, $U ≡ H^{\otimes n} O_{f′} H^{\otimes n} O_{f} H^{\otimes n}$. I am struggling with this calculation. Here's what I did.
$$H^{\otimes n} O_{f′} H^{\otimes n} O_{f} H^{\otimes n}|0^{n}\rangle$$ $$= H^{\otimes n} O_{f′} H^{\otimes n} 2^{−\frac{n}{2}}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) |x \rangle$$ $$= H^{\otimes n} O_{f′} ~2^{−n}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{x.y} |y \rangle $$ $$= H^{\otimes n} ~2^{−n} \sum_{x \in \mathbb{F}^{n}_{2}} f(x) \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{x.y} f'(y) |y \rangle $$ $$= 2^{−\frac{3n}{2}} \sum_{x \in \mathbb{F}^{n}_{2}} f(x) \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{x.y} f'(y) \sum_{z \in \mathbb{F}^{n}_{2}} (-1)^{y.z} |z \rangle $$
I am not sure whether I have the correct expression and if I do, I have no idea how to simplify this large expression to get $|s\rangle$.