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 \begin{equation} 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} \end{equation}

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


  • $\begingroup$ What's a query to a bitstring? What information do you get from such a query? $\endgroup$
    – Tristan Nemoz
    Commented Jun 12, 2022 at 4:33
  • $\begingroup$ Are you able to solve it for $T=1$? $\endgroup$ Commented Jun 12, 2022 at 7:36
  • $\begingroup$ @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. $\endgroup$
    – user206904
    Commented Jun 12, 2022 at 15:59
  • $\begingroup$ @TristanNemoz, please see the edited version, I hope it is clearer now without having to go through the lecture note and the previous chapter... $\endgroup$
    – user206904
    Commented Jun 12, 2022 at 15:59
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Jun 12, 2022 at 16:34


Your Answer

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

Browse other questions tagged or ask your own question.