量子計算理論之研究(I)

Abstract

本計畫將從計算理論(computational complexity)的角度研究量子計算(quantum computation)的計 算能力。吾人期望找尋一般量子計算中的複雜度等級(complexity class),即BQP，相對應於一般 傳統計算機之隨機演算法(probabilistic computation)之複雜度等級,即BPP，之間的集合包含關 係。若能找出一問題屬於BQP，但不屬於BPP，則將可確定量子計算確實優於傳統計算機模型。 反之，若可證明BQP=BPP，則顯示量子計算將可由傳統方式模擬,這表示我們將可找到不錯的 隨機演算法來作因數分解。 以現有之計算理論對於量子計算之初步研究結果顯示，對於大多數的布林函數，量子計算均無 法如同「質因數分解」問題一般給出指數倍加快(exponential speed-up)，由於實現量子計算之成 本極鉅，吾人希望藉由計算理論之角度，仔細探討量子計算之真實能力。 研究方向將包括: 1. 以通訊複雜度(communication complexity)角度，研究多台量子電腦間合作解決問題時傳輸 所需耗費的資料量大小，其中吾人將著重於研究「指紋法(fingerprinting method)」及相關問 題之通訊協定所能處理的範圍。 2. 以計數複雜度(counting complexity)角度，並配合「相對化(relativized)」的證明技巧，吾人 期望能定義新的複雜度等級(complexity class)使BQP 之位階能被更加確定。並將試圖發掘 「非相對化(unrelativized)」之結果，以便更加真實描繪BQP 與其餘複雜度等級之包含關係。 3. 以決策樹複雜度(decision tree complexity)角度，瞭解一般布林函數轉化為決策樹後之查詢複 雜度(query complexity)，並試圖改進現有理論之下限邊界值(lower bounds)。

This research will study the computational power of quantum computation, from the computational complexity-theoretic point. We want to find the set relationship among the common complexity class of quantum computation, BQP, and its probabilistic counterpart in classical computation, BPP. If we could find a problem, which resides in BQP, but not in BPP, then quantum computation is really a superior computation model than traditional computers. On the other hand, if we could show that BQP = BPP. Then quantum computation would be of not much use since it could be done in classical ways. The results to date show that for most of Boolean functions, quantum computer could not give exponential speed-ups as it does on the integer factoring problem. Due to the high cost of realizing quantum computers physically, we want to study the true power of quantum computation in order to predict its usefulness. Our research would focus on three aspects: 1. Communication complexity: we want to study the communication resources required on data transmission between quantum computers. We would especially focus on the 「fingerprinting method」, and find the set of problems, which it could be applied to. 2. Counting complexity: with the method of relativization, we would like to define a new complexity classes in which the role of BQP with existing classes could be understood better. We will also pursuit unrelativized results in which more accurate relationships among quantum and classical classes could be devised. 3. Decision tree complexity: we would want to know more of the query complexities of general Boolean functions under the quantum computation model, and study on the possibilities of improving the existing bounds. This could generate some potential on the classical circuit complexity.