Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Classical and quantum computation with small space bounds

Basit öğe kaydını göster

dc.contributor Ph.D. Program in Computer Engineering.
dc.contributor.advisor Say, Ahmet Celal Cem.
dc.contributor.author Yakaryılmaz, Abuzer.
dc.date.accessioned 2023-03-16T10:13:33Z
dc.date.available 2023-03-16T10:13:33Z
dc.date.issued 2011.
dc.identifier.other CMPE 2011 Y34 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/12567
dc.description.abstract In this thesis, we introduce a new quantum Turing machine model that supports general quantum operators, together with its pushdown, counter, and nite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many di erent cases. The main contributions are summarized below. Firstly, we consider quantum Turing machines in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by quantum Turing machines is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted quantum Turing machines; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic quantum Turing machines is given. Secondly, we consider constant space-bounded quantum Turing machines in the bounded error setting: (i) we introduce a new type of quantum and probabilistic nite automata with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way probabilistic and two-way classical-head quantum nite automata are shown to be more succinct than two-way nondeterministic nite automata and their one-way variants; (iv) we also introduce probabilistic and quantum nite automata with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime quantum nite automata augmented with a write-only memory is investigated by showing many simulation results for di erent kinds of counter automata. Parallelly, some results on counter and pushdown automata are obtained. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight. Moreover, the same question is investigated for some other kinds of realtime machines and several nonregular languages recognized by them in small space bounds are presented.
dc.format.extent 30cm.
dc.publisher Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2011.
dc.relation Includes appendices.
dc.relation Includes appendices.
dc.subject.lcsh Machine theory.
dc.subject.lcsh Computational complexity.
dc.subject.lcsh Quantum computers.
dc.title Classical and quantum computation with small space bounds
dc.format.pages xv, 169 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım