Efficient two-way quantum finite state automata
Verimli çift yönlü kuantum sonlu durumlu makineler
- Tez No: 179071
- Danışmanlar: PROF. A. C. CEM SAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2007
- 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ı: 67
Özet
Benzer işler için bilinen en iyi klasik algoritmalardan üstel olarak daha verimli kuantum algoritmalarının kesfi, araştırmacıları kuantum hesaplamanın gorünürdeki üstunlugunün sebeplerini ve sınırlarını daha iyi anlamak için bir çok hesaplama modelinin klasik ve kuantum surumlerinin goreceli guçlerini karşılaştırmaya itmiştir. Bu sekildeki karşılaştırmalı analiz sonuçları ilginç gorünen modellerden biri sonlu durumlu makinelerdir. Bu çalışmada farklı kuantum sonlu makine türleri arasında en güçlü aile olan çift yonlü sonlu durumlu makinelere (2ksm) odaklanılmıştır. Kondacs ve Watrous herhangi bir verili pozitif hata sınırı e için Leq = {anbn| n > 0} dilini tanıyan 2ksm'nin inşası için buldukları yontemi kullanarak 2ksm'lerin klasik benzerlerinden daha güçlü oldugunu ispatlamis¸lardır. w girdi dizisi ol-mak üzere, bu yonteme gore insa edilen makineler O((\)) sayısında duruma sahiptir ve O((\)|w|) adım çalışırlar. Araştırmamızda, bu masraf fonksiyonlarının istenen hata sınırına baglılı?gını azaltmanın yolları incelenmektedir. Aynı dili tanıyan daha etkili yontemler sunulmaktadır. Yontemlerimizden birinin ürettigi sonlu makineler O(|w|) adımda dururlar (çalısma zamanı hata sınırına baglı degildir) ve verili herhangi bir c sabiti için O((\)i) sayıda duruma sahiptirler. Durum sayısı karmaşıklıgı J'a gore poli-logaritmik olan ve O(log(±)|w|) adımda duran sonlu makineler üreten başka yontemler de sunulmaktadır
Özet (Çeviri)
The discovery of quantum algorithms which are exponentially more e- cient than the best known classical algorithms for similar tasks has spurred researchers to compare the relative powers of the classical and quantum versions of several computational models to better understand the causes and limitations of the apparent power of quantum computing. One model for which such comparative analyses have led to interesting results is that of nite automata. Among the various types of quantum nite automata, we concentrate on the strongest family, namely, two{way quantum nite automata (2qfa's). Kondacs and Watrous proved that 2qfa's are more powerful than their classical counterparts by describing a method for constructing 2qfa's that recognize the non{regular language Leq = fanbnj n > 0g for any given error bound > 0. Machines built according to this method have O(( 1 )2) states, and they halt after O(( 1 )jwj) steps, where w is the input string. In this thesis, we examine ways of reducing the dependence of these cost functions on the desired error bound. We present more ecient constructions to recognize the same language. One of our methods produces machines which halt in O(jwj) time (i.e. the running time does not depend on the error bound) and which have O(( 1 )2 c ) states for any given constant c > 1. Other methods, yielding machines whose state complexities are polylogarithmic in 1 , and which halt in O(log( 1 )jwj) time, are also presented.
Benzer Tezler
- İki boyutlu iki gruplu nötron difüzyon denkleminin lineer sınır elemanları ile çözümü
The application of linear boundary elements method two dimensional and two group neutron diffusion equation
SIRMA USTAARAMOĞLU
Yüksek Lisans
Türkçe
1997
Nükleer Mühendislikİstanbul Teknik ÜniversitesiFizik Ana Bilim Dalı
DOÇ. DR. BİLGE ÖZGENER
- Nicem devinbilimde olasılıkçıl evrim kuramı, evrilteç devinbilimi, konaç bükümü ve yanaşık açılımlar: Bakışık üstel gizilgüçlü dizgeler
Probabilistic evolution theory, evolver dynamics, coordinate bending and asymptotic expansions: Quantum symmetric exponential potential systems
SEMRA BAYAT ÖZDEMİR
Doktora
Türkçe
2021
Matematikİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. METİN DEMİRALP
- Taban operatörlerine açılım yöntemi ile enerji spektrumunun belirlenmesi: Kuvantum anharmonik salıncı
Başlık çevirisi yok
EBRU NUHOĞLU
- New efficient characteristic three polynomial multiplication algorithms and their applications to NTRU prime
Yeni verimli karakteristik üç polinom çarpımı algoritmaları ve NTRU prime'a uygulamaları
ESRA YENİARAS
Doktora
İngilizce
2022
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
DOÇ. DR. MURAT CENK
- New TMVP-based multiplication algorithms for polynomial quotient rings and application to post-quantum cryptography
Polinom halkaları için yeni TMVP-tabanlı çarpım algoritmaları ve quantum-sonrası kriptografiye uygulamaları
İREM KESKİNKURT PAKSOY
Doktora
İngilizce
2022
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. MURAT CENK