1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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)


    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 &
    Last edited: Dec 11, 2013
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted