Can there be different gate implementations of same oracle implementation?

Question

I have been reading about Bernstein-Vazirani Algorithm, and it uses what is known as a phase oracle. Basically, it is CNOT gate with several controls attached to the ancilla qubit $|-\rangle$ (it is discussed in detail over here link) in the circuit what the Oracle $O$ does is that

$$O |+\rangle^{\otimes N}|-\rangle\text{ }=\text{ }|+-+--\dots\rangle|-\rangle$$

by the first ket on the R.H.S I mean that whichever ket from the input acts as a control, it flips the state from $|+\rangle$ to $|-\rangle$ when it comes out as output from the oracle. Note: Ancilla plays no role in computation.

However, I do not understand why do we need CNOT gates and ancilla (I am aware of the reversibility criterion of quantum circuits). My point is that why can't this oracle be implemented by $Z$ and $I$ (Identity) gates. $Z$ gates placed at those indices of the input ket which acted as a control for the previous version of the oracle and $I$ gates placed at the ones which did not act as a control. We then have for a new implementation of the same oracle

$$O'|+\rangle^{\otimes N}=|+-+--\dots\rangle$$

This new oracle implementation is also reversible as it is made of $Z$ and $I$ gates. Moreover, it does not need ancilla. Then why is it not discussed in standard textbooks? Am I wrong somewhere?

Answer 1

I am answering my own question as I found an answer.

The answer is affirmative, that the standard phase oracle made of CNOT gates and an ancilla qubit can be replaced by Z and I gates by discarding the ancilla.

The oracle ($U_f$) in the BZ alogorithm follows:

$$|x\rangle|b\rangle \stackrel{U_{f}}{\rightarrow}|x\rangle|y \oplus f(x)\rangle \equiv|x\rangle|b \oplus(a \cdot x \bmod 2)\rangle=(-1)^{f_{a}(x)}|x\rangle|b\rangle$$

If we consider another oracle ($U_a$), forgetting the last ancilla qubit,

$$|x\rangle_{\rightarrow}^{U_{a}}(-1)^{f_{a}(x)}|x\rangle$$

We see, both oracles give same output except for the ancilla qubit which is of no value in the computation. Surprisingly, we can create the later version using just simple single qubit gates $Z$ and $I$.

$$\begin{gathered} U_{a}=U^{1} \otimes U^{2} \cdots \otimes U^{i} \otimes \cdots \otimes U^{n-1} \otimes U^{n}, \\ U^{i}=\left\{\begin{array}{cc} I, & a_{i}=0 \\ \sigma_{z}, & a_{i}=1 \end{array}, \quad I=\left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right), \quad \sigma_{z}=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right) .\right. \end{gathered}$$

Basically, ancilla plays no role in the computation in BZ algorithm, hence an equivalent oracle can be created using only single qubit operators.

This has been discussed in detail on second page of the paper link

Answer 2

I think the output is the same of what you are suggesting but the function has changed.The Oracle is described as a function $f:\{0,1\}^n→ \{0,1\}$ which is no longer the case when you replace the CNOT gates by Z gates.

I don't any applications for this algorithm but I can tell you why quantum is advantageous for solving the problem of the oracle. This can help you understanding the difference in your gate sequency and that of the algorithm.

• The function of the oracle is $s\cdot x$ and the objective is to recover the secret string s
• A classical computer can solve this problem with minimally n executions. Namely it can execute x_1=100...00, x_2=010...00, ..., x_n=000...01 to recover the string bits s_1,s_2,... and s_n.
• A quantum computer can use Bernstein-Vazirani's algorithm to find the secret string in one iteration. This can be done by measuring the input string x after executing the function once.
• The advantage of quantum is thus a speedup from n executions to only 1!