qc000018.htm

5.1 Deutsch’s problem

The simplest way to illustrate the power of quantum computing is to solve the so-called Deutsch’s problem. Consider a Boolean function

and suppose that we have a black box to compute it. We would like to know whether

is constant (that is,

) or balanced (

). To make this test classically, we need two computations of

and

and one comparison. Is it possible to do it better? The answer is affirmative, and here is a possible solution.

Suppose that we have a quantum black box to compute

. Consider the transformation

which applies to two qubits,

and

and produces

This transformation flips the second qubit if

acting on the first qubit is 1, and does nothing if

acting on the first qubit is 0.

The black box is “quantum", so we can choose the input state to be a superposition of

and

. Assume first that the second qubit is initially prepared in the state

. Then,

Next take the first qubit to be

The black box will produce

Next we will perform a measurement that projects the first qubit onto the basis

: we will obtain

if the function

is balanced and

in the opposite case. So, Deutsch’s problem was solved with only one computation of

. The explanation consists in the ability of a quantum computer to be in a blend of states: we can compute

and

, but also, and more importantly, we can extract some information about

which tells us whether

is equal or not to

Can any function

be implemented by a quantum gate array

? The answer is affirmative. Identifying the values 0 and 1 with the kets

respectively

may be defined as the linear operator

, which satisfies, for any

the equality

(13)

To compute

we apply

. Graphically, the transformation

is presented in Figure 14. We shall argue that

for any function , is a unitary transformation.

We have

hence, in view of the equality

, it suffices to prove that

The function

can be defined in four ways: 1.

; 2.

; 3.

; and 4.

We will investigate the matrix

in each situation, taking into account the correspondences:

Figure 14: _Quantum gate array

In the first case, we have

, hence

. In the second case,

, so it follows that

A direct computation shows that in the third case,

we denote, as usual, the sum modulo 2.