Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9906084 · Lecture notes in computer science

A Foundation of Programming a Multi-tape Quantum Turing Machine

Tomoyuki Yamakami

Published Jan 1, 1999• 35 citations
arXivHTMLPDF
DOI
10.1007/3-540-48340-3_39

Related papers

A formulation of Quantum Turing Machine

Ryuichi Sawae, Hiroshi Takeuchi, Tadahito Harima

•Dec 1, 1995•0 citations

Local Transition Functions of Quantum Turing Machines

Masanao Ozawa, Harumichi Nishimura

Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.

arXiv:quant-ph/9811069•RAIRO - Theoretical Informatics and Applications•Sep 1, 2000•41 citations

Classically-controlled Quantum Computation

Simon Perdrix, Philippe Jorrand

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine is simulated by a CQTM without loss of efficiency. Furthermore, we show that any k -tape CQTM is simulated by a 2-tape CQTM with a quadratic loss of efficiency. The gap between classical and quantum computations which was already pointed out in the framework of measurement-based quantum computation (see [S. Perdrix, Ph. Jorrand, Measurement-Based Quantum Turing Machines and their Universality, arXiv, quant-ph/0404146 , 2004]) is confirmed in the general case of classically-controlled quantum computation. In order to appreciate the similarity between programming classical Turing machines and programming CQTM, some examples of CQTM will be given in the full version of the paper. Proofs of lemmas and theorems are omitted in this extended abstract.

Electronic Notes in Theoretical Computer Science•Feb 24, 2006•13 citations

Halting of Quantum Turing Machines

Masanao Ozawa

Lecture notes in computer science•Jan 1, 2002•6 citations

Quantum Turing Machine Simulator

Joachim Hertel

The Mathematica Journal•Jan 1, 2001•3 citations

Classically controlled quantum computation

Simon Perdrix, Philippe Jorrand

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically controlled Quantum Turing Machine (CQTM), which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for formalised classical control. In a CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine can be simulated by a CQTM without loss of efficiency. Furthermore, we show that any -tape CQTM can be simulated by a 2-tape CQTM with a quadratic loss of efficiency. In order to compare CQTMs with existing models of quantum computation, we prove that any uniform family of quantum circuits (Yao 1993) is efficiently approximated by a CQTM. Moreover, we prove that any semi-uniform family of quantum circuits (Nishimura and Ozawa 2002), and any measurement calculus pattern (Danos et al. 2004) are efficiently simulated by a CQTM. Finally, we introduce a Measurement-based Quantum Turing Machine (MQTM), which is a restriction of CQTMs in which only projective measurements are allowed. We prove that any CQTM is efficiently simulated by a MQTM. In order to appreciate the similarity between programming classical Turing machines and programming CQTMs, some examples of CQTMs are given.

arXiv:quant-ph/0407008•Mathematical Structures in Computer Science•Jul 24, 2006•29 citations
It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine is simulated by a CQTM without loss of efficiency. Furthermore, we show that any k -tape CQTM is simulated by a 2-tape CQTM with a quadratic loss of efficiency. The gap between classical and quantum computations which was already pointed out in the framework of measurement-based quantum computation (see [S. Perdrix, Ph. Jorrand, Measurement-Based Quantum Turing Machines and their Universality, arXiv, quant-ph/0404146 , 2004]) is confirmed in the general case of classically-controlled quantum computation. In order to appreciate the similarity between programming classical Turing machines and programming CQTM, some examples of CQTM will be given in the full version of the paper. Proofs of lemmas and theorems are omitted in this extended abstract.
It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically controlled Quantum Turing Machine (CQTM), which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for formalised classical control. In a CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine can be simulated by a CQTM without loss of efficiency. Furthermore, we show that any -tape CQTM can be simulated by a 2-tape CQTM with a quadratic loss of efficiency. In order to compare CQTMs with existing models of quantum computation, we prove that any uniform family of quantum circuits (Yao 1993) is efficiently approximated by a CQTM. Moreover, we prove that any semi-uniform family of quantum circuits (Nishimura and Ozawa 2002), and any measurement calculus pattern (Danos et al. 2004) are efficiently simulated by a CQTM. Finally, we introduce a Measurement-based Quantum Turing Machine (MQTM), which is a restriction of CQTMs in which only projective measurements are allowed. We prove that any CQTM is efficiently simulated by a MQTM. In order to appreciate the similarity between programming classical Turing machines and programming CQTMs, some examples of CQTMs are given.