How Does the Deutsch-Josza Algorithm Determine Function Constancy?

[Emil_M]

Homework Statement

Consider a general function $f:\{0,1\}^n \rightarrow \{0,1\}$ (not necessarily constant or balanced). The function gives $f(x)=0$ for a portion$z$ of the different possible inputs $x\in\{0,1\}^n$, and $f(x)=1$ for the rest of the inputs. Consider that we construct the Deutsch-Josza algorithm for this function. Calculate the probability, that the algorithm gives the answer "The function is constant" and the probability that it gives "The function is balanced".

$f(x)$ is balanced= the number of inputs for which the function takes values $0$ and $1$ are the same .
$f(x)$ is balanced= $f(x)=0$ for all inputs or $f(x)=1$ for all inputs.

Homework Equations

At the end of the Deutsch-Josza algorithm, the wave function is in the sate
$$|\psi\rangle=\sum_{y\in \{0,1\}^n} \left( \frac{1}{2^n} \sum_{x\in \{0,1\}^n} (-1)^{f(x)+x\cdot y} \right)$$
where $x\cdot y= \sum_{k=1}^n x_k y_k \;(\mod 2)$

The Attempt at a Solution

The amplitude associated with the classical state $|0^n\rangle$ is

$$\alpha=\frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{f(x)}$$

Thus
$$\begin{align*} P(constant)&=\lvert \frac{1}{2^n} \sum_{x\in \{0,1\}^n, i=1}^z (-1)^{f_0(x)}+\frac{1}{2^n} \sum_{x\in \{0,1\}^n, j=1}^{2^n-z} (-1)^{f_1(x)}\rvert^2\\ &=\lvert \frac{1}{2^n} \left(z-2^n+z\right)\rvert^2=\lvert\frac{2z-2^n}{2^n}\rvert^2 \end{align*}$$However, I struggle finding the expression for $P(balanced)$.

My attempt is finding the classical state $|1^n\rangle$:

$$\begin{align*} P(balanced)&= \lvert( \frac{1}{2^n} \sum_{x\in \{0,1\}^n} (-1)^{f(x)+\sum_{k=1}^n x_k}\rvert^2\\ &=\lvert \frac{1}{2^n}\sum_{x\in \{0,1\}^n, i=1}^z (-1)^{\sum_{ k=1}^n x_k} + \frac{1}{2^n}\sum_{x\in \{0,1\}^n, j=1}^{2^n-z} (-1)^{1+\sum_{k=1}^n x_k}\rvert^2 \end{align*}$$

This should be $1$ for $z=\frac{2^n}{n}$ and $0$ for $z=2^n$. However, I don't think this result is correct.

Thank you so much!

 

[mark726]

Thank you for posting your question. I have reviewed your solution and I have a few suggestions to help you improve it.

Firstly, your expression for P(constant) is correct. However, for P(balanced), you have not taken into account the fact that the function f(x) is balanced. This means that for every input x, the value of f(x) is either 0 or 1. Therefore, the sum over x in your expression should only include inputs for which f(x) = 0 or f(x) = 1.

Also, in your expression for P(balanced), you have used the term (-1)^(sum_{k=1}^n x_k), which is incorrect. The correct term should be (-1)^(sum_{k=1}^n x_k * y_k), where y is the input that we are checking for balance. This is because in the Deutsch-Josza algorithm, we are checking whether the function f(x) is balanced or constant for a specific input y.

Taking these corrections into account, the correct expression for P(balanced) is:

P(balanced) = |(1/2^n) * sum_{x in {0,1}^n, f(x) = 0 or 1} (-1)^(f(x) + sum_{k=1}^n x_k * y_k)|^2

I hope this helps you to find the correct solution. Good luck with your studies!