De-Quantising the Solution of Deutsch's Prolem

Abstract

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch’s problem. Consider a Boolean function f : {0,1}→{0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant (that is, f (0) = f (1)) or balanced ( f (0) ≠ f (1)). Classically, to solve the problem seems to require the computation of f (0) and f (1), and then the comparison of results. Is it possible to solve the problem with only one query on f ? In a famous paper published in 1985, Deutsch posed the problem and obtained a “quantum” partial affirmative answer. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be de-quantised to a deterministic simpler solution which is as efficient as the quantum one. The use of “superposition”, a key ingredient of quantum algorithm, is—in this specific case—classically available.