Deutsch-Jozsa algorithm modification

1. Dec 11, 2013

shantan

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:

$$\sum \nolimits_{x \epsilon (0,1)^n} (-1)^{xy} = \begin{Bmatrix} &2^n &if &y=0^n \\ &0, &otherwise & \end{Bmatrix}$$

Last edited: Dec 11, 2013