# How to solve this Deutsch Jozsa variant?

You are given a function $$f : \{0,1\}^n \to \{0,1\}$$ and a quantum circuit, $$C$$, computing the signed implementation of $$f$$. Let $$I_0$$ be the input bit-strings of length $$n$$ where the first bit is $$0$$, and $$I_1$$ be the remaining ones (i.e., the first bit is $$1$$).

You are given the promise that $$f$$ is one of these two types:

1. $$f(x) = 0$$ for all $$x$$ belonging to $$I_0$$ and $$f(x) = 1$$ for all $$x$$ belonging to $$I_1$$

2. The total number of strings in $$I_0$$ for which $$f(x) = 1$$ plus the total number of strings in $$I_1$$ for which $$f(x)$$ is $$0$$ is $$2^{n-1}$$.

Give an algorithm (i.e., quantum circuit) to distinguish between these two cases by calling $$C$$ only once.

• Thanks @KAJ226 !! Commented Nov 13, 2020 at 17:52
• Is this a homework problem? If so, please add some of your own work to the bottom Commented Nov 13, 2020 at 19:02
• No it is not. I was reading notes of Ronald de Wolf to brush up my QC concepts and I found this problem. Intrigued by the problem I started solving it but couldn't get any idea on how to proceed. Commented Nov 13, 2020 at 19:22

I like this one!

Hint: Can you transform the function into another one that is closer to the type of functions Deutsch-Jozsa algorithm deals with?

Answer under spoiler, so as not to ruin the fun for others:

Implement the following phase oracle based on the oracle given for $$f(x)$$: $$g(x) = f(x)$$ if $$x \in I_0$$, and $$g(x) = 1 - f(x)$$ if $$x \in I_1$$. You can do that by applying the $$f(x)$$ oracle and then doing a Z gate on the first qubit.
Now you have one of the two cases:
1. $$g(x) = 0$$ for all $$x$$ (constant!)
2. The total number of strings for which $$g(x) = 1$$ equals $$2^{n-1}$$ (balanced!)
And this is exactly the Deutsch-Jozsa problem!

• Thank you so much @Mariia. That is really an elegant approach !! Commented Nov 13, 2020 at 21:30