4 Quantum Computers
A classical computer bogs down when it is made to simulate a quantum system; Feynman [
58
] suggested that a quantum computer might do a better job. In fact earlier, Benioff [
10
] devised an elaborate quantum-mechanical simulation of a Turing machine, the first half-classical, half-quantum Turing machine; his construction was as powerful as a Turing machine. In the same line of research Feynman [
58
,
59
] proposed quantum versions of logical circuits. Albert [
2
] has described the first “truly" quantum computer, a “quantum automaton"; this machine has properties not shared by any classical automata. Quantum automata are, of course, not universal computers. In 1985 Deutsch _[
48
] published a model of a quantum computer, the first “true" quantum universal Turing machine, one which is relying directly on the interference of quantum states. In the same year, 1985, Peres _[
109
] improved Benniof and Feynman _models. In 1992 Deutsch and Jozsa _[
52
] dicussed a few problems that could be solved faster with quantum computers than conventional Turing machines. This was the first indication that quantum computing might be superior to classical computing.
