On the simulation of quantum turing machines

✍ Scribed by Marco Carpentieri

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 338 KB
• Volume: 304
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00054-9

✦ Synopsis

In this article we shall review several basic deÿnitions and results regarding quantum computation. In particular, after deÿning Quantum Turing Machines and networks the paper contains an exposition on continued fractions and on errors in quantum networks. The topic of simulation of Quantum Turing Machines by means of obvious computation is introduced. We give a full discussion of the simulation of multitape Quantum Turing Machines in a slight generalization of the class introduced by Bernstein and Vazirani. As main result we show that the Fisher-Pippenger technique can be used to give an O(tlogt) simulation of a multi-tape Quantum Turing Machine by another belonging to the extended Bernstein and Vazirani class. This result, even if regarding a slightly restricted class of Quantum Turing Machines improves the simulation results currently known in the literature.