MilestoneTheory & algorithmsConfirmed

Yao connects quantum circuits with quantum Turing machines

Nov 1993

Andrew Yao shows that quantum Turing machines and systematically generated quantum circuits can simulate each other with only polynomial overhead. This links two ways of defining what an efficient quantum computation can do.

Why it matters

It gave circuit-based quantum algorithms a firm connection to the mathematical model used to study the power and limits of computation.

Andrew Chi-Chih Yao · Princeton

See it on the timeline

Related

• David Deutsch describes a universal quantum computer (Jul 8, 1985)