Bernstein–Vazirani problem in book as exercise

Question

I´ve solved the Exercise 7.1.1 (Bernstein–Vazirani problem) of the book "An introduction to quantum computing" (Mosca et altri). The problem is the following:

Show how to find $a \in Z_2^n$ given one application of a black box that maps $|x\rangle|b\rangle \to |x\rangle |b \oplus x · a\rangle$ for some $b\in \{0, 1\}$.

I´d say we can do it like this:

• First i go from $|0|0\rangle \to \sum_{i \in \{0,1\}^n}|i\rangle| + \rangle$ using QFT and Hadamard
• Then I apply the oracle: $$ \sum_{i \in \{0,1\}^n}(-1)^{(i,a)} |i\rangle| + \rangle $$
• Then I read the pase with an Hadamard (since we are in $Z_2^n$ our QFT is an Hadamard) $$ |a\rangle |+ \rangle $$

I think is correct. Do you agree?

Answer 1

This is not correct: you need to use the state $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$ instead of $|+\rangle$.

The important thing is that you've missed showing how the black box map that you've stated gives the oracle output that you've stated. To see this, apply the map on $$ |x\rangle|+\rangle\mapsto|x\rangle(|0\oplus x\cdot a\rangle+|1\oplus x\cdot a\rangle)/\sqrt{2}=|x\rangle(|0\rangle+|1\rangle)/\sqrt{2}. $$ When the $|+\rangle$ state is there, you get no phase. Meanwhile, with the $|-\rangle$ state, $$ |x\rangle|-\rangle\mapsto|x\rangle(|0\oplus x\cdot a\rangle-|1\oplus x\cdot a\rangle)/\sqrt{2}=\left\{\begin{array}{cc} |x\rangle(|0\rangle-|1\rangle)/\sqrt{2} & x\cdot a=0 \\ |x\rangle(|1\rangle-|0\rangle)/\sqrt{2} & x\cdot a=1\end{array}\right.. $$ This can simply be written as $(-1)^{x\cdot a}|x\rangle|-\rangle$.