# Mapping $| y \rangle$ to $(-1)^{x \cdot y}| y \rangle$

I was checking some QC lecture notes by Ronald de Wolf and I came across this exercise that I can't solve.

Page 27 (pdf page 35), question 5, part b link: https://homepages.cwi.nl/~rdewolf/qcnotes.pdf

A slightly edited version:

Given some input input bitstring $$x \in \{0,1\}^N$$ and a unitary oracle $$$$O_{x}: |i\rangle = \begin{cases} (-1)^{x_i} |i\rangle & \text{if 1 \leq i \leq n}\\ |i\rangle & \text{if i=0} \end{cases}$$$$

Give a quantum algorithm that uses $$O$$ and to map $$| y \rangle \mapsto (−1)^{x·y} | y \rangle$$ for every $$y ∈ \{0, 1\}^N$$"

Can someone please suggest a solution or give some hints ?

I am thinking of applying the oracle twice, $$O_y O_x | y \rangle$$ Or maybe use a had $$: H O_x | y \rangle$$ but I am not sure if that works as intended we do get the $$(-1)^{x y}$$ but we also get some extra factor $$1/\sqrt{2^n}$$in the phase. I am not so sure which route to go...

Thanks

• What's a query to a bitstring? What information do you get from such a query? Commented Jun 12, 2022 at 4:33
• Are you able to solve it for $T=1$? Commented Jun 12, 2022 at 7:36
• @CraigGidney The condition about T is not the problem... It's how to build the mapping that I can't do. for the sake of conciseness, I edited the question to make it clearer without opening the long pdf. Commented Jun 12, 2022 at 15:59
• @TristanNemoz, please see the edited version, I hope it is clearer now without having to go through the lecture note and the previous chapter... Commented Jun 12, 2022 at 15:59
• @user206904 Okay I'll be more direct. Break the problem into cases and solve cases in order to understand the full solution. Solve the problem for $T=1$ before you try to solve it for arbitrary $T$. If that's still too hard, solve it for $T=1,n=1$. Then for $T=1,n=2$. Then $T=1,n=3$. Then $T=1,n=4$. And hopefully by then you see the pattern that lets you solve $T=1$. Then do $T=2$. Then do $T=3$. Then general $T$. Commented Jun 12, 2022 at 16:34