# Measuring Deutsch-Jozsa in the Fourier Basis

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?

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