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.

  • $\begingroup$ Thanks @KAJ226 !! $\endgroup$ Nov 13, 2020 at 17:52
  • $\begingroup$ Is this a homework problem? If so, please add some of your own work to the bottom $\endgroup$
    – C. Kang
    Nov 13, 2020 at 19:02
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 13, 2020 at 19:22

1 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!

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

Your Answer

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

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