Implementing the one-bit Deutsch Oracle algorithm using phase

Question

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a reversible way). However, I've heard there is a different way of implementing the one-bit Deutsch Oracle algorithm involving phases which only requires a single qbit; how is this done?

Answer 1

Overview

To recap the one-bit Deutsch Oracle problem, there are four possible oracle functions: constant-0, constant-1, identity, and negation. The task is to determine whether the oracle function is constant (constant-0 & constant-1) or variable/balanced (identity & negation). You can do this using phases as follows:

1. Rewrite the oracle function as $U_f|x\rangle=(-1)^{f(x)}|x\rangle$
2. Calculate $U_f|+\rangle$
3. Measure in the $\{|+\rangle, |-\rangle \}$ basis; the oracle function is constant if the result is $|+\rangle$ and variable/balanced if the result is $|-\rangle$

Rewriting the oracle functions

Constant-0

We have:

$f(0) = 0, f(1) = 0$

So:

$U_f|0\rangle = (-1)^{f(0)}|0\rangle = (-1)^0|0\rangle = 1|0\rangle = |0\rangle$

$U_f|1\rangle = (-1)^{f(1)}|1\rangle = (-1)^0|1\rangle = 1|1\rangle = |1\rangle$

In this case $U_f = I$, the identity operator.

Constant-1

We have:

$f(0) = 1, f(1) = 1$

So:

$U_f|0\rangle = (-1)^{f(0)}|0\rangle = (-1)^1|0\rangle = -1|0\rangle = -|0\rangle$

$U_f|1\rangle = (-1)^{f(1)}|1\rangle = (-1)^1|1\rangle = -1|1\rangle = -|1\rangle$

We always multiply the phase by -1. For this we can use a rotation gate $U_f = R_y(2\pi)$.

Identity

We have:

$f(0) = 0, f(1) = 1$

So:

$U_f|0\rangle = (-1)^{f(0)}|0\rangle = (-1)^0|0\rangle = 1|0\rangle = |0\rangle$

$U_f|1\rangle = (-1)^{f(1)}|1\rangle = (-1)^1|1\rangle = -1|1\rangle = -|1\rangle$

So if the input is $|0\rangle$ then we leave it alone, but if it's $|1\rangle$ then we flip the phase. Sound familiar? Recall the phase-flip, or Z-gate:

$Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$

So $U_f = Z$ for Identity.

Negation

We have:

$f(0) = 1, f(1) = 0$

So:

$U_f|0\rangle = (-1)^{f(0)}|0\rangle = (-1)^1|0\rangle = -1|0\rangle = -|0\rangle$

$U_f|1\rangle = (-1)^{f(1)}|1\rangle = (-1)^0|1\rangle = 1|1\rangle = |1\rangle$

In this case $U_f = XZX$.

Calculating $U_f|+\rangle$

Constant-0

$I|+\rangle = |+\rangle$

Constant-1

$R_y(2\pi)|+\rangle = -|+\rangle$

Identity

$Z|+\rangle = |-\rangle$

Negation

$XZX|+\rangle = XZ|+\rangle = X|-\rangle = -|-\rangle$

Measurement

It's pretty clear that if we measure in the $\{|+\rangle, |-\rangle \}$ basis, we'll get $|+\rangle$ when the oracle function is constant and $|-\rangle$ when the oracle function is variable. Done.

Discussion

While this approach does have the benefit (for learners) of not requiring multiple qbits or a CNOT gate, the rewriting step seems more like "cheating" given the problem statement.