**Mathematics of Quantum Computing**

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.

*Yuri Manin*

Back to Colloquium Page