Introduction to Quantum Physics and Information Processing

Problems 173

Problems

8.1. Some texts implement the quantum function evaluator as a “controlled-

˜

U

f

”

gate (Figure 8.19), where

˜

U

f

acts only on the lower register, and is defined

by

˜

U

f

|yi = |y ⊕f(x)i:

|xi

•

|xi

|yi

˜

U

f

|y ⊕ f(x)i

FIGURE 8.19: The quantum function evaluator as a controlled

˜

U

f

gate.

How is the action of this implementation different from the f-controlled

NOT gate of Figure 7.15? Check by using standard basis states as well as

superpositions as inputs.

8.2. Show that the phase kickback trick works because the input state in the

bottom register is an eigenstate of the

˜

U

f

operator for the Deutsch algo-

rithm.

8.3. Deutsch’s original version of his algo ...