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?