Let $f$ be a function from $N$ bits to one bit, where $f$ is either constant or balanced. Consider the Deutsch-Jozsa algorithm, where each of the $N$ output qubits is measured in the Fourier basis $\{|+\rangle, |−\rangle\}$. I'm meant to show that the function $f$ is constant iff all the measurements give the outcome measure $|+\rangle$

Here's my attempt at the forward's direction:

If $f$ is constant, $V_f e_0 = e_0$ or $-e_0$

$$|\langle +|e_0\rangle|^2 = |\frac1{\sqrt n}\sum_{x}\langle +|x\rangle|^2 = |\frac1{\sqrt{2n}}\sum_{x} \sum_{y=0,1}\langle y|x\rangle|^2 = |\sqrt{2/n}|^2 = \frac{2}{n},$$

which isn't equal to 1? Where am I going wrong? Also, how would I solve the backward direction?

  • $\begingroup$ In the maths, you appear to be describing the measurement on a single qubit rather than $N$ qubits? $\endgroup$
    – DaftWullie
    Feb 28, 2022 at 9:54


Your Answer

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