How to solve this Deutsch Jozsa variant?

Question

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.

Answer 1

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!