1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Deutsch-Jozsa algorithm modification

  1. Dec 11, 2013 #1
    1. The problem statement, all variables and given/known data

    Suppose we have a function F: {0,1}^n -> {0,1} that satisfy the following promise: either

    1)F evaluates to 0 on the first 2^(n-1) inputs and to 1 on the second 2^(n-1) inputs (inputs are in lexicographical order)

    OR

    2)the number of evaluations to 0 in the first 2^(n-1) inputs equals 2^(n-2) and the number of evaluations to 1 on the seconds 2^{n-1} inputs bits equals to $2^(n-2).

    2. Relevant equations

    Modify the Deutsch-Jozsa algorithm to efficiently distinguish between the two cases.

    3. The attempt at a solution

    We know that DJ algorithm can be used for solving this problem:
    Having a unknown one-bit function f from and over Z2, find if the function is balanced or not (i.e. has the same number of 1 or 0).

    Perhaps i shoudld put some Hadamard gates on the input line to entangle all the qubits, but it's just an intuition.

    I think that this lemma should also be used:

    [tex]\sum \nolimits_{x \epsilon (0,1)^n} (-1)^{xy} = \begin{Bmatrix}
    &2^n &if &y=0^n \\
    &0, &otherwise &
    \end{Bmatrix}
    [/tex]
     
    Last edited: Dec 11, 2013
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Deutsch-Jozsa algorithm modification
Loading...