# Deutsch-Josza algorithm

1. Jan 21, 2016

### Emil_M

1. The problem statement, all variables and given/known data
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.

2. Relevant 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)$

3. 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!

2. Jan 26, 2016