Deutsch-Josza Alrorithm
Let us now operate oracle V_f on the the Hadamard state | x > that has |0 > and | 1 > in equal probability
|
| x > = 1/\sqrt2 ( | 0 > + | 1 >)
|
|
and obtain
|
V_f | x > = 1/\sqrt2 { (-1)f(0)| 0 > + (-1)f(1)| 1 > }
|
|
The probability P of finding the same state | x > after the operation of V_f on |x > is given by
|
P = | < x | V_f | x > |2 = 1/4 | (-1)f(0) + (-1)f(1) |2
|
|
Looking into the detail, we have
|
P = 1 ( f(0)=f(1) ; when f(x) is a constant )
P = 0 ( f(0)<>f(1); when one of f(0), f(1) is 1 and the othre 0 )
|
|
In specific term, P = 1 is obtained for the case of f being A or D, and P = 0 for B or C. Classically, oracle has to be consulted twice in order to calculate both f(0) and f(1). But what we have observed in the above expression is that quantum oracle V_f is operated just once to determin both f(0) and f(1). You might say quantum oracle U_f is drawn twice. But that is not really the point. (Besides, there is another way to do the same with single operation of U_f.) We can extend the same trick to the case of general x with n bits. Single operation of V_f can distinguish between two cases
|
P = 1 ( f(x) is constant )
P = 0 ( # of x that gives f(x)=1 and that gives f(x)=0 are same )
|
|
but the classical oracle operation will have to be done 2^n times to determin all f(x) with all possible x. It is 4 times for n=2 bits, 16 times for n=3 bits, and256 times for n=4 bits. So with large n, the quantum improvement is exponential.
The quantum acceleration of deciding this parity-type property of f(x) is discovered by Deutsch and Josza. The truth is that this particular property of f(x) is not much of practical importance. But still, this was a first concrete demonstration of the power of quantum information processing. Pedagigical value dictates us to examin this algorithm in detail in the following section.
|
Go To:
ResearchPage