# Why does this solution to the Bernstein-Vazirani problem use $(-1)^{f(x)}$

I am reading a solution to the Bernstein-Vazirani problem. For those unaware, the issue is to find a randomly selected $0 \leq a \lt 2^n$ given only a function $f(x) = a_0x_0 \oplus a_1x_1 \oplus ... = a \cdot x$ where $a_i$ and $x_i$ represent the ith bits of $a$ and $x$ respectively.

The solution starts out with an n-bit input register and 1-bit output register. The output register is initialized to

$$\textbf{HX}|0\rangle = \textbf{H}|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$$

The next part of the solution, the part I don't understand, is that the author says that $\textbf{U}_f$ applied to the conventional basis state $|x\rangle_n|y\rangle_1$ flips the value y if and only if $f(x) = 1$. Conceptually, this makes sense, but the author formalizes the above like so:

$$\textbf{U}_f |x\rangle_n \textbf{H}|1\rangle = \textbf{U}_f |x\rangle_n \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = (-1)^{f(x)} |x\rangle_n \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$$

I don't understand how multiplication by $(-1)$ is equivalent to flipping a bit here. To me, that would imply that the above is equal to (when $f(x) = 1)$

$$|x\rangle_n (-1)\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |x\rangle_n\frac{1}{\sqrt{2}}(-|0\rangle + |1\rangle)$$

This doesn't look like a bit flip because $-|0\rangle \neq |0\rangle$

What am I missing?

Is it because that $-|0\rangle$, while not equivalent to $|0\rangle$, is equally likely to produce a 0 classical bit when measured?

• – E.P.
Apr 19, 2018 at 10:25

Recall that for an arbitrary qubit $$|x\rangle$$, we have that:

$$H|x\rangle = \frac{1}{\sqrt{2}} (|0\rangle + (-1)^{x}|1\rangle)$$

So the Hadamard operator allows us to obtain superpositions from input qubits. Now the Bernstein-Vazirani quantum circuit (which is also the Deutsch-Josza circuit) starts by applying $$H^{\otimes n}$$ to the $$n$$-qubit input $$|0^{n}\rangle$$, which yields:

$$2^{-n/2} \sum_{x \in \{0, 1\}^{n}} |x\rangle$$

As $$0^{n} \cdot x = 0$$ for all $$x \in \{0, 1\}^{n}$$, we don't have any negative terms appear after applying the bank of Hadamards. This justifies the above sum.

Now we apply the $$U_{f}$$ gate to obtain: $$2^{-n/2} \sum_{x \in \{0, 1\}^{n}} (-1)^{f(x)} |x\rangle = 2^{-n/2} \sum_{x \in \{0, 1\}^{n}} (-1)^{a \cdot x} |x\rangle$$

Which is the result of applying $$H^{\otimes n}|a\rangle$$. Now the Hadamard operator is its own inverse, so applying: $$H^{\otimes n} \biggr( 2^{-n/2} \sum_{x \in \{0, 1\}^{n}} (-1)^{f(x)} |x\rangle = 2^{-n/2} \sum_{x \in \{0, 1\}^{n}} (-1)^{a \cdot x} |x\rangle \biggr) = |a\rangle$$

As desired.