ABSTRACT
The idea of using quantum mechanics to provide more power than classical computers seems to have begun around 1981–2 (Benioff, 1982), but Deutsch (1985) put the concept on a sounder footing a short time later. Deutsch reformulated the Turing (1937) thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Hence, the user must provide some cleverness if this state is to be determined. Benioff pointed out the need for the quantum state to experience interference, some indeterminism, and was what we would today call an entangled state. He also realized that nondissipative evolution was unphysical, so immediately it became clear that a great deal of effort would be required to minimize the decoherence of the physical states. Deutsch (1989) then provided some input as to what type of states or systems might be usable in this process. Jozsa (1991) mathematically showed that one could associate a quantum state to each function that one desired to evaluate, and that this should lead to a rapid solution of problems via the quantum computer (Deutsch and Jozsa, 1992).
