Understanding the output of a Deutsch-Jozsa circuit

Question

I'm looking at the Deustch-Jozsa algorithm. While reading this Qiskit tutorial. I didn't understand what the presented result in plot mean. That is, why the output 1111 means a balanced function? What would we expect from a constant function?

I don't know if my question is well explained, if it's not please let me know, and I improve this question.

Answer 1

After the application of the Hadamard sandwitch along with the intermediate oracle, as explained here,

$\begin{aligned} \lvert \psi_3 \rangle & = \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)} \left[ \sum_{y=0}^{2^n-1}(-1)^{x \cdot y} \vert y \rangle \right] \\ & = \frac{1}{2^n}\sum_{y=0}^{2^n-1} \left[ \sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x \cdot y} \right] \vert y \rangle \\ & = \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x \cdot \textbf{0}} \vert 0 \rangle ^{\otimes n} + \frac{1}{2^n}\sum_{y=1}^{2^n-1} \left[ \sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x \cdot y} \right] \vert y \rangle \\ & = \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} \vert 0 \rangle ^{\otimes n} + \frac{1}{2^n}\sum_{y=1}^{2^n-1} \left[ \sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x \cdot y} \right] \vert y \rangle \end{aligned}$

$\implies$ if we measure the first $n$ qubits, the probability of measuring $\vert 0 \rangle ^{\otimes n}$ $\quad \quad = P_{\vert 0 \rangle ^{\otimes n}} = \left\lvert \frac{1}{2^n}\sum_\limits{x=0}^{2^n-1}(-1)^{f(x)} \right\rvert^2$

Now, when the function $f(x)$ is a constant, we have either of two following cases:

• $f(x)=1$, $\forall{x} \in \{0,\ldots, 2^{n}-1\}$ $\implies (-1)^{f(x)}=-1,\;\forall{x} \implies P_{\vert 0 \rangle ^{\otimes n}}=\left\lvert \frac{1}{2^n}\sum_\limits{x=0}^{2^n-1}(-1) \right\rvert^2=\lvert\frac{1}{2^n}.(-2^n)\rvert^2=(-1)^2=1$
• $f(x)=0$, $\forall{x} \in \{0,\ldots, 2^{n}-1\}$ $\implies (-1)^{f(x)}=1,\;\forall{x} \implies P_{\vert 0 \rangle ^{\otimes n}}=\left\lvert \frac{1}{2^n}\sum_\limits{x=0}^{2^n-1}(1) \right\rvert^2=\lvert\frac{1}{2^n}.(2^n)\rvert^2=(1)^2=1$

Hence, whenever the function $f(x)$ is a constant, we measure the first $n$ qubits as $\vert 0 \rangle ^{\otimes n}$ with probability $1$, i.e., $f(x)$ is a constant function if we measure $00\ldots 0$ (all $0$s), otherwise $f(x)$ is a balanced function (by assumption).

Also, arguing in another way, when $f(x)$ is balanced, exactly half of $(-1)^{f(x)}$ values will be $1$ and the rest half will be $-1$, s.t., $\sum_\limits{x=0}^{2^n-1}(-1)^{f(x)}=0$, hence, $P_{\vert 0 \rangle ^{\otimes n}} = \left\lvert \frac{1}{2^n}\sum_\limits{x=0}^{2^n-1}(-1)^{f(x)} \right\rvert^2=0$, i.e., probability of measuring all zeros will be $0$, i.e., measurement will never result in all zeros (will contain at least one $1$ qubit).

Answer 2

In the Deutsch-Jozsa algorithm, if the function is constant, you are guaranteed to get the outcome 000...0. If the function is balanced, you are guaranteed not to get the answer 000...0. Since you got 1111, you did not get 0000 and so the function was balanced.

Answer 3

The controlled-Z gates happen to be the correct type of gates that can output an instant cleanly separable result with probability 1 for the Deutsch-Jogza problem:

whereas if the controlled-Z gates are vanished

This means a single measurement is $q_0$ can determine whether $q_8$ is constant ($q_0 = 0$) or balanced ($q_0 = 1$).

Once the correct circuit is found, analysis can be performed to reason why the circuit works.