小波轉換為了解決傅立葉轉換的不足而誕生，傅立葉轉換在處理非平穩訊號時具有缺陷，只能分析含有哪些頻率成分，對於訊號彼此出現的先後順序並不能正確判讀。而小波轉換基底，具備有限長度和隨時間衰減之特性，能夠同時獲取時域及頻率資訊，彌補傅立葉轉換的缺陷。
量子電腦透過位元獨特的「量子疊加」和「量子糾纏」特性，對比傳統電腦的運算步驟被位元數所限制，量子位元能夠同時產生0和1的疊加態，跳脫線性關係，往指數型運算邁進，傳統電腦需要上萬年才能解決的運算，量子電腦只要短時間即能完成。
本文目的是將小波轉換與量子電腦做結合，成為新的「量子小波理論」。選用離散小波轉換中，最為廣泛使用的多貝西小波為研究主題，利用矩陣分解、量子排列、以及量子邏輯閘設計方法，將其實現至量子電路上。
最終成果是將古典多貝西D8小波，成功在量子電路上實現。以基礎一位元邏輯閘和CNOT邏輯閘組合出多貝西D8小波轉換之完整量子電路，同時計算此電路設計需要的時間與空間複雜度。
最後將設計完成的量子邏輯電路，加上量子容錯理論，估算容錯前後所需代價之差異。

Wavelet transform was born in order to solve the shortcomings of Fourier transform. Fourier transform has defects in processing non-stationary signals. It can only analyze which frequency components it contains, and cannot correctly interpret the order in which the signals appear. The wavelet transform base has the characteristics of finite length and decrease with time, which can obtain time domain and frequency information at the same time to compensate for the defects of Fourier transform.

Quantum computers use the unique "quantum superposition" and "quantum entanglement" characteristics of qubits. Compared with traditional computers, the calculation steps are limited by the number of bits. Qubits can generate superposition states of 0 and 1 at the same time.

The purpose of this article is to combine wavelet transform with quantum computers to become a new "quantum wavelet theory." In the discrete wavelet transform, the most widely used Daubechies wavelet transform is selected as the research topic, and it is realized on the quantum circuit by matrix decomposition, quantum arrangement, and quantum logic gate design methods.

The final result is to successfully implement the classical Daubechies D8 wavelet on a quantum circuit. Combine the basic one-bit logic gate and the CNOT logic gate to form a complete quantum circuit of the Daubechies D8 wavelet transform, and calculate the time and space complexity required for the circuit design.

Finally, the designed quantum logic circuit is added with quantum fault tolerance theory to estimate the difference in cost before and after fault tolerance.

[1] Brecht, B., et al. "Photon temporal modes: a complete framework for quantum information science." Physical Review X 5.4 (2015): 041017.
[2] Bennett, Charles H. "Logical reversibility of computation." IBM journal of Research and Development 17.6 (1973): 525-532.
[3] Bennett, Charles H., and Peter W. Shor. "Quantum information theory." IEEE transactions on information theory 44.6 (1998): 2724-2742.
[4] Steane, Andrew. "Quantum computing." Reports on Progress in Physics 61.2 (1998): 117.
[5] Gruska, Jozef. Quantum computing. Vol. 2005. London: McGraw-Hill, 1999.
[6] O'brien, Jeremy L. "Optical quantum computing." Science 318.5856 (2007): 1567-1570.
[7] Maggiore, Michele. "Quantum groups, gravity, and the generalized uncertainty principle." Physical Review D 49.10 (1994): 5182.
[8] Deutsch, David. "Quantum theory, the Church–Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985): 97-117.
[9] Shor, Peter W. "Quantum computing." Documenta Mathematica 1.1000 (1998): 1.
[10] De Wolf, Ronald. "Quantum Computation and Shor's Factoring Algorithm." CWI and University of Amsterdam (1999).
[11] Arute, Frank, et al. "Quantum supremacy using a programmable superconducting processor." Nature 574.7779 (2019): 505-510.
[12] Cirac, Juan Ignacio, and Peter Zoller. "A scalable quantum computer with ions in an array of microtraps." Nature 404.6778 (2000): 579-581.
[13] Farhi, Edward, and Sam Gutmann. "Analog analogue of a digital quantum computation." Physical Review A 57.4 (1998): 2403.
[14] Deutsch, David. "Quantum theory, the Church–Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985): 97-117.
[15] Mermin, N. David. Quantum computer science: an introduction. Cambridge University Press, 2007.
[16] Bracewell, Ronald Newbold, and Ronald N. Bracewell. The Fourier transform and its applications. Vol. 31999. New York: McGraw-Hill, 1986.
[17] Winograd, Shmuel. "On computing the discrete Fourier transform." Mathematics of computation 32.141 (1978): 175-199.
[18] Rao, Raghuveer. "Wavelet transforms." Encyclopedia of imaging science and technology (2002).
[19] Daubechies, Ingrid, and Wim Sweldens. "Factoring wavelet transforms into lifting steps." Journal of Fourier analysis and applications 4.3 (1998): 247-269.
[20] Farge, Marie. "Wavelet transforms and their applications to turbulence." Annual review of fluid mechanics 24.1 (1992): 395-458.
[21] Holschneider, Matthias, et al. "A real-time algorithm for signal analysis with the help of the wavelet transform." Wavelets. Springer, Berlin, Heidelberg, 1990. 286-297.
[22] Donoho, David L. "Interpolating wavelet transforms." Preprint, Department of Statistics, Stanford University 2.3 (1992): 1-54.
[23] Heil, Christopher E., and David F. Walnut. "Continuous and discrete wavelet transforms." SIAM review 31.4 (1989): 628-666.
[24] Cohen, Albert, Ingrid Daubechies, and Pierre Vial. "Wavelets on the interval and fast wavelet transforms." (1993).
[25] Xiong, Zixiang, Kannan Ramchandran, and Michael T. Orchard. "Wavelet packet image coding using space-frequency quantization." IEEE transactions on image processing 7.6 (1998): 892-898.
[26] Learned, Rachel E., and Alan S. Willsky. "A wavelet packet approach to transient signal classification." Applied and computational Harmonic analysis 2.3 (1995): 265-278.
[27] Klappenecker, Andreas. "Wavelets and wavelet packets on quantum computers." Wavelet Applications in Signal and Image Processing VII. Vol. 3813. International Society for Optics and Photonics, 1999.
[28] Daubechies, I., ORTHONORMAL BASES OF COMPACTLY SUPPORTED WAVELETS. Communications on Pure and Applied Mathematics, 1988. 41(7): p. 909-996.
[29] A theory for multiresolution signal decomposition: the wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Pattern Analysis and Machine Intelligence, IEEE Transactions on, IEEE Trans. Pattern Anal. Mach. Intell., 1989(7): p. 674.
[30] Wickerhauser, M.V., <Lectures on Wavelet Packet Algorithms.pdf>. 1991.
[31] Adaptive transforms for image coding using spatially varying wavelet packets. IEEE Transactions on Image Processing, Image Processing, IEEE Transactions on, IEEE Trans. on Image Process., 1996(7): p. 1197.
[32] Fast Full-Search-Equivalent Pattern Matching Using Asymmetric Haar Wavelet Packets. IEEE Transactions on Circuits and Systems for Video Technology, Circuits and Systems for Video Technology, IEEE Transactions on, IEEE Trans. Circuits Syst. Video Technol., 2018(4): p. 819.
[33] Hoyer, P., Efficient Quantum Transforms. 1997.
[34] Fijany, A. and C.P. Williams, Quantum Wavelet Transforms: Fast Algorithms and Complete Circuits. 1998.
[35] Hai-Sheng, L., et al., The multi-level and multi-dimensional quantum wavelet packet transforms. Scientific Reports, 2018
[36] https://images.app.goo.gl/Y987xKj5xgGvt8Yr9
[37] Cain, Michael E., et al. "Fast-Fourier transform analysis of signal-averaged electrocardiograms for identification of patients prone to sustained ventricular tachycardia." Circulation 69.4 (1984): 711-720.
[38] Guo, Chenlei, Qi Ma, and Liming Zhang. "Spatio-temporal saliency detection using phase spectrum of quaternion fourier transform." 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2008.
[39] Rioux, Marc, P. Boulanger, and T. Kasvand. "Segmentation of range images using sine wave coding and Fourier transformation." Applied optics 26.2 (1987): 287-293.
[40] https://community.sw.siemens.com/s/article/what-is-the-fourier-transform
[41] Zhou, Shumin, Bin Tang, and Rui Chen. "Comparison between non-stationary signals fast Fourier transform and wavelet analysis." 2009 International Asia Symposium on Intelligent Interaction and Affective Computing. IEEE, 2009.
[42] Perraudin, Nathanaël, and Pierre Vandergheynst. "Stationary signal processing on graphs." IEEE Transactions on Signal Processing 65.13 (2017): 3462-3477.
[43] Keselbrener, Laurence, and Solange Akselrod. "Selective discrete Fourier transform algorithm for time-frequency analysis: method and application on simulated and cardiovascular signals." IEEE Transactions on Biomedical Engineering 43.8 (1996): 789-802.
[44] Pei, Soo-Chang, and Jian-Jiun Ding. "Fractional Fourier transform, Wigner distribution, and filter design for stationary and nonstationary random processes." IEEE Transactions on Signal Processing 58.8 (2010): 4079-4092.
[45] MacIsaac, Dawn, Philip A. Parker, and Robert N. Scott. "The short-time Fourier transform and muscle fatigue assessment in dynamic contractions." Journal of Electromyography and Kinesiology 11.6 (2001): 439-449.
[46] https://www.itread01.com/content/1550297724.html
[47] Griffin, Daniel, and Jae Lim. "Signal estimation from modified short-time Fourier transform." IEEE Transactions on Acoustics, Speech, and Signal Processing 32.2 (1984): 236-243.
[48] Nawab, S., T. Quatieri, and Jae Lim. "Signal reconstruction from short-time Fourier transform magnitude." IEEE Transactions on Acoustics, Speech, and Signal Processing 31.4 (1983): 986-998.
[49] Kwok, Henry K., and Douglas L. Jones. "Improved instantaneous frequency estimation using an adaptive short-time Fourier transform." IEEE transactions on signal processing 48.10 (2000): 2964-2972.
[50] Allen, Jont B., and Lawrence R. Rabiner. "A unified approach to short-time Fourier analysis and synthesis." Proceedings of the IEEE 65.11 (1977): 1558-1564.
[51] Bentley, Paul M., and J. T. E. McDonnell. "Wavelet transforms: an introduction." Electronics & communication engineering journal 6.4 (1994): 175-186.
[52] Chakrabarti, Chaitali, Mohan Vishwanath, and Robert M. Owens. "Architectures for wavelet transforms: A survey." Journal of VLSI signal processing systems for signal, image and video technology 14.2 (1996): 171-192.
[53] Rioul, Olivier, and Patrick Flandrin. "Time-scale energy distributions: A general class extending wavelet transforms." IEEE Transactions on Signal Processing 40.7 (1992): 1746-1757.
[54] Gurley, Kurtis, and Ahsan Kareem. "Applications of wavelet transforms in earthquake, wind and ocean engineering." Engineering structures 21.2 (1999): 149-167.
[55] Ovanesova, A. V., and Luis E. Suarez. "Applications of wavelet transforms to damage detection in frame structures." Engineering structures 26.1 (2004): 39-49.
[56] Wong, Man Wah. Wavelet transforms and localization operators. Vol. 136. Springer Science & Business Media, 2002.
[57] Youssef, Omar AS. "Fault classification based on wavelet transforms." 2001 IEEE/PES Transmission and Distribution Conference and Exposition. Developing New Perspectives (Cat. No. 01CH37294). Vol. 1. IEEE, 2001.
[58] Claypoole, Roger, et al. "Nonlinear wavelet transforms for image coding." Conference Record of the Thirty-First Asilomar Conference on Signals, Systems and Computers (Cat. No. 97CB36136). Vol. 1. IEEE, 1997.
[59] Alsberg, Bjørn K., Andrew M. Woodward, and Douglas B. Kell. "An introduction to wavelet transforms for chemometricians: A time-frequency approach." Chemometrics and Intelligent Laboratory Systems 37.2 (1997): 215-239.
[60] Lewis, A. S., and G. Knowles. "Video compression using 3D wavelet transforms." Electronics Letters 26.6 (1990): 396-398.
[61] DeVore, Ronald A., Björn Jawerth, and Bradley J. Lucier. "Image compression through wavelet transform coding." IEEE Transactions on information theory 38.2 (1992): 719-746.
[62] Lewis, Adrian S., and G. Knowles. "Image compression using the 2-D wavelet transform." IEEE Transactions on image Processing 1.2 (1992): 244-250.
[63] Averbuch, Amir, Danny Lazar, and Moshe Israeli. "Image compression using wavelet transform and multiresolution decomposition." IEEE Transactions on Image Processing 5.1 (1996): 4-15.
[64] Schlosshauer, Maximilian. "Quantum decoherence." Physics Reports 831 (2019): 1-57.
[65] Mazzola, Laura, Jyrki Piilo, and Sabrina Maniscalco. "Sudden transition between classical and quantum decoherence." Physical review letters 104.20 (2010): 200401.
[66] Calderbank, A. Robert, and Peter W. Shor. "Good quantum error-correcting codes exist." Physical Review A 54.2 (1996): 1098.
[67] Knill, Emanuel, and Raymond Laflamme. "Theory of quantum error-correcting codes." Physical Review A 55.2 (1997): 900.
[68] Barends, Rami, et al. "Superconducting quantum circuits at the surface code threshold for fault tolerance." Nature 508.7497 (2014): 500-503.
[69] Raussendorf, Robert, Jim Harrington, and Kovid Goyal. "Topological fault-tolerance in cluster state quantum computation." New Journal of Physics 9.6 (2007): 199.
[70] Fowler, Austin G., et al. "Surface codes: Towards practical large-scale quantum computation." Physical Review A 86.3 (2012): 032324.
[71] Barends, Rami, et al. "Superconducting quantum circuits at the surface code threshold for fault tolerance." Nature 508.7497 (2014): 500-503.
[72] Fowler, Austin G., Ashley M. Stephens, and Peter Groszkowski. "High-threshold universal quantum computation on the surface code." Physical Review A 80.5 (2009): 052312.
[73] Wang, David S., Austin G. Fowler, and Lloyd CL Hollenberg. "Surface code quantum computing with error rates over 1%." Physical Review A 83.2 (2011): 020302.
[74] Bravyi, Sergey, and Jeongwan Haah. "Magic-state distillation with low overhead." Physical Review A 86.5 (2012): 052329.
[75] Meier, Adam M., Bryan Eastin, and Emanuel Knill. "Magic-state distillation with the four-qubit code." arXiv preprint arXiv:1204.4221 (2012).
[76] Eastin, Bryan, and Emanuel Knill. "Restrictions on transversal encoded quantum gate sets." Physical review letters 102.11 (2009): 110502.
[77] Vasmer, Michael, and Dan E. Browne. "Universal quantum computing with 3D surface codes." arXiv preprint arXiv:1801.04255 (2018).
[78] Gidney, Craig, and Austin G. Fowler. "Efficient magic state factories with a catalyzed CCZ rangle to 2T rangle transformation." Quantum 3 (2019): 135.
[79] Vasmer, Michael, and Dan E. Browne. "Three-dimensional surface codes: Transversal gates and fault-tolerant architectures." Physical Review A 100.1 (2019): 012312.
[80] Brown, Benjamin J. "A fault-tolerant non-Clifford gate for the surface code in two dimensions." Science Advances 6.21 (2020): eaay4929.