Hidden shift problem as a benchmarking function

Question

I encountered the hidden shift problem as a benchmarking function to test the quantum algorithm outlined in this paper / arXiv (the problem also features here / arXiv).

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. \begin{align*} 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 \end{align*} 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$.

Answer 1

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.

Answer 2

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