### 9.4 Swapping states

Three applications of the *C _{not }* gate will swap

*|a, b〉 to |b, a〉*:

where ⊕ denotes modulo 2 addition^{2}

### 9.5 The Deutsch algorithm

Pay very careful attention to this landmark algorithm in quantum computing. Consider the Boolean functions f that map *{0, 1} to {0, 1}*. There are exactly four such functions, as follows:

(1) two “constant” functions:* f(0)* =* f(1)* = 0 and *f(0)* = *f(1)* = 1;

(2) two “balanced” functions:* f(0)* = 0, *f(1)* = 1 and* f(0)* = 1,* f(1)* = 0.

The task is to identify the set to which* f(0)* and *f(1)* belong to in only one measurement. Note, that we do not seek the values of* f(0)* and *f(1)* but only a global property of *f.*

The solution provided here is reported in Cleve, et al^{3}., which improves upon the original paper by Deutsch (1985)^{4}. Deutsch’s solution had three possible outcomes: “balanced”, “constant”, and “inconclusive” with 50% probability that it would produce an “inconclusive” result. The solution described here always correctly identifies “constant” and “balanced” functions. The improvement took more than a decade to be discovered.

Let the initial state of the 2-qubit system be *|Ψ〉 = |01〉* . When the Hadamard gate acts on it, we get

What has been cleverly accomplished is that by measuring the first qubit we may determine* f(0) ⊕ f(1)* which will tell us if* f(0) = f(1)* or not. In essence, just one evaluation of *f(x)* has allowed us to find a global property of* f(x),* namely, *f(0)⊕ f(1)*. On the other hand, a classical computer would have required at least two evaluations. The Deutsch algorithm provided the first example that a quantum computer could do something that a classical computer cannot. It was simply brilliant in conception.

### 9.6 The Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm^{5} solves a generalized Deutsch problem. Given a black box *U _{f}* whose action is to perform

*|x, y〉 |x, y ⊕ f(x)〉 for x ∈ {0, 1}*and that it is known beforehand that f is one of two kinds: either

^{n}≡{0,…,2^{n}-1} and f(x)∈ {0, 1},*f(x)*is constant for all values of x, or else

*f(x)*is balanced, i.e., equal to 1 for exactly half of all possible x, and 0 for the other half. The significance of this problem is that a classical solution, in the worst-case, would require

*2*evaluations of f before determining the answer with certainty since one may receive 2

^{n-1}+1*0s before finally getting a 1. Remarkably, the Deutsch-Jozsa algorithm requires only one evaluation of f. The reader is encouraged to see Table 9.1 where the algorithm is provided in summary form.*

^{n}/2The Deutsch–Jozsa algorithm later inspired two revolutionary quantum algorithms, namely Shor’s factoring algorithm and Grover’s search algorithm, described in Section 10.

### 9.7 Computing f(x) in parallel

This is remarkable. The first term contains information about *f(0)* along with its input* x = 0*, and the second term contains information about* f(1*) along with its input *x = 1*. That is, the second qubit is in an equal superposition of *f(0) and f(1),* and the two values were calculated in parallel. This power of quantum algorithms comes from quantum parallelism and entanglement. So, most quantum algorithms begin by computing a function f(x) on a superposition of all values of *x* as follows:

Start with an n-qubit state *|00…〉* and apply H to all the qubits to get

which is the superposition of all integers *0≤ x < 2 ^{n}.* Next, add a

*k-qubit*register in state |00..0〉, large enough to hold the longest value of

*f(x).*Then by linearity

Thus *f(x)* is computed in parallel for all values of* x∈ {0,…, 2 ^{n} -1},* provided one knows how to construct the appropriate

*U*that will map a pair of qubit strings

_{f}*|x, 0〉 i*nto the pair

*|x, f(x)〉*. The output comes from the constructive interference of parallel computations.

The trick in constructing* U _{f}* is to break down the computation, corresponding to the function

*f(x)*, into a set of 1-qubit and 2-qubit unitary operations such that the state |x

*〉*, 0 is mapped to the state

*|x, f(x)〉*for any input x. Note that the number of qubits required for the second register must be at least sufficient to store the longest result

*f(x)*for any of these computations. In general, in designing quantum algorithms, one assumes that for reasonable functions, a suitable

*U*can be built.

_{f}^{2} 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕ 1 = 1. See Sec. A.5.7 in Appendix A for a quick recall of modular arithmetic.

^{3}Cleve, et al (1998).

^{4} Deutsch (1985).

^{5} Deutsch & Jozsa (1992).