From Kaye, Laflamme and Mosca's An Introduction to Quantum Computing:

Exercise 7.1.1 (Bernstein-Vazirani problem) Show how to find $\mathbf a \in Z_2^n$ given one application of a black box that maps $|\mathbf x\rangle |b\rangle \mapsto |\mathbf x\rangle |b\oplus \mathbf x \cdot \mathbf a\rangle$ for some $b\in\{0,1\}$.

I looked up in Google and other Stack Exchange problems to solve this one, but I think I can't understand the problem. What does it mean by "given one application of a black box, for some $b$"? I guess I have to use almost the same circuit as the Deutsch-Jozsa algorithm (like the picture below) with the second register as $|b〉$ instead of $|-〉$ but I am stuck at interpreting the exercise.

enter image description here

Could anyone please help me how to solve the exercise?


1 Answer 1


Yes, the situation is exactly the same as in the Deutsch-Jozsa algorithm: you can assume that you have access to a single, monolithic quantum gate that implements the mapping $$|\mathbf x\rangle |b\rangle \mapsto |\mathbf x\rangle |b\oplus \mathbf x \cdot \mathbf a\rangle \tag 1$$ that you've been given, i.e. exactly as in Deutsch-Jozsa with the particular choice of $f(\mathbf x)=\mathbf x \cdot \mathbf a$. There are two aspects of that exercise that are important:

  • The gate is a black box. That is, you can assume you have the gate $U$ acting as per $(1)$, but you have no other access to $\mathbf a$ or any other internal aspect of its operation.
  • You only get one single use of the gate. If you could use it multiple times, you could just scan over $\mathbf x$ by flipping one bit to 1 at a time, with the ancilla in $b=0$, and then measuring the ancilla, to get $\mathbf a$. The single-use prohibition means that you need to be cleverer than that.

Now, because the gate is so similar to the Deutsch-Jozsa formalism, you can just take the same circuit and ride on the same calculations, plugging in your particular $f$ into the state at the end. Your job is to figure out what measurements need to be done on that state to figure out what $\mathbf a$ is, and to prove that those measurements do indeed return the correct value.

  • $\begingroup$ Thank you for your answer. I think I have to use |b⟩ instead of |−⟩. However, then I can't analyze the circuit properly. What is the expression of the state after the second Hadamard gates? Also I am stuck at what measurement is to be used to figure out the correct value of 'a'.... Could you please explain in more detail? $\endgroup$
    – Keith
    Aug 29, 2017 at 13:47
  • $\begingroup$ @Keith No. $|b\rangle$ refers to either of the computational states; its action on $|x\rangle|-\rangle$ will in general produce an entangled state. As to your further questions, giving away the answer would completely devalue the exercise as a learning resource. As I said, you can use all of the existing formalism for the Deutsch-Jozsa formulation, so if either of the aspects you're asking about is unclear, that just means that you haven't understood Deutsch-Jozsa properly. $\endgroup$ Aug 29, 2017 at 13:51

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.