1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – glS ♦
    Sep 21, 2020 at 14:14

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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