4
$\begingroup$

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:

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry, it seems some part of the question were poorly written. I'm aware that the oracle only outputs a single bit. I've clarified the question. $\endgroup$ – Jay S Apr 23 at 21:06
  • $\begingroup$ I guess that this is the part I have an issue with: 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$). $$$$ 1) The references I've linked seem to gloss over this point, are these just bad references or is this considered obvious for some reason? 2) It also feels like this trivials the problem entirely. A classical variant of XOR that leaks some arbitrary info would work just as well, would it not? $\endgroup$ – Jay S Apr 23 at 21:10
  • $\begingroup$ Those references will presumably have already worked through this calculation for earlier examples (all oracle problems work the same way), and so feel justified in glossing over the point. $\endgroup$ – DaftWullie Apr 24 at 7:41
  • $\begingroup$ It does not trivialise the problem. The oracle can be defined in exactly the same way for the classical problem (it is just a reversible implementation of the classical function, and that can also be classical) and it still requires n calls of the oracle, while the quantum version only requires a single call. $\endgroup$ – DaftWullie Apr 24 at 7:43
  • $\begingroup$ Suppose, we have a classical system and our oracle is implemented by a variation on XOR that simply outputs to both bits, ie |10> to |11> |00> to |00> and |11> to |00>. This can get the answer in one query by virtue of the fact that it writes s directly to the input bits (if we input all zeroes). I admit this seems kind of silly, but this is essentially what the CNOT oracle does in the Hadamard basis. $\endgroup$ – Jay S Apr 24 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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