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?


1 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$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.