Classical and quantum computation with small space bounds
Az belleğe sahip klasik ve kuantum hesaplama
- Tez No: 286359
- Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 184
Özet
Bu tezde genel kuantum operatörlerini destekleyen yeni bir kuantum Turing makine modeli ile birlikteonun yığıt-bellekli, sayaçlı ve sonlu bellekli modelleri tanımlandı ve az belleğe sahipklasik ve kuantum makinelerin hesaplama güçleri bir çok durum için incelendi.Temel katkılarımız aşağıda özetlenmiştir.İlk olarak kuantum Turing makineleri sınırlı olmayan hata açısından ele alındı:(i) logaritma-altı bellek kullanılan bazı durumlarda hesaplama gücü açısındankuantum Turing makinelerinin klasik muadillerinden üstün olduğu gösterildi;(ii) aynı sonuç sonlu belleğe sahip kısıtlı kuantum Turing makineleri için de elde edildi;(iii) gerçek-zamanlı sonlu belleğe sahip belirlenimci olmayan kuantum Turing makinelerinintanıdığı dil ailesi belirlendi.İkinci olarak, sonlu belleğe sahip kuantum Turing makineleri sınırlı hata açısından ele alındı:(i) sola gitme veya durma hakkı yasaklanmış fakat kendisini başlangıç noktasına taşıyabilenözel kafaya sahip yeni çift-yönlü kuantum ve olasılıksal sonlu durumlu makineler tanımlandı;(ii) hesaplama gücü açısından bu tür kuantum makinelerin olasılıksal olanlardan daha güçlü olduğu gösterildi;(iii) bu modeller temelinde, çift-yönlü olasıksal ve klasik kafaya sahip kuantum sonlu durum makinelerin,çift-yönlü belirlenimci olmayan sonlu durum makineler ile kendi tek-yönlü muadillerindendaha az sonlu bellek kullandıkları gösterildi;(iv) ayrıca olasılıksal ve kuantum sonseçimli sonlu durumlu makineler ile sınırlı hata payıile tanıdıkları dil sınıfları tanımlandı ve bir çok özellikleri gösterildi.Üçüncü olarak, sadece yazma hakkı olan bir hafıza eklenen gerçek-zamanlı kuantum sonlu durumlumakenelerin hesaplama gücü, farklı türdeki sayaçlı makineler üzerinden yapılan bir çok benzetim ile incelendi.Paralel olarak, sayaçlı ve yığıt-bellekli makinelere dair bazı sonuçlar elde edildi.Son olarak, literatürde geçen bazı alt sınırların,düzenli olmayan bir dili tanıyan gerçek-zamanlı klasik Turing makineler için mümkün olan en iyi sınırlar olduklarıgösterildi.Ek olarak, benzer soru diğer tür gerçek-zamanlı makineler için araştırıldı veonlar tarafından az bellek ile tanınan birçok düzenli olmayan dilin varlığı gösterildi.
Özet (Çeviri)
In this thesis, we introduce a new quantum Turing machine model that supportsgeneral quantum operators, together with its pushdown, counter, and finite automaton variants,and examine the computational power of classical and quantum machines using small space boundsin many different 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 machinesis 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 byrealtime 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 finite automatawith a special two-way input head which is not allowedto be stationary or move to the left but has the capability to reset itselfto its starting position;(ii) the computational power of this type of quantum machineis shown to be superior to that of the probabilistic machine;(iii) based on these models, two-way probabilistic and two-way classical-head quantumfinite automata are shown to be more succinct than two-way nondeterministic finite automataand their one-way variants;(iv) we also introduce probabilistic and quantum finite automata with postselection with theirbounded error language classes, and give many characterizations of them.Thirdly, the computational power of realtime quantum finite automata augmented with awrite-only memory is investigated by showing many simulation results for different 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 languageare shown to be tight. Moreover, the same question is investigated for some other kinds of realtime machines andseveral nonregular languages recognized by them in small space bounds are presented.
Benzer Tezler
- Spreading and transport properties of quantum walks
Kuantum yürüyüşlerinin yayılım ve taşınım özellikleri
İSKENDER YALÇINKAYA
Doktora
İngilizce
2016
Fizik ve Fizik MühendisliğiSabancı ÜniversitesiFizik Ana Bilim Dalı
PROF. DR. MEHMET ZAFER GEDİK
- Nanoçubuklarda büyük yer değiştirme ve yerel olmayan elastisite teorilerine göre deplasman hesabı
Calculation of displacements of nanorods according to nonlocal theory of elasticity and large displacement theory
GÖKHAN GÜÇLÜ
Doktora
Türkçe
2020
Matematikİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. REHA ARTAN
- Development of application specific transport triggered processors for post-quantum cryptography algorithms
Post-kuantum kriptografi algoritmaları için uygulamaya özel taşıma tetiklemeli işlemcilerin geliştirilmesi
LATİF AKÇAY
Doktora
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
- Time domain surface integral equation solvers for quantum corrected electromagnetic analysis of plasmonic nanostructures
Başlık çevirisi yok
İSMAİL ENES UYSAL
Doktora
İngilizce
2016
Bilim ve TeknolojiKing Abdullah University of Science and TechnologyDR. HAKAN BAĞCI
- Quantum optics with single-photon nanoantenna
Tek foton kaynağı ile kuantum optik
OĞUZHAN YÜCEL
Yüksek Lisans
İngilizce
2019
Fizik ve Fizik MühendisliğiOrta Doğu Teknik ÜniversitesiFizik Ana Bilim Dalı
DOÇ. DR. ALPAN BEK
DOÇ. DR. SERKAN ATEŞ