請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/23117
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 郭斯彥 | |
dc.contributor.author | Yi-Lin Ju | en |
dc.contributor.author | 朱怡霖 | zh_TW |
dc.date.accessioned | 2021-06-08T04:42:46Z | - |
dc.date.copyright | 2009-08-20 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-06 | |
dc.identifier.citation | [1] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, pp. 1484–1509, 1997.
[2] L. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212–219, 1996. [3] C. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proceedings of IEEE International Conference on Computers Systems and Signal Processing, pp. 175–179, 1984. [4] C.-M. Yu, I.-M. Tsai, Y.-H. Chou, and S.-Y. Kuo, “Improving the network flow problem using quantum search,” in Proceedings of the 2007 IEEE Conference on Nanotechnology, pp. 1126–1129, Aug. 2007. [5] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp, “Tight bounds on quantum searching,”Fortschritte der Physik, vol. 46, pp. 493–506, 1998. [6] C. Zalka, “Grover’s quantum searching algorithm is optimal,” Physical Review A, vol. 60, pp. 2746–2751, 1999. [7] G. Chen, S. A. Fulling, and J. Chen, “Generalization of grover’s algorithm to multiobject search in quantum computing, part I, continuous time and discrete time,” in Mathematics of Quantum Computation (R. K. Brylinski and G. Chen, eds.), pp. 135– 160, CRC Press, 2002. [8] B. Ofer, S. Daniel, and S. Yishai, “Analysis of grover’s quantum search algorithm as a dynamical system,” Physical Review A, vol. 68, p. 022326, 2003. [9] J. Roland and N. J. Cerf, “Quantum-circuit model of hamiltonian search algorithms,”Physical Review A, vol. 68, p. 062311, 2003. [10] S. Aaronson, “Lower bounds for local search by quantum arguments,” in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 465–474, 2004. [11] A. N. Soklakov and R. Schack, “Efficient state preparation for a register of quantum bit.” http://arxiv.org/abs/quant-ph/0408045. [12] C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum.” http://xxx.lanl.gov/quant-ph/9607014. [13] H. Buhrman, C. Durr, M. Heiligman, P. H. yer, F. Magniez, M. Santha, and R. de Wolf, “Quantum algorithms for element distinctness,” in 16th IEEE Annual Conference on Computational Complexity, pp. 131–137, 2001. [14] Z. DIAO, Z. M. Suhail, and G. CHEN, “A quantum circuit design for Grover’s algorithm,” Zeitschrift f ¨ur Naturforschung. A, vol. 57, pp. 701–708, 2002. [15] L. Xiao and J. A. Jones, “Robust logic gates and realistic quantum computation,”Physical Review A, vol. 73, no. 3, p. 032334, 2006. [16] I.-M. Tsai and S.-Y. Kuo, “An algorithm for minimum space quantum boolean circuits construction,” Journal of Circuits, Systems, and Computers, vol. 15, no. 5, pp. 719–738, 2006. [17] A. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters, vol. 67, no. 6, pp. 661–663, 1991. [18] C. Bennett, “Quantum cryptography using any two nonorthogonal states,” Physical Review Letters, vol. 68, no. 21, pp. 3121 – 2124, 1992. [19] C. Erven, C. Couteau, R. Laflamme, and G. Weihs, “Entangled quantum key distribution over two free-space optical links,” Optics Express, vol. 16, no. 21, pp. 16840–16853, 2008. [20] “Id quantique sa.” http://www.idquantique.com/. [21] “Magiq technologies.” http://www.magiqtech.com/. [22] J. Liu, S. Rao, B. Li, and H. Zhang, “Opportunities and challenges of peer-to-peer internet video broadcast,” in Proceedings of the IEEE, vol. 96, pp. 11–24, 2008. [23] C.-Y. Chong and S. Kumar, “Sensor networks: evolution, opportunities, and challenges,” in Proceedings of the IEEE, vol. 91, pp. 1247–1256, 2003. [24] V. Karimipour, A. Bahraminasab, and S. Bagherinezhad, “Entanglement swapping of generalized cat states and secret sharing,” Physical Review A, vol. 65, p. 042320, Apr 2002. [25] M. ˙ Zukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert, “‘‘event-ready-detectors’’Bell experiment via entanglement swapping,” Physical Review Letters, vol. 71, pp. 4287–4290, Dec 1993. [26] Y.-L. Ju, I.-M. Tsai, and S.-Y. Kuo, “Quantum circuit design and analysis for database search applications,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 54, pp. 2552–2563, 2007. [27] I. M. Tsai, S. Y. Kuo, and D. Wei, “Quantum boolean circuit approach for searching an unordered database,” in Proceedings of the 2002 IEEE Conference on Nanotechnology, pp. 315–318, 2002. [28] I.-M. Tsai and S.-Y. Kuo, “Quantum boolean circuit construction and layout under locality constraint,” in Proceedings of the 2001 IEEE Conference on Nanotechnology, pp. 111–116, 2001. [29] C.-Y. Lu, S.-A.Wang, and S.-Y. Kuo, “Quantum boolean circuits construction using tabulation method,” in Proceedings of the 2004 IEEE Conference on Nanotechnology, pp. 596–598, 2004. [30] D. P. Divincenzo, “The physical implementation of quantum computation,” Fortschritte der Physik, vol. 48, no. 9-11, pp. 771–783, 2000. [31] T. D. Ladd, J. R. Goldman, F. Yamaguchi, Y. Yamamoto, E. Abe, and K. M. Itoh, “An all silicon quantum computer,” Physical Review Letters, vol. 89, p. 017901, 2002. [32] P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt, and A. G. White, “Grover’s search algorithm : an optical approach,” Journal of Modern Optics, vol. 47, pp. 257–266, 2000. [33] I. M. Tsai, S. Y. Kuo, S. L. Huang, Y. C. Lin, and T. T. Chen, “Experimental realization of an NMR quantum switch,” in Proceedings of the 2004 ERATO conference on Quantum Information Science, 2004. [34] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000. [35] D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Physical Review A, vol. 51, pp. 1015–1022, Feb 1995. [36] A. Barenco, “A universal two-bit gate for quantum computation,” in Proceedings of the Royal Society, vol. 449, pp. 679–683, 1995. [37] “Data encryption standard.” http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf. [38] “RSA’s DES challenge iii.” http://www.rsa.com/rsalabs/node.asp?id=2108. [39] “Distributed.net.” http://www.distributed.net/. [40] “EFF DES cracker.” http://www.eff.org/. [41] Y. L. Ju, I. M. Tsai, and S. Y. Kuo, “Performing authenticated encryption with nanoscale phenomenon,” in Proceedings of the 2005 IEEE Conference on Nanotechnology, 2005. [42] D. Micciancio and S. Panjwani, “Optimal communication complexity of generic multicast key distribution,” IEEE/ACM Transactions on Networking, vol. 16, pp. 803–813, Aug. 2008. [43] D. Liu, P. Ning, and W. Du, “Group-based key predistribution for wireless sensor networks,” ACM Transactions on Sensor Networks, vol. 4, no. 2, pp. 1–30, 2008. [44] M. Zukowski, A. Zeilinger, and H. Weinfurter, “Entangling photons radiated by independent pulsed sources,” in Fundamental Problems in Quantum Theory (D. M. Greenberger and A. Zelinger, eds.), vol. 755 of New York Academy Sciences Annals, p. 91, 1995. [45] S. Bose, V. Vedral, and P. L. Knight, “Multiparticle generalization of entanglement swapping,” Physical Review A, vol. 57, pp. 822–829, Feb 1998. [46] J. Bouda and V. Buzek, “Entanglement swapping between multi-qudit systems,”Journal of Physics A: Mathematical and General, vol. 34, pp. 4301–4311, 2001. [47] T. Gao, F. L. Yan, and Z. X. Wang, “Deterministic secure direct communication using ghz states and swapping quantum entanglement,” Journal of Physics A: Mathematical and General, vol. 38, no. 25, pp. 5761–5770, 2005. [48] J. Lee, S. Lee, J. Kim, and S. D. Oh, “Entanglement swapping secures multiparty quantum communication,” Physical Review A, vol. 70, p. 032305, Sep 2004. [49] Z.-j. Zhang and Z.-x. Man, “Multiparty quantum secret sharing of classical messages based on entanglement swapping,” Physical Review A, vol. 72, p. 022303, Aug 2005. [50] W. D¨ur, G. Vidal, and J. I. Cirac, “Three qubits can be entangled in two inequivalent ways,” Physical Review A, vol. 62, p. 062314, Nov 2000. [51] M. Fitzi, N. Gisin, and U. Maurer, “Quantum solution to the byzantine agreement problem,” Physical Review Letters, vol. 87, p. 217901, Nov 2001. [52] J. Jaewoo, P. Young-Jai, L. Jinhyoung, J. Jingak, and K. Inbo, “Quantum secure communication via a w state,” Journal of the Korean Physical Society, vol. 46, no. 4, pp. 763–768, 2005. [53] M. H. A. Khan and M. A. Perkowski, “Quantum ternary parallel adder/subtractor with partially-look-ahead carry,” Journal of Systems Architecture: the EUROMICRO Journal, vol. 53, no. 7, pp. 453–464, 2007. [54] R. B. Griffiths and C.-S. Niu, “Semiclassical fourier transform for quantum computation,”Physical Review Letters, vol. 76, pp. 3228–3231, Apr 1996. [55] L. Hales and S. Hallgren, “An improved quantum fourier transform algorithm and applications,” in FOCS ’00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, (Washington, DC, USA), p. 515, IEEE Computer Society, 2000. [56] N. Yoran and A. J. Short, “Efficient classical simulation of the approximate quantum fourier transform,” Physical Review A, vol. 76, no. 4, p. 042321, 2007. [57] Z. Zilic and K. Radecka, “Scaling and better approximating quantum fourier transform by higher radices,” IEEE Transactions on Computers, vol. 56, pp. 202–207,Feb. 2007. [58] S.-A.Wang, C.-Y. Lu, I.-M. Tsai, and S.-Y. Kuo, “Modified karnaugh map for quantum boolean circuits construction,” in proceedings of the 2003 IEEE Conference on Nanotechnology (IEEE-NANO 2003), vol. 2, pp. 651–654 vol. 2, Aug. 2003. [59] D. Maslov, G. Dueck, D. Miller, and C. Negrevergne, “Quantum circuit simplification and level compaction,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, pp. 436–444, March 2008. [60] S.-A. Wang, C.-Y. Lu, I.-M. Tsai, and S.-Y. Kuo, “An XQDD-based verification method for quantum circuits,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E91-A, no. 2, pp. 584–594, 2008. [61] Y.-H. Chou, I.-M. Tsai, and S.-Y. Kuo, “Quantum boolean circuits are 1-testable,” IEEE Transactions on Nanotechnology, vol. 7, pp. 484–492, July 2008. [62] M. Hillery, V. Buˇzek, and A. Berthiaume, “Quantum secret sharing,” Physical Review A, vol. 59, pp. 1829–1834, Mar 1999. [63] S. Bagherinezhad and V. Karimipour, “Quantum secret sharing based on reusable Greenberger-Horne-Zeilinger states as secure carriers,” Physical Review A, vol. 67, p. 044302, Apr 2003. [64] G. P. He, Z. D. Wang, and Y.-K. Bai, “Quantum secret sharing based on smolin states alone,” Physics A: Mathematical and Theoretical, vol. 41, p. 415304, 2008. [65] I.-C. Yu, F.-L. Lin, and C.-Y. Huang, “Quantum secret sharing with multilevel mutually (un)biased bases,” Physical Review A, vol. 78, no. 1, p. 012344, 2008. [66] S. Lin, Q.-Y. Wen, F. Gao, and F.-C. Zhu, “Improving the security of multiparty quantum secret sharing based on the improved bostr¨om-felbinger protocol,” Optics Communications, vol. 281, no. 17, pp. 4553 – 4554, 2008. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/23117 | - |
dc.description.abstract | 量子資訊科學是一利用量子物理特性作為資訊計算處理的新興研究學門。由於其跨領域的特性,各種傳統計算機領域在量子系統中有了新的研究探討空間和可能解決方案。在本論文中,我們研究量子搜尋的電路設計和量子糾纏態分享方式,並提出其在計算與安全通訊的可能應用。
首先,我們探討量子邏輯電路設計的細節以實現量子演算法及其兩種實際生活應用:電話簿搜尋和對稱式密碼系統破解。我們發現,量子搜尋演算法的效率雖然理論上可超越傳統演算法,但若要作為實際生活應用,還有許多需要考量的地方,例如其規模大小的影響等。為此我們定義適用的實際應用類型為某種類的單向函數,並為之設計出一種量子電路通用模型。 其次,我們提出一個量子糾纏態的安全分享傳輸協定,並且說明如何應用在點對點的資訊傳輸和多點廣播通訊。在這些應用中,只有合法的使用者可以正確的解密,其安全性是由量子的海森堡不確定性原理所保障。 最後,由於糾纏態分享協定中的量子通道在某些現實情境中可能無法取得,我們引用另一種糾纏態分享方式:糾纏態交換。我們提出兩種系統化的設計方式,在不需要傳送量子的情況下,可以直接且安全的分享應用所需的客制量子糾纏態。第一種方式是基於哈達馬矩陣,可以應用在認證的秘密資訊傳輸。第二種方式利用傅立葉轉換,可以更進一步的用在多量子多階層態的量子系統中及應用於秘密分享。不同於傳統密碼系統,這些量子通訊協定的安全性皆是根基於量子不可破的量子自然物理特性。 | zh_TW |
dc.description.abstract | Quantum information science is a fascinating field of research that studies how to process information based on quantum mechanisms. Due to its interdisciplinary nature, potential applications can be found almost in every field of computer science and electrical engineering. This thesis aims to discuss how to apply quantum mechanics to different applications in quantum computing and quantum cryptography, including quantum search and entanglement distribution.
First, based on Grover's quantum search algorithm, we give the quantum circuits for two applications, searching a phone book and breaking a symmetric cryptosystem. Although these two applications have quite different types of search criteria, they are both one-way functions and the proposed circuits can actually be generalized to any such problems. In this perspective, we propose a template of quantum circuits that is capable of searching the solution of a certain class of one-way functions. Second, we propose a protocol to securely distribute entanglement states and show how to use it to perform encrypted communication and broadcasting. In these applications, only legitimate users can decrypt the messages, whereas eavesdroppers, if existing, will receive garbage. In comparison with classical cryptographic protocols, the security of our protocols is guaranteed by the Heisenberg uncertainty principle of quantum mechanics, instead of unproven mathematical hard problems. Third, since the quantum channel needed in our entanglement sharing protocol might not be available under some circumstances, we study a quantum phenomenon called entanglement swapping, which can be used to distribute entanglement states without transmitting qubits. We propose two systematic methodologies so application-specific entanglement states among participants can be generated and distributed directly. The first method is based on Hadamard matrix, and can be used to perform authenticated encryption. The other one is based on quantum Fourier transform, and can be applied on multi-particle multi-level quantum systems. We describe its circuit design and demonstrate that it can be applied to distributed applications such as secret sharing. In comparison with classical cryptographic protocols, its security is guaranteed by quantum physics, instead of any unproven mathematic conjecture. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T04:42:46Z (GMT). No. of bitstreams: 1 ntu-98-D91921018-1.pdf: 1786087 bytes, checksum: ce94226f0018c18a0cecea6517253109 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 中文摘要 iii 英文摘要 iv 1 Introduction 1 2 Notations and Preliminaries 6 2.1 Quantum States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Quantum Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Entanglement Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Quantum Circuit Design and Analysis for Database Search Applications 15 3.1 Grover’s Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.2 Selective-Inversion . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.3 Inversion-about-Average . . . . . . . . . . . . . . . . . . . . . . 18 3.1.4 Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Searching in a Phone Book . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Breaking Symmetric Cryptosystems . . . . . . . . . . . . . . . . . . . . 24 3.4 Implementation and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 28 3.5 Template for One-Way Functions . . . . . . . . . . . . . . . . . . . . . . 31 4 Quantum Entanglement Sharing and Secure Message Broadcasting 33 4.1 Quantum Entanglement Sharing . . . . . . . . . . . . . . . . . . . . . . 34 4.1.1 The Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1.2 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Application Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.1 Classical Message Encryption . . . . . . . . . . . . . . . . . . . 41 4.2.2 Secure Message Broadcasting . . . . . . . . . . . . . . . . . . . 42 4.2.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . 46 5 Hadamard Based Entanglement Swapping and Authenticated Encryption 49 5.1 Entanglement Swapping Revisited . . . . . . . . . . . . . . . . . . . . . 50 5.2 Quantum Authentication Protocol . . . . . . . . . . . . . . . . . . . . . 52 5.3 Analysis and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6 Fourier Transform Based Entanglement Swapping and Distributed Quantum Secret Sharing 59 6.1 Fourier Transform Based Measurement Design . . . . . . . . . . . . . . 60 6.1.1 Two-particle Multi-level . . . . . . . . . . . . . . . . . . . . . . 60 6.1.2 Multi-particle Multi-level . . . . . . . . . . . . . . . . . . . . . 63 6.2 Circuit Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.2.1 Multi-level Quantum Gates . . . . . . . . . . . . . . . . . . . . . 66 6.2.2 Circuits for Entanglement Swapping . . . . . . . . . . . . . . . . 70 6.3 Distributed Secret Sharing and Other Applications . . . . . . . . . . . . . 73 6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7 Conclusions 77 References 79 | |
dc.language.iso | en | |
dc.title | 量子搜尋與糾纏態分享於量子資訊科學之應用 | zh_TW |
dc.title | Quantum Search and Entanglement Sharing for Applications in Quantum Information Science | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 蔡一鳴,雷欽隆,顏嗣鈞,王勝德,袁世一,陳錦洲,王國禎 | |
dc.subject.keyword | 量子資訊科學,量子搜尋,量子糾纏態, | zh_TW |
dc.subject.keyword | quantum information science,quantum search,quantum entanglement, | en |
dc.relation.page | 87 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2009-08-06 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 1.74 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。