# What does "given one application of a black box" mean, in a quantum-computing context?

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.

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.
• @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. Aug 29, 2017 at 13:51