Is the Bernstein-Vazirani algorithm dependent on the specific behavior of the oracle?

Question

My understanding of the Bernstein-Vazirani algorithm is as follows:

1. We have a black box oracle with secret string $s$. The black box does $$f(x) =s\cdot{x}=(\sum_1^n s_i\cdot{x_i})$$

2. We run each qubit through a Hadamard gate first, then through the oracle:

3. If $s_i = 0$, nothing happens and the ith qubit is still in the $|+\rangle$ state. If $s_i = 1$, the $i$-th qubit picks up a phase and is now in the $|-\rangle$ state.

4. We run ignore the output and run the inputs qubits through another Hadamard gate, and now we've recovered s with only a single query!

---

The part I don't understand is that nothing about the oracle (1) promises this phase kickback will occur. The references I've seen seem to implicitly assume this, why are they assuming this behavior?

Even the first reference, which describes a CNOT-gate based implementation of this oracle, only does so after the solution — which to me suggests that the implementation is a detail rather than a necessary feature of the problem.

To clarify, I'd have no issues if the oracle was explicitly stated to have this phase kickback behavior, but its seems like this condition is being taken for granted.

---

References:

• CMSC 33001: Novel Computing Architectures and Technologies (Lecture 8)
• Lecture 18, Tues March 28: Bernstein-Vazirani, Simon (Scott Aaronson)
• Lecture 4: Elementary Quantum Algorithms (Dieter van Melkebeek)
• CSE 599d - Quantum Computing: The Recursive and Nonrecursive Bernstein-Vazirani Algorithm (Dave Bacon)

Answer 1

The whole point of an oracle-based algorithm is that it does depend on the promised structure of the oracle. For Bernstein-Vazirani, it is assumed that the oracle acts as $$ |x\rangle|y\rangle\rightarrow |x\rangle|y\oplus (x\cdot s)\rangle. $$ That is the fundamental starting point (and is just the reversible implementation of $x\cdot s$). If you didn't have an oracle that did this, all bets would be off (this is one of the key reasons why we haven't proven that quantum computation is faster that classical - the only proven speedups are with respect to specific oracles, but that can never eliminate the possibility of different oracles offering different results).

Notice that this definition of the oracle involves $n+1$ qubits, the $n$ qubits of input and one ancilla qubit. The way that you've described the functionality does not quite fit with this. The way that you've written it seems to suggest that you're expecting $|x\rangle\mapsto|x\oplus s\rangle$. This is not the case. Indeed, if that were the case, then what you'd actually have to state for the oracle is

1. We have a black box oracle with secret string s. For each bit, if $s_i=1$ then 0 is mapped to 1 and 1 is mapped to 0. If $s_i=0$ then it is unchanged.
2. If $s_i=1$ then it also maps $|+\rangle$ to $|+\rangle$ and $|-\rangle$ to $-|-\rangle$.

This is the result of linearity: if $|0\rangle\mapsto|0\rangle$ and $|1\rangle\mapsto|1\rangle$, then this is the identity map; whatever you input is what you output. Meanwhile, if $|0\rangle\mapsto|1\rangle$ and $|1\rangle\mapsto|0\rangle$, then it must be that $(|0\rangle+|1\rangle)\mapsto(|1\rangle+|0\rangle)$ and $(|0\rangle-|1\rangle)\mapsto(|1\rangle-|0\rangle)$. Moreover, determining $s$ would be trivial; we'd just input $x=0$, and read the output.

Instead, what you actually have to do is make sure that you input the state $(|0\rangle-|1\rangle)/\sqrt{2}$ on the ancilla qubit. In doing so, the state of the ancilla qubit will not change. So, we can describe the net effect on just the $n$ other qubits as being $$ |x\rangle\mapsto (-1)^{s\cdot x}|x\rangle. $$ This is the phase kick-back that you mention. Notice that if all you do is use basis states, then the phase is undetectable. However, if you input the state $|+\rangle^{\otimes n}$, as you mention, then you do indeed get the output $H^{\otimes n}|s\rangle$.