Local Transition Functions of Quantum Turing Machines
Masanao Ozawa; Harumichi Nishimura
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 34, Issue: 5, page 379-402
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topOzawa, Masanao, and Nishimura, Harumichi. "Local Transition Functions of Quantum Turing Machines." RAIRO - Theoretical Informatics and Applications 34.5 (2010): 379-402. <http://eudml.org/doc/222093>.
@article{Ozawa2010,
abstract = {
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.
},
author = {Ozawa, Masanao, Nishimura, Harumichi},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Quantum Turing machines; transition functions;
multi-tape quantum Turing machines.; quantum Turing machines},
language = {eng},
month = {3},
number = {5},
pages = {379-402},
publisher = {EDP Sciences},
title = {Local Transition Functions of Quantum Turing Machines},
url = {http://eudml.org/doc/222093},
volume = {34},
year = {2010},
}
TY - JOUR
AU - Ozawa, Masanao
AU - Nishimura, Harumichi
TI - Local Transition Functions of Quantum Turing Machines
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 5
SP - 379
EP - 402
AB -
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.
LA - eng
KW - Quantum Turing machines; transition functions;
multi-tape quantum Turing machines.; quantum Turing machines
UR - http://eudml.org/doc/222093
ER -
References
top- P. Benioff, The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Statist. Phys.22 (1980) 563-591.
- E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM J. Comput.26 (1997) 1411-1473.
- D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London Ser. A400 (1985) 97-117.
- D. Deutsch, Quantum computational networks. Proc. Roy. Soc. London Ser. A425 (1989) 73-90.
- R.P. Feynman, Simulating physics with computers. Internat. J. Theoret. Phys.21 (1982) 467-488.
- J. Gruska, Quantum Computing. McGraw-Hill, London (1999).
- M. Hirvensalo, On quantum computation. Ph.D. Thesis, Turku Center for Computer Science, Finland (1997).
- H. Nishimura and M. Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines. Theoret. Comput. Sci. (to appear). Available at the LANL quantum physics e-print archive at http://xxx.lanl.gov/archive/quant-ph/9906095
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, MA (1994).
- P.W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser. IEEE Computer Society Press, Los Alamitos, CA (1994) 124-134.
- A. Yao, Quantum circuit complexity, in Proc. 34th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA (1993) 352-361.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.