3
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\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.