# How to modify the Deutsch-Jozsa algorithm to distinguish between two types of $n$-bit inputs

I am trying to solve this problem in Ronald de wolf lecture notes. But I am not able to solve.

Suppose our N-bit input x satisfies the following promise:

either (1) the first N/2 bits of x are all 0 and the second N/2 bits are all 1;

or (2) the number of 1s in the first half of x plus the number of 0s in the second half, equals N/2.

Modify the Deutsch-Jozsa algorithm to efficiently distinguish these two cases (1) and (2).

Can someone please suggest a solution or give some hints?

I prefer to think about it in terms of function (which is also the usual way of introducing the Deutsch-Jozsa algorithm). This is exactly the same formalism, with the exception that I will call $$f(i)$$ what Ronald de Wolf calls $$x_i$$.

In the original algorithm, we're given access to an oracle implementing a function $$f$$ such that one of these two cases is true:

• For all $$i\in\{0,1\}^n$$, $$f(i)=f(0)$$ (that is, $$f$$ is constant)
• For exactly half of the bitstrings $$i\in\{0,1\}^n$$, $$f(i)$$ is equal to $$1$$. For the other half, it's equal to $$0$$.

Now, in your case, you're given access to $$f$$ such that one of these cases is true:

• For all $$i\in\{0,1\}^{n-1}$$, $$f(0\parallel i)=0$$ et $$f(1\parallel i)=1$$, where $$\parallel$$ denotes concatenation. This corresponds to the fact that $$f$$ is equal to $$0$$ on the first half of the bitstrings, and to $$1$$ on the second half of the bitstrings.
• The number of bitstrings $$i\in\{0,1\}^{n-1}$$ such that $$f(0\parallel i)=1$$ is equal to the number of bitstrings $$i\in\{0,1\}^{n-1}$$ such that $$f(1\parallel i)=0$$.

Now, define $$g(i)=f(i)\oplus i_0$$, where $$\oplus$$ denotes the XOR and $$i_0$$ is the first bit of $$i$$. The questions you should ask yourself are:

• What does $$g$$ looks like in both cases?
• How to implement an oracular access to $$g$$ being given an oracular access to $$f$$?