1
$\begingroup$

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

Thanks

Improve this question
$\endgroup$
5
  • $\begingroup$ What's a query to a bitstring? What information do you get from such a query? $\endgroup$
    – Tristan Nemoz
    Jun 12, 2022 at 4:33
  • $\begingroup$ Are you able to solve it for $T=1$? $\endgroup$
    – Craig Gidney
    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
    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
    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$
    – Craig Gidney
    Jun 12, 2022 at 16:34

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.