2007/01/16 by Willem Fouché, Willem L. Fouché, Fouché, Willem +7 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0701108
7 pages
arxiv created 2007/01/16 · arxiv updated 2009/12/01
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.