量子計算與量子資訊科學是一門新興的研究領域，藉著結合了量子力學以及新的物理定律，提供給我們更進階的途徑，來解決傳統計算機所難以克服的問題。在目前的文獻當中，已經有許多驚人的量子演算法被開發出來，同時亦證明了量子電腦比目前的傳統電腦更具效能。由於量子計算可能潛藏的衝擊與重要性，量子資訊科學已經吸引了越來越多的研究者，從事未來奈米科學與資訊科技的創新性開發。

在本論文中，我們提出了一個整合型的量子網路架構，以提供量子行動裝置達到量子無線通訊的服務。為了達到量子通訊，傳送端與接收端之間必須事先共享有量子糾纏態。而量子糾纏態的共享，通常可以藉由先行產生某些EPR序對，再經由量子固網將其分配給傳送與接收端。而且，為了降低未來鋪設量子有線網路的成本，此論文提供了一量子交換機的電路。此量子交換機利用了我們所提出之量子合併演算法，以致於可以很快的將所有輸入的量子資料，轉換至其目的接口。此外，本論文亦策劃了一量子的行動網路架構，以構成無線擷取和骨幹網路之間的通訊介面。這些網路設備主要是負責為量子行動裝置，提供分程傳送量子狀態的服務。最後，藉由我們所建立之量子路由機制，將使得所有的量子無線裝置擁有與任何有線或無線的量子裝置通訊的能力，以達成量子無線通訊的目標。

總結來說，本論文整合了量子固定骨幹網路、量子路由演算法、以及量子無線網路設備，以便於提供量子行動通訊的環境。除此之外，本論文亦已針對所提的網路架構，進行了可行性的分析。本論文的成果將有助於促進未來量子行動網路之建立與實現。

Quantum computation and quantum information science (QIS) whose study combines the exploration of quantum mechanics and new physical principals provide us with advanced tools to solve the hard problems in conventional Turing machines. In literature, many outstanding quantum algorithms have been developed to illustrate that quantum-based computers are more powerful than traditional computers. Due to its potential impact and significance, QIS has drawn more and more attentions for further research and innovations in the future development of nanoscience and information technology.

In this dissertation, we aim at providing an integrated quantum network architecture for quantum mobile devices to achieve quantum wireless communications. First of all, this dissertation proposes the quantum switching circuits that can switch each input quantum data to its target port quickly. To fulfill quantum communication, it is necessary for both sender and receiver to share some entangled quantum states. In general, that is often achieved by generating some EPR pairs and distributing them through the quantum fixed networks. Nevertheless, our quantum switching utilizing the presented quantum merge sorting as a subroutine can greatly reduce the cost in constructing quantum wired networks. In addition, this dissertation also devises a wireless network architecture that constitutes the radio interface between the radio access and fixed network systems. Those components act as intermediate nodes for quantum mobile devices to relay their quantum states. Finally, based on the quantum routing mechanism, quantum mobile nodes are able to communicate with any wired or wireless quantum equipments wirelessly even if they do not share entanglement directly.

In conclusion, this dissertation integrates the quantum fixed backbone networks, quantum routing mechanism, and the wireless network components so as to provide a quantum mobile communication environment. Besides, the feasibility of the proposed network architecture is also verified. Based on these achievements, the field of the quantum wireless communication would be driven further into the real-world applications.

[Amb99] A. Ambainis, “A better lower bound for quantum algorithms searching an ordered list,” in Proc. of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 352-357, 1999.
[ANT+02] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, “Dense Quantum Coding and Quantum Finite Automata,” Journal of the ACM, vol. 49, pp. 496-511, July 2002.
[Aru01] A. J. Arul, “Impossibility of comparing and sorting quantum states,” ArXive e-print quant-ph/0107085, 2001.
[Aud06] J. Audretsch. Entangled World: The Fascination of Quantum Information and Computation. John Wiley & Sons, 2006.
[ASY02] A. Ambainis, A. Smith, and K. Yang, “Extracting Quantum Entanglement (General Entanglement Purification Protocols),” in Proc. of the 17th IEEE Annual Conference on Computational Complexity, May 2002, pp. 82-91.
[AZ02] D. P. Agrawal, Q. A. Zeng. Introduction to Wireless and Mobile Systems. Brooks Cole, Aug 2002.
[Bar95] A. Barenco, “A universal two-bit gate for quantum computation,” Proc. Roy. Soc. Lond. A, vol. 449, pp. 679-683, 1995.
[BB84] C. Bennett and G. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” in Proc. of IEEE International Conference on Computers, Systems and Signal Processing, pp. 175-179, 1984.
[BBC+93] C. H. Bennett, G. Brassard, C. Crépeau, R. Josza, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels,” Phys. Rev. Lett., 70:1895-1899, 1993.
[BBC+95] A. Barenco, C. Bennett, R. Cleve, D. P. Divincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin and H. Weinfurter, “Elementary Gates for Quantum Computation,” Phys. Rev. A, 52(5), pp. 3457-3467, 1995.
[BBE92] C. H. Bennett, G. Brassard, and A. K. Ekert, “Quantum cryptography,” Scientific American, pp. 50-57, Oct 1992.
[BBP+96] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, “Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels,” Phys. Rev. Lett., vol. 76, pp. 722-725, 1996.
[BCG+02] H. Barnum, C. Crépeau, D. Gottesman, A. Smith, and A. Tapp, “Authentication of Quantum Messages,” in Proc. of the 43th Annual IEEE Symposium on the Foundations of Computer Science, pp. 449-458, Nov. 2002.
[BCS04] G. Benenti, G. Casati, and G. Strini. Principles of Quantum Computation and Information. World Scientific, 2004.
[BH99] M. Butler and P. Hartel, “Reasoning about Grover’s Quantum Search Algorithm Using Probabilistic wp,” ACM Transactions on Programming Languages and Systems, vol. 21, pp. 417-429, May 1999.
[BHM96] E. Biham, B. Huttner, and T. Mor, “Quantum cryptographic network based on quantum memories,” Phys. Rev. A, vol. 54, pp. 2651-2658, Oct. 1996.
[BL05] T. Beth and G. Leuchs. Quantum Information Processing. John Wiley & Sons, 2005.
[Bra70] G. H. Brandley, “Algorithm and Bound for the Greatest Common Divisor of n Integers,” Communication of ACM, vol. 13, July 1970.
[BS96] E. Bach and J. Shallit, Algorithmic Number Theory, Volume 1: Efficient Algorithms, MIT Press, 1996.
[BVK98] S. Bose, V. Vedral, and P. L. Knight, “Multiparticle generalization of entanglement swapping,” Phys. Rev. A, vol. 57, no. 2, pp. 822-829, 1998.
[Chu00] I. L. Chuang, “Quantum algorithm for clock synchronization,” Phys. Rev. Lett., 85:2006, Aug 2000.
[CLR+01] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Sep. 2001.
[Coh98] H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1991.
[Cop94] D. Coppersmith, “An approximate Fourier transform useful in quantum factoring,” IBM Research Report RC, 19642 1994.
[CS96] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” Phys. Rev. A, 54:1098, 1996.
[CT02] K. W. Cheng and C. C. Tseng, “Quantum full adder and subtractor,” Electronics Letters, vol. 38, pp. 1343-1344, Oct. 2002.
[CW06a] S. T. Cheng and C.-Y. Wang, “Quantum Switching and Quantum Merge Sorting,” IEEE Trans. Circuits and Systems I: Regular Papers, vol. 53, no. 2, pp. 316-325, Feb. 2006.
[CW06b] S. T. Cheng and C.-Y. Wnag, “Quantum Greatest Common Divisor Algorithm and Modular Homogenous Equations,” submitted to SIAM Journal on Computing, 2006
[CWT05] S. T. Cheng, C.-Y. Wang, and M. H. Tao, “Quantum Communication for Wireless Wide-Area Networks,” IEEE Journal on Selected Areas in Communications, pp. 1424-1432, July 2005.
[DBC+99] W. Dür, H. J. Briegel, J. I. Cirac, and P. Zoller, “Quantum repeater based on entanglement purification,” Phys. Rev. A, vol. 59, pp. 169-181, 1999.
[Die82] D. Dieks, “Communication by EPR devices,” Phys. Lett. A, 92(6), pp. 271-272, 1982.
[DiV95a] D. P. DiVincenzo, “Quantum computation,” Science, vol. 270, pp. 255-261, 1995.
[DiV95b] D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Phys. Rev. A, vol. 51(2), 1995, pp. 1015-1022.
[FGS+99] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Invariant quantum algorithms for insertion into an ordered list,” ArXive e-print quant-ph/9901059, 1999.
[Fun03] K. Funahashi, “The Controlled-U and Unitary Transformation in Two Qudit,” ArXive e-print quant-ph/0304078, 2003.
[Got97] D. Gottesman, “Stabilizer Codes and Quantum Error Correction,” Ph.D. thesis, California Institute of Technology, CA, 1997.
[Gro96] L. Grover, “A fast quantum mechanical algorithm for database search,” in Proc. of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212-219, 1996.
[Hal02] S. Hallgren, “Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem,” in Proc. of the 34th Annual ACM Symposium on Theory and Computing, pp. 653-658, 2002.
[Her96] I. N. Herstein, Abstract Algebra, Wiley Text Books, 1996.
[HNS01] P. Høyer, J. Neerbek, Y. Shi, “Quantum complexities of ordered searching, sorting and element distinctness,” in Proc. of the 28th International Colloquium on Automata, Languages and Programming, pp. 62-73, 2001.
[JAD+00] R. Jozsa, D. S. Abrams, J. P. Dowling, and C. P. Williams, “Quantum Clock Synchronization Based on Shared Prior Entanglement,” Phys. Rev. Lett. 85, pp. 2010-2013, Aug. 2000.
[Jeb93] T. Jebelean, “A generalization of the binary GCD algorithm,” in Proc. of the 1993 ACM International Symposium on Symbolic and Algebraic Computation, pp. 111-116, July 1993.
[JM96] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” in Mobile Computing, T. Imielinski and H. Korth, Eds. Norwell, MA: Kluwer, 1996, pp. 153-181.
[Kan98] B. Kane, “A silicon-based nuclear spin quantum computer,” Nature, 393:133-137, 1998.
[Kit95] A. Y. Kitaev, “Quantum measurements and the Abelian stabilizer problem,” ArXive e-print quant-ph/9511026, 1995.
[Kla03] H. Klauck, “Quantum Time-Space Tradeoffs for Sorting,” in Proc. of the 35th ACM Symposium on Theory of Computing, pp. 69-76, 2003.
[Knu98] D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley, 1998.
[KSW04] H. Klauck, R. Spalek, and R. del Wolf, “Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs,” ArXive e-print quant-ph /0402123, July 2004.
[Lan61] R. Landauer, “Irreversibility and heat generation in the computing process,” IBM F. Res. Dev., vol. 5, pp. 183, 1961.
[Leh38] D. H. Lehmer, “Euclid’s Algorithm for Large Numbers,” American Mathematical Monthly, vol. 45, no. 4, pp. 227-233, Apr. 1938.
[Llo93] S. Lloyd, “A potentially realizable quantum computer,” Science, vol. 261, pp. 1569-1571, 1993.
[MN98] C. Moore and M. Nilsson, “Parallel Quantum Computation and Quantum Codes,” ArXive e-print quant-ph/9808027, 1998.
[MRR04] C. Moore, D. Rockmore, and A. Russell, “Generic Quantum Fourier Transforms,” in Proc. of the ACM-SIAM Symposium on Discrete Algorithms, 2004.
[NC00] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, England, 2000.
[NS82] D. Nassimi and S. Sahni, “Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network,” Journal of the Association for Computing Machinery, vol. 29, pp. 642-667, July 1982.
[NS02] A. Nayak and J. Salzman, “On communication over an entanglement- assisted quantum channel,” in Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp. 689-704, May 2002.
[OCC+03] M. Oskin, F. T. Chong, I. L. Chuang, and J. Kubiatowicz, “Building Quantum Wires: The Long and the Short of it,” in Proc. of the 30th Annual International Symposium on the Computer Architecture, pp. 374-385, 2003.
[Rap01] T. S. Rappaport. Wireless Communications Principles and Practice. Prentice Hall PTR, Dec 2001.
[RT99] E. Royer and C. K. Toh, “A review of current routing protocols for ad hoc mobile wireless networks,” IEEE Personal Communications, vol. 6, no. 2, pp. 46-55, April 1999.
[Sho94] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proc. of the 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 124-134, 1994.
[Sho97] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput., vol. 26, pp. 1484-1509, 1997.
[Sor94] J. Sorenson, “Two fast GCD algorithms,” Journal of Algorithms, vol. 16, pp. 110-144, 1994.
[Sor95] J. Sorenson, “An analysis of Lehmer’s Euclidean GCD algorithm,” in Proc. of the 1995 ACM International Symposium on Symbolic and Algebraic Computation, pp. 254-258, July 1995.
[SPH+04] S. Scheel, J. Pachos, E. A. Hinds, and P. L. Knight, “Quantum Gates and Decoherence,” ArXive e-print quant-ph/0403152, 2004.
[SRO04] M. K. Shukla, R. Ratan and A. Y. Oruc, “A Quantum Self-Routing Packet Switch,” in Proc. of the 38th Annual Conference on Information Sciences and Systems, Mar. 2004.
[Ste96] A. M. Steane, “Error correcting codes in quantum theory,” Phys. Rev. Lett., 77:793, 1996.
[TK02] I. M. Tsai and S. Y. Kuo, “Digital Switching in the Quantum Domain,” IEEE Trans. Nanotechnology, vol. 1, pp. 154-164, Sep. 2002.
[TKH+04] I. M. Tsai, S. Y. Kuo, S. L. Huang, Y. C. Lin, and T. T. Chen, “Experimental Realization of an NMR Quantum Switch,” ArXive e-print quant-ph/ 0405170, 2004.
[TKW02] I. M. Tsai, S. Y. Kuo, and David S. L. Wei, “Quantum Boolean Circuit Approach for Searching and Unordered Database,” in Proc. of the 2002 2nd IEEE Conference on Nanotechnology, pp. 325-318, Aug. 2002.
[VW04] F. Vatan and C. Williams, “Optimal Quantum Circuits for General Two-Qubit Gates,” Phys. Rev. A 69, 032315, 2004.
[Web95] K. Weber, “The accelerated integer GCD algorithm,” ACM Trans. Mathematical Software, vol. 21, pp. 111-122, 1995.
[WZ82] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” Nature, vol. 299, pp. 802-803, 1982.
[ZZH+93] M. Zukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert, ““Event-Ready-Detectors” Bell Experiment via Entanglement Swapping,” Phys. Rev. Lett. 71, pp. 4287-4290, 1993.