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

Question

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?

Answer 1

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.