Quantum computing: an introduction

The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin´s (1982, 1997) ideas of reversible computation. After some remarks about Deutsch´s (1985) pioneering work on quantum complexity and Shor´s (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover´s (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.