UNIVERSALITY IN QUANTUM COMPUTATION 论文

摘要

We show that in quantum computation almost every gate that operates on two or more bits is a universal gate. We discuss various physical considerations bearing on the proper definition of universality for computational components such as logic gates. Introduction It has been known for several years that the theory of quantum computers --- i.e. machines that rely on characteristically quantum phenomena to perform computations [1] --- is substantially different from the classical theory of computation, which is essentially the theory of the universal Turing machine. We may identify three important differences. Firstly, the properties of quantum computers are not postulated in abstracto but are deduced entirely from the laws of physics. Logically, this was already true of the classical theory, as Landauer [2] has pointed out, but the intuitive nature of the classically-available computational operations, and the millennia-long history of their study, allowed pioneers such as Turing, Chu...