(3.230.76.48) 您好!臺灣時間:2021/04/12 14:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉穎駿
研究生(外文):Ying-Chun Liu
論文名稱:量子群組測試
論文名稱(外文):Quantum Group Testing with k-selective Families
指導教授:蔡錫鈞蔡錫鈞引用關係陳榮傑陳榮傑引用關係
指導教授(外文):Shi-Chun TsaiRong-Jaye Chen
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:67
中文關鍵詞:量子計算群組測試selective family量子搜尋演算法
外文關鍵詞:quantum computationgroup testingselective familyGrover's algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:150
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
我們將會在這篇論文中提出量子群組測試的演算法。
群組測試這個問題已有五十年的歷史。
Clementi et al. 於 2001 年提出了 k-selective family。
而 Indyk 則在 2002 年提出了一個較簡單的 k-selective family 造法。
這個 k-selective family 正好可以用來解決群組測試問題。
這篇論文中我們先介紹 Grover 的量子搜尋演算法,
然後我們將合併 $k$-selective family 及量子搜尋演算法,
來解決群組測試問題。
這樣可以得到更好的時間複雜度。

We describe the quantum group testing algorithm.
Group testing problem has a history of research
in the early days of computer science.
In 2001, Clementi et al. introduce the k-selective family which
can be used to solve this problem.
Indyk provides a explicit construction method for the k-selective family
in 2002.
In this thesis, we first explain Grover's quantum search algorithm.
Then we involve the k-selective system with quantum computation
to solve the group testing problem with a better time complexity.

Contents
Chinese Abstract i
English Abstract ii
Contents iii
List of Figures v
List of Tables vi
1 Introduction 1
1.1 The Rest of This Thesis . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notation and Symbols . . . . . . . . . . . . . . . . . . . . . . 2
2 Quantum Mechanics and Computation 5
2.1 Quantum bits . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Dirac Ket/Bra Notation . . . . . . . . . . . . . . . . . 5
2.1.2 Single qubit . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 Multiple qubits . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Single qubit gates . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Multiple qubit gates . . . . . . . . . . . . . . . . . . . 12
2.3 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Quantum Algorithms . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.1 Quantum Search algorithm . . . . . . . . . . . . . . . . 22
3 Combinatorial Group Testing 27
3.1 Introduction to Group Testing . . . . . . . . . . . . . . . . . . 27
3.2 k-selective family . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 coin-weighting problem . . . . . . . . . . . . . . . . . . . . . . 36
4 Quantum Search with k-selective family 41
4.1 Prepared Unitary Operation . . . . . . . . . . . . . . . . . . . 43
4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Conclusion 53
Bibliography 56

[1] Michel Boyer, Gilles Brassard, Peter Hyer, and Alain Tapp. Tight
bounds on quantum searching. Technical Report PP-1996-11, 30, 1996.
[2] Gilles Brassard, Peter Hyer, and Alain Tapp. Quantum counting. Lec-
ture Notes in Computer Science, 1443:820+, 1998.
[3] Bogdan S. Chlebus, Leszek Gasieniec, Anna Ostlin, and John Michael
Robson. Deterministic radio broadcasting. In Automata, Languages and
Programming, pages 717{728, 2000.
[4] Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Selective
families, superimposed codes, and broadcasting on unknown radio networks.
In Proceedings of the twelfth annual ACM-SIAM symposium on
Discrete algorithms, pages 709{718. ACM Press, 2001.
[5] David Deutsch. Quantum theory, the Church-Turing principle and the
universal quantum computer. Proceedings of the Royal Society of London
Ser. A, A400:97{117, 1985.
[6] Ding-Zhu Du and Frank K. Hwang. Combinatorial Group Testing and
its Application. World Scientic, 2nd edition, 2000.
[7] Christoph Durr and Peter Hyer. A quantum algorithm for nding the
minimum, 1996.
[8] R. P. Feynman. Quantum-mechanical computers. Journal of the Optical
Society of America B-Optical Physics, 1:464, 1984.
[9] R. P. Feynman. Quantum-mechanical computers. Foundations of
Physics, 16:507{531, 1986.
[10] Richard P. Feynman. Simulating physics with computers. Int. J. of The.
Phys., 21:467, 1982.
[11] S. J. Glaser, T. Schulte-Herbruggen, M. Sieveking, O. Schedletzky, N. C.
Nielsen, O. W. Sorensen, and C. Griisigner. Unitary control in quantum
ensembles: Maximizing signal intensity in coherent spectroscopy.
Science, 280:421{425, 1998.
[12] G. A. Goldin. Gauge transformations for a family of nonlinear
schrodinger equations. nmp?, 4:6{11, 1997.
[13] Robert B. Griths and Chi-Sheng Niu. Semiclassical fourier transform
for quantum computation. Phys. Rev. Lett., 76:3228, 1996. Also arXiv,
quant-ph/951107.
[14] Lov. K. Grover. A fast quantum mechanical algorithm for database
search. In , 28th Annual ACM Symposium on the Theory of Computing
(STOC), pages 212{219, May 1996.
[15] Lov K. Grover. Quantum computers can search rapidly by using almost
any transformation. Los Alamos e-Print Archive, December 1997.
[16] Lov K. Grover. Quantum mechanics helps in searching for a needle in a
haystack. Los Alamos e-Print Archive, June 1997.
[17] Piotr Indyk. Explicit constructions of selectors and related combinatorial
structures, with applications. In Proceedings of the thirteenth annual
ACM-SIAM symposium on Discrete algorithms, pages 697{704. ACM
Press, 2002.
[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and
Quantum Information. Cambridge University Press, rst edition, 2002.
[19] Eleanor Rieel and Wolfgang Polak. An introduction to quantum
computing for non-physicists. ACM Computing Surveys, 32:300{335,
September 2000.
[20] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms
and factoring. In IEEE Symposium on Foundations of Computer
Science, pages 124{134, 1994.
[21] Peter W. Shor. Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer. SIAM Journal on Com-
puting, 26(5):1484{1509, 1997.
[22] David R. Simon. On the power of quantum computation. In Proceed-
ings of the 35th Annual Symposium on Foundations of Computer Sci-
ence, pages 116{123, Los Alamitos, CA, 1994. Institute of Electrical and
Electronic Engineers Computer Society Press.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔