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


2 Answers 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.

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.

  • $\begingroup$ 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). $\endgroup$
    – Danylo Y
    Commented Apr 8, 2019 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.