2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.