2
$\begingroup$

What are the minimum and maximum number of inputs you would need to check to know whether this 4-bit classical Deutsch-Jozsa oracle is balanced or constant?

$\endgroup$
4
$\begingroup$

Well, the best case scenario corresponds to the minimum tries and worst case to the maximum. Let us first look at the best case.

Imagine you make 2 queries to the DJ oracle and you get different outputs. What does this imply? It means your oracle must be balanced because you have different outcomes for 2 different queries. Since in some scenario you can distinguish the nature of the oracle, the minimum tries are 2.

Now, let us look at the worst case. Instead of taking 4, let's say we have an n-bit oracle. For this oracle you have $2^n$ different inputs. Imagine that you have made $2^{n-1}$ queries with distinct bit strings and got the same result i.e. either all 0s or 1s. At this point, you still can not comment on the nature of the function whether it is balanced or constant as it may be so that it has value 1 or value 0 for all the bit strings you input.

This implies that you must need atleast 1 more query to test whether it is balanced or constant. Thus, in this worst case scenario, you would need at max $2^{n-1} + 1$ number of queries.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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