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

Question

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?

Answer 1

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$?