Turing machines based on quantum logic can solve undecidable problems. In this paper we will give recursion-theoretical characterization of the computational power of this kind of quantum Turing machines. In detail, for the unsharp case, it is proved that Σ01 ∪Π01⊆ LTd(ε,Σ)(LTw(ε,Σ))⊆Π02 when the truth value lattice is locally finite and the operation ∧ is computable, where LTd(ε,Σ)(LTw(ε,Σ))denotes the class of quantum language accepted by these Turing machine in depth-first model (respectively, width-first model); for the sharp case, we can obtain similar results for usual orthomodular lattices.Turing machines based on quantum logic can solve undecidable problems. In this paper we will give recursion-theoretical characterization of the computational power of this kind of quantum Turing machines. In detail, for the unsharp case, it is proved that Σ01 ∪Π01⊆ LTd(ε,Σ)(LTw(ε,Σ))⊆Π02 when the truth value lattice is locally finite and the operation ∧ is computable, where LTd(ε,Σ)(LTw(ε,Σ))denotes the class of quantum language accepted by these Turing machine in depth-first model (respectively, width-first model); for the sharp case, we can obtain similar results for usual orthomodular lattices.

EPiC series in computingJan 23, 20180 citations

Halting of Quantum Turing Machines

Masanao Ozawa

Lecture notes in computer scienceJan 1, 20027 citations

一般化量子チューリング機械について (情報科学と函数解析の接点 : これまでとこれから)

Satoshi Iriyama, Masanori Ohya

In this paper, we construct a novel model of a universal quantum Turing machine(QTM) which is free from the specific time for an input data and efficiently simulates each step of a given QTM.Deutsch [1] formulated a precise model of a quantum computer as quantum Turing machine (QTM) and proposed a model of universal quantum Turing machine which requires exponential time of $t$ to simulate any other QTM with $t$ steps.Bernstein and Vazirani[2] showed the existence of an efficient universal QTM by slightly modifying Deutsch's model.In [3] several issues related with QTM and universal QTM are discussed.Nishimura and Ozawa gave anotherIn this paper, we construct a novel model of a universal quantum Turing machine(QTM) which is free from the specific time for an input data and efficiently simulates each step of a given QTM.Deutsch [1] formulated a precise model of a quantum computer as quantum Turing machine (QTM) and proposed a model of universal quantum Turing machine which requires exponential time of $t$ to simulate any other QTM with $t$ steps.Bernstein and Vazirani[2] showed the existence of an efficient universal QTM by slightly modifying Deutsch's model.In [3] several issues related with QTM and universal QTM are discussed.Nishimura and Ozawa gave another

数理解析研究所講究録Oct 1, 20040 citations

t

to simulate any other QTM with

t

steps.Bernstein and Vazirani[2] showed the existence of an efficient universal QTM by slightly modifying Deutsch's model.In [3] several issues related with QTM and universal QTM are discussed.Nishimura and Ozawa gave another