Deutsch’s Algorithm

Deutsch’s algorithm doesn’t solve any significant problem in computer science. However, it is the first to provide proof that in some instances quantum computers are significantly faster than traditional computers. Deutsch found a solution for a certain problem in a single step whereas a classical approach needs two.

Consider a function f that maps [0,1] into [0,1]. If it is known that f(x) is either constant (0 or 1 for all values of x) or balanced (0 for exactly half of all possible x and 1 for the other half), then the problem is to decide what type it is.

Assume this function is implemented inside a black box also called an oracle. Thus, the only way to gain any information about the function is to apply some input x∈ {0, 1} and check the device output f(x) ∈ {0, 1).

If a classical computer is used to determine whether f is balanced or constant the computer needs to evaluate the function both for x=0 and for x=1 separately, and then compare the two outputs to decide whether f(x=0) is indeed equal to f(x=1).

Deutsch’s Algorithm evaluates the function by framing the problem in a slightly different manner. Instead of checking out the values f(0) and f(1) separately, the algorithm determines the value of f simultaneously for x=0 and x=1. A function f(x) is balanced if the value of f(x=0) ⊕ f(x=1) = 1, even though it is not possible to determine the actual value.