# Hidden shift problem as a benchmarking function

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$$.

Well, you can simplify $$H^{\otimes n} O_{f} H^{\otimes n}|0^{n}\rangle = H^{\otimes n} 2^{−\frac{n}{2}}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) |x \rangle =$$ $$= ~2^{−n}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{x.y} |y \rangle = ~2^{−n}\sum_{x \in \mathbb{F}^{n}_{2}}\sum_{y \in \mathbb{F}^{n}_{2}} f(x) (-1)^{x.y} |y \rangle =$$ $$= ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}}\left(~2^{−\frac{n}{2}}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) (-1)^{x.y} \right) |y \rangle = ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} f′(y\oplus s)|y \rangle$$

On the other hand $$O_{f'} H^{\otimes n} |s\rangle = O_{f'} ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{s.y}|y \rangle = ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{s.y}f'(y)|y \rangle$$

Now, if $$|s\rangle = H^{\otimes n} O_{f′} H^{\otimes n} O_{f} H^{\otimes n} |0\rangle$$ then $$O_{f′} H^{\otimes n} |s\rangle = H^{\otimes n} O_{f} H^{\otimes n} |0\rangle$$.
Hence it must be $$~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} f′(y\oplus s)|y \rangle = ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{s.y}f'(y)|y \rangle ,$$ i.e. $$f′(y\oplus s) = (-1)^{s.y}f'(y)$$

Well, the last equality just can't be true for a general bent $$f'$$ and $$s$$,$$y$$, because you can deduce $$f'(y)=f'(s)$$, hence $$f'$$ must be constant.

So, there is a mistake somewhere. Probably with notations or definitions. A deeper look is needed.

EDIT.
Ok, after some digging I found a mistake :) Authors of the first paper not quite carefully restated results of the source paper (your second link). In fact, $$f'$$ must be a Hadamard transform of the shifted $$f$$, and not a shift of the Hadamard transform of $$f$$! That is, it must be $$f'(x) = ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{x.y}f(y\oplus s)$$ or, equivalently, by changing $$x$$,$$y$$ $$f'(y) = ~2^{−\frac{n}{2}} \sum_{x \in \mathbb{F}^{n}_{2}} (-1)^{x.y}f(x\oplus s)$$

With this correct $$f'$$ we have $$~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}}\left(~2^{−\frac{n}{2}}\sum_{x \in \mathbb{F}^{n}_{2}} f(x) (-1)^{x.y} \right) |y \rangle = ~2^{−\frac{n}{2}} \sum_{y \in \mathbb{F}^{n}_{2}} (-1)^{y.s}f′(y)|y \rangle$$ and everything coincides (in the context of my previous calculations).

Your calculations are correct, however, there are two issues: first, note that the promise on the dual bent function is actually not $$f^\prime(x\oplus s) = 2^{-\frac{n}{2}} \sum_{y \in \mathbb{F}_2^n} (-1)^{xy} f(y) , \; \forall x \in \mathbb{F}_2^n$$ as stated. Instead you really want to define here the dual as in my paper https://arxiv.org/abs/0811.3208 as $$f^\prime(x) = 2^{-\frac{n}{2}} \sum_{y \in \mathbb{F}_2^n} (-1)^{xy} f(y) , \; \forall x \in \mathbb{F}_2^n.$$ Note that the definition of the dual is independent of the hidden shift $$s$$.

The second issue is that in your calculation $$H^{\otimes n} {\cal O}_{f^\prime} H^{\otimes n} {\cal O}_{f} H^{\otimes n} |0\rangle$$ you used the unshifted version of $$f$$. Hence, the outcome is the shift $$s=(0,\ldots,0)$$, corresponding to the unshifted function (which is a perfectly valid input to the problem of course). Indeed, your second to last line can be simplified to $$H^{\otimes n} 2^{-n/2} \sum_{y \in \mathbb{F}_2^n} f^\prime(y) f^\prime(y) |y\rangle = H^{\otimes n} 2^{-n/2} \sum_{y \in \mathbb{F}_2^n} |y\rangle = |0 \ldots 0\rangle,$$ as it should be for hidden shift $$s=(0,\ldots, 0)$$.

For a general hidden shift $$s\in \mathbb{F}_2^n$$, the calculation is as follows. Denote by $$g(x) = f(x\oplus s)$$. Then $$H^{\otimes n} {\cal O}_{f^\prime} H^{\otimes n} {\cal O}_{g} H^{\otimes n} |0\rangle$$ $$= H^{\otimes n} {\cal O}_{f^\prime} H^{\otimes n} 2^{-n/2} \sum_{x\in \mathbb{F}_2^n} f(x\oplus s)|x\rangle$$ $$= H^{\otimes n} {\cal O}_{f^\prime} 2^{-n} \sum_{y \in \mathbb{F}_2^n} \left( \sum_{x \in \mathbb{F}_2^n} (-1)^{xy} f(x\oplus s) \right) |y \rangle$$ $$= H^{\otimes n} {\cal O}_{f^\prime} 2^{-n} \sum_{y \in \mathbb{F}_2^n} (-1)^{ys} \left( \sum_{x \in \mathbb{F}_2^n} (-1)^{xy} f(x) \right) |y \rangle$$ $$= H^{\otimes n} {\cal O}_{f^\prime} 2^{-n/2} \sum_{y \in \mathbb{F}_2^n} (-1)^{ys} f^\prime(y) |y\rangle$$ $$= H^{\otimes n} 2^{-n/2} \sum_{y \in \mathbb{F}_2^n} (-1)^{ys} f^\prime(y) f^\prime(y) |y\rangle$$ $$= H^{\otimes n} 2^{-n/2} \sum_{y \in \mathbb{F}_2^n} (-1)^{ys} |y\rangle$$ $$= |s\rangle,$$ as desired.

• I think they redefined $f$ to be your $g$, and $f'$ to be composition of the dual operation and the shift applied to $f$. But they took composition in the wrong order (it must dual of the shifted $f$, not shift of the dual). – Danylo Y Apr 8 '19 at 8:17