Co language

Co language

這文章主要是想講Co language 和  co-NP，還有一些推論，鑒於我最近在讀complexity theory:
也做了一些筆記，希望可以分享給大家。

給一個decision problem的集合，可以定義這個集合的 "co":
首先先講一下定義: 還有一些基本性質><，還有他和其他的complexity class 的關係:
Given any complexity class, one can try to define co-that complexity class

Go back to Main page Notes for Complexity theory

比方像是這個 class 和 P, EXP, NP 等關係: 基本上用到一些很簡單的集合論而已
Just some simple techniques, one can show some basic theorems about these complexity class.

結束這些看起來抽象的定義以後: 應該要找一些真正的屬於 co-NP 的問題。
首先介紹 
After presenting some abstract proof, one should look for some questions belonging to co-NP

(1)Perfect matching.

Finally I try to present Prett's theorem.
Whether a number is a prime number belongs to NP and also belongs to co-NP.
I followed "CS681 Computational Number Theory Lecture 17: Primality is in NP ∩ coNP Instructor: Piyush P Kurur Scribe: Ramprasad Saptharishi"





Corollary: Factoring belongs to NP and belongs to co-NP
Most people believed that factoring belongs  to P. Quantum computing and Shor's algorithm become interesting in this class.
Indeed, Factoring belongs to BQP.

Little branch park and paint Branch Park 賞秋景 (含影片)

趁著假日無聊時候，想說到附近騎腳踏車逛逛，現在是11月了，秋天到了，美國很冷了，

漂亮的是，附近的山都變色了，有黃綠紅各式各樣的顏色。

我一個人騎著腳踏車移動著，首先來到的是  paint Branch Park. 照片如下:

有地方可以打球，也有地方可以躺著睡覺，很涼爽，假日只有我一個人，一個人走來走去，享受孤寂。Adelphi, 馬里蘭州 20783

這張照片是我躺著拍的。

Little branch park:

這是個鄰近的公園，跟上一個沒差很遠，景更美，能走的路也更多了。

3900 Sellman Rd, Beltsville, MD 20705

這個公園更大，裡面有小河，跟剛剛的小公園不一樣，有一條trail 可以走，也可以騎腳踏車進入。大概10分鐘就騎完了，如果用走路可以走30分鐘，天氣兩爽，顏色繽紛。如下照片:

這一株紅的非常過分呢

準備回家啦。這裡可以騎到巴爾帝摩路。之後看要到馬里蘭大學也都可以。

Video, 請大家訂閱唷，才能大家欣賞很多美景

Shor's algorithm and Hidden subgroup problems

Quantum Fourier transform and periodic finding algorithm:
Simply speaking, quantum fourier transform is analog to discrete fourier transform which can solve the periodic algorithm


Go back to Main page Notes for Complexity theory

Go back to the main quantum computing page

Shor's algorithm:
If we can solve periodic problem in polynomial time, then we have chance to solve factoring problem in polynomial time. This algorithm is called shor's algorithm.

這可以證明 Factoring belongs to BQP.

BQP= all decision language 可以被 Quantum Turing machine 在 polynomial time 解出。

由此可見: BQP 可能不等於NP，產生潛力。

Hidden subgroup problems: 
more abstractly, one can generalize simon's algorithm, shor's algorithm to problem called hidden subgroup problem. But we can not solve this problem in polynomial time if the group is not commutative.

Reference:

(1) Quantum Computation and Quantum Information textbook by Nielsen 

 QC-textbook.pdf

(2)  Ryan O'Donnell lecture note on Quantum Computing

(3)  Andrew Child's : lecture note on Quantum algorithms

忠孝SOGOHTC短短

短短拿氣球真的是超可愛的阿 謝謝短短給我這幾張ㄟ 都好讚好可愛喔 還有兩張合照沒有出XD 慢慢來 這次去了兩天XD 太可愛太正啦

Simple quantum algorithm

I write this article in order to record some basic quantum algorithms which I might forget.

Deutsch–Jozsa algorithm and Simon's algorithm:

Go back to Main page Notes for Complexity theory
Go back to the main quantum computing page

Suppose, we have a black box function called (f): and there are only two case:

We want to find which case is the right case.  In classical, at least we need two oracles. If we are very lucky, we get the different output compare to the result we get at the beginning. If we are at very bad situation, we have to do at least 2^{n-1}+1 times to find the answer.

Simon's algorithm

Reference:

(1) Quantum Computation and Quantum Information textbook by Nielsen 

 QC-textbook.pdf

(2)  Ryan O'Donnell lecture note on Quantum Computing

(3)  Andrew Child's : lecture note on Quantum algorithms

發期中考考卷

今天發考卷，呵呵呵，研究所的量子力學，班上滿分，被教授 唸出來，叫到我名字呵呵，好爽好爽，就只有我滿分，我其實以前都很享受這種感覺，我的過去又出現了，六十人ㄟ，運氣超好，居然最後有算出來，哈哈，爽，結果回到宿舍...

同同學....我們不認識喔 .你不必要這樣吧，大家素不相識ㄟ，臉書歡迎追蹤喔，個人沒在加不熟大學同學(好像是 異曲同工 正妹: 臉書歡迎追蹤或是加粉專喔 個人無在加不熟攝影師粉絲喔 等等等這樣XD......)

我在想，他搜尋聽到的名字，再看到我臉書，往下滑動態....... 是怎樣的感受阿???? 他可能想看班上滿分的人的臉書長怎樣? 好想看他表情 哈哈哈.... 運氣好而已，賽到，哈哈