# Implementing the one-bit Deutsch Oracle algorithm using phase

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?

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

• note that you can use $$...$$ to center equations that should go on their own line
– glS
Nov 1, 2019 at 17:13