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?


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.