# Deutsch-Jozsa Misunderstanding

I fail to understand Deutsch-Jozsa algorithm. As wikipedia suggests: $${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$$. The function takes n-digit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all outputs or 1 on all outputs) or balanced (returns 1 for half of the input domain and 0 for the other half). The task then is to determine if {\displaystyle f}f is constant or balanced by using the oracle.

Question 1: If I use probabilistic algorithm on a normal computer, can't I just input once a single 0 in the oracle, then input once a single 1. And I am done.

I also read here: http://www.diva-portal.org/smash/get/diva2:840938/FULLTEXT01.pdf: Consider that Bob generates a list of arbitrary length from a balanced function. Then the list will contain equally many zeros and ones, thus if Alice draws a random element in the list it will be a zero or one with a probability of 1/2. If she draws two elements. then she can obtain the outcomes ”00”, ”01”, ”10” and ”11”, each with an equal probability of 1/4. If Alice now has to guess whether the function was constant or balanced, she will guess correctly half of the times. If she instead draws a third element the outcome will be a uniform probability distribution over the following possible outcomes ”000”, ”001”, ”010”, ”011”, ”100”, ”101”, ”110” and ”111”. Alice will now guess correctly six out of eight times.

Qurstion 2: So if she has ”001” (or eve "01"/"10") isn't that already a balanced function?

• please stick to one specific question per post. Also remember to upvote answers after accepting them. It would also greatly improve the post if you could use a meaningful title – glS Sep 21 '20 at 14:14

## 2 Answers

Regarding your first question, there are $$n$$ inputs to $$f$$ and the task is to determine if $$f$$ is constant or balanced (under the promise that it is one or the other); you can do this on a quantum computer with a single query to $$f$$. If $$n=1$$, then classically you can do as you suggest, input $$0$$ for one query, and input $$1$$ for another query, for a total of two queries, but the quantum computer still wins with only one query.

Regarding your second question, yes you are correct; if you ever classically get two outputs that differ, then (under the promise) you can be sure that the function is balanced. However, Deutsch-Josza notes that you can guarantee it's balanced with only a single query.

Classically you need at least two, and up to $$2^{n-1}+1$$, queries, but quantum-mechanically a single query suffices.

If you did not already, start by having a look to the Deutsch's algorithm, which is the single-qubit version of the Deutsch-Jozsa algorithm you are looking at.

Here you have some quick resources:

It is simpler than Deutsch-Jozsa and a good stepping stone.