STOC 被拒絕: 出國讀書體驗到 失敗是常態

 

STOC 被拒絕: 出國讀書體驗到 失敗是常態

The ACM Symposium on Theory of Computing 理論計算機科學 最高等級期刊 我很常失敗 You sent 真的 老大也這樣講 你別看我這樣 我失敗率有8成 做每一件事情 

都8成會失敗

這是出國鐵律

失敗就是人生常態 我現在做一個計畫 一個文章 一個賺錢idea

 我都expect他會失敗 

他假如一開順利 我就expect他接下來會不順

這就是我的博士學習 

我做太多文章 失敗率超高 成功也是一波三折

習慣失敗 跟吃飯喝水依樣 我發現這也是博士訓練

Note for Quantum Computing

Note for Quantum Computing

Hand writing notes for Quantum Computing:

You can download as you want:

1:Simple quantum algorithm
2:Shor's algorithm and Hidden subgroup problems
3:Super densecoding and quantum Teleportation 
4:Grover's Algorithm
5:Quantum Algorithms and Quantum Complexity
6:Adversary Method for Quantum lower bound 
7:Quantum Probability 
8:Shannon Entropy and Data compression 
9:Quantum Error Correction 中文
10:Another view of quantum Information 
11:BQP

BQP?

BQP? 簡寫就是bounded-error quantum polynomial time (BQP) :

主要是 看他的一些性質

跟其他complexity class的關係

主要參考: Scott aaronson 的書

還有 Quantum Information Theory:
Ryan O'Donnell

Go back to the main quantum computing page

做的小筆記，最後說一下，部落格即將轉型，以後可能會停刊。

Another view of quantum Information

Another view of quantum Information:

Go back to the main quantum computing page

Quantum Error Correction 中文

Quantum Error Correction?
本文章 主要介紹: Quantum Error Correction stabilized code:
這主題也是相對來說困難的:
主要是 要如何 做出 Quantum Error Correction。
而且是用更數學的方式來說明

也就是所謂的:stabilized code。

跟classical 不一樣的事情是: 

quantum error correction 就是把一個hilbert space 塞到一個更大的 codespace裡面。

藉由Codespace 上面的一些operators。

互相交集，用來recover 這個hilbert space.

以下就是note 。可以follow

Nielsen 的課本。

Go back to the main quantum computing page

Shannon Entropy and Data compression

Shannon Entropy and Data compression:

這主題真的是相對來說困難了。
Shannon提出一個 entropy的概念，我們以前認定了的 entropy 多半是物理的，混亂的。但是20世紀初，Shannon 提出一個 entropy的概念 給一個機率，就可以得到一個entropy
這個可以把他推廣成 Data compression 和 quantum computing
quantum information theory。從這裡，似乎可以看出一點 量子資訊理論:

Go back to the main quantum computing page

附錄的定理:

Gibbs' inequality

Quantum Probability

Quantum Probability ?

這文章主要要談到三個 General 的推廣 從一般classical 機率論 到 Quantum Probability。
三個概念:
Probability (density matrix)
Event (Measurement in Quantum computing)
Expectation (non commutative Probability theory)

分別都做了推廣:

Go back to the main quantum computing page

Adversary Method for Quantum lower bound

Adversary Method for Quantum lower bound 可以被視為是一種 計算 quantum query model 的 lower bound 的技巧:在 Grover's algorithm 裡面，已經推論過:
這裡證明 更 general 的情況:

還多提了幾個應用:

Adversary Method for Quantum lower bound 大家看看唄:

Go back to the main quantum computing page

Grover's algorithm and query complexity

在討論完 Grover's algorithm 以後，我們就可以來討論所謂的quantum computing的計算模型

query model + query complexity

Go back to Main page Notes for Complexity theory

Go back to the main quantum computing page

Grover's algorithm

Grover's algorithm 應該可以算是最有名的 quantum algorithm 之一。
題目是這樣:
假設有一個box，裡面有很多Ball (n 個). 有一個是正確答案。其他不是。 你要拿幾次球，才可以拿到正確答案?
這問題根本就沒任何辦法，如果要保證中: 要n次 才能中。
就算randomized 的拿，也沒有任何差別。

Go back to the main quantum computing page


這個問題比很多NP complete更難。因為這些問題，還有某種結構: 比方說3 sat, hamiltonian cycle, maximum cut,.........
都可以暴力解，但都要2^n time.不過神奇的事情是
Grover's algorithm 只需要 開根號 n 的 queries. 就可以做到，或是說 開根號 n 的steps.   

最後我們可以證明，開根號n 是optimal的最佳解法。

更general approach 可以看
Adversary Method for Quantum lower bound

Superdense coding and quantum teleportation

Superdense coding and quantum teleportation 

Really simple protocal convey quantum state or classical bits via sharing the bell state.

Go back to the main quantum computing page

all copyrights reserved

hope if this note help you, you can introduce this website to other people.

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

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