Alan Turing famously described his model of computation as an idealized physical device, "machine", rather than a linguistic or algebraic construction. However, a Turing machine is a classical one, in the sense that its states form a discrete set, and its evolution law is deterministic.

In the 1980s physicists started discussing quantum computers whose states lie in a Hilbert space ("entangling"). The use of entangled states allows one in principle to implement parallel computation, say, of many values of a certain function simultaneously. The famous Shor's factoring algorithm cleverly used this possibility.

In the talk I will explain several basic mathematical ideas underlying the quantum computing project, and illustrate them by describing Shor's factoring and Grover's search quantum routines.