Three-dimensional quantum wavelet transforms

Abstract

Wavelet transform is being widely used in the field of information processing. One-dimension and two-dimension quantum wavelet transforms have been investigated as important tool algorithms. However, three-dimensional quantum wavelet transforms have not been reported. This paper proposes a multi-level three-dimensional quantum wavelet transform theory to implement the wavelet transform for quantum videos. Then, we construct the iterative formulas for the multi-level three-dimensional Haar and Daubechies D4 quantum wavelet transforms, respectively. Next, we design quantum circuits of the two wavelet transforms using iterative methods. Complexity analysis shows that the proposed wavelet transforms offer exponential speed-up over their classical counterparts. Finally, the proposed quantum wavelet transforms are selected to realize quantum video compression as a primary application. Simulation results reveal that the proposed wavelet transforms have better compression performance for quantum videos than two-dimension quantum wavelet transforms.

Key words： wavelet transform; wavelet video coding; quantum wavelet transform; quantum information processing; quantum image processing

1 Introduction

Quantum principles provide significant improvements for information processing [1,2] and enable fast quantum algorithms for factorization [3], mapping [4], and database search [5,6]. The quantum circuit model is an essential quantum computer model [7] and promotes the efficient implementation of quantum algorithms such as quantum image processing [8-12] and quantum machine learning [13].

Classical wavelet transform [14] was widely used in information processing, such as image watermarking [15]. Its quantum counterpart, quantum wavelet transform (QWT), has also been used in quantum watermarking [16] and quantum image compression [17]. The QWT classifies as one-dimensional or multi-dimensional according to the types of data it acts on is one-dimension or multi-dimension [17]. The one-dimensional Haar QWT (1D-HQWT) and the one-dimensional Daubechies D4 QWT (1D-D4QWT) have been proposed and implemented by quantum circuits [18-21]. Using generalized tensor products [22], we have designed the multi-level 1D-HQWT and 1D-D4QWT [23], quantum wavelet packet transform [24], and two-dimensional quantum wavelet transforms [17]. The complexity of the classical fast wavelet transform is O(2^n) [25]. In contrast, the above quantum wavelet transforms can be implemented by O(n^3) basic operations. Thus, quantum wavelet transforms achieve exponentially speed up in comparison with their classical counterparts.

3D classical wavelet transform has been used currently in 3D image processing. For instance, 3D-WT can be directly applied to the 3D images themselves to realize the compression of 3D images [26]. Furthermore, 3D-WT expanded the 2D-WT to treat volumetric data and outperformed 2D-WT in volumetric image processing [27]. In addition, 3D-DWT is also a common technique for a spectral-spatial approach, which has the advantage of extracting the spatial and spectral information simultaneously [28]. Therefore, we believe that the quantum version of 3D-WT, 3D quantum wavelet transform (3D-QWT), has potential applications for 3D image processing, such as video compression and classification.

The 3D-WT for separable 3D wavelets can be implemented by 2D-WT followed by 1D-WT [29], but the corresponding 3D-QWT is not easy to be realized. Because the controlled operation entangles the different dimensions, a 3D-QWT cannot be implemented by combining a 2D-QWT and a 1D-QWT. I.e., the 3D-QWT is not simply a tensor product of three separable 1D-QWTs or a tensor product of one separable 1D-QWT and one 2D-QWT. Therefore, the algorithm for the 3D-QWT needs to be redesigned.

Inspired by the implementation method of the 2D quantum wavelet transform [17], we propose the multi-level 3D-HQWT and 3D-D4QWT in this paper. To build a complete framework of the QWT, we design the implementation circuits for the inverses of 3D-HQWT and 3D-D4QWT, respectively. Complexities of the proposed 3D-QWTs reveal that they are exponentially faster than their classical counterparts. We discuss quantum video compression as a primary application of the proposed 3D-QWTs. Simulation results demonstrate that the proposed wavelet transforms have better compression performance for quantum videos than two-dimension quantum wavelet transforms.

The rest of this paper is organized as follows. Section 2 introduces the background of quantum video representation and quantum wavelet transform. Section 3 presents the multilevel three-dimensional quantum wavelet transforms. In Section 4, we propose quantum video compression for the proposed 3D quantum wavelet transforms. Section 5 gives the simulation results and comparison analysis. Finally, conclusions and future works are drawn in Section 6.

2 Background knowledge

For clarity, we briefly introduce the quantum video representation of NASS proposed in [9]. In addition, we describe the perfect shuffle permutation, the generalized tensor product, and 1D quantum wavelet transforms.

2.1 Normal arbitrary superposition state (NASS)

The computational basis states |0⟩, |1⟩, and their dual states ⟨0| and ⟨1| can be expressed as

(1)\begin{array}{r}|0⟩=\left[\begin{array}{l}1\\ 0\end{array}\right],|1⟩=\left[\begin{array}{l}0\\ 1\end{array}\right],⟨0|=\left[10\right],⟨1|=\left[01\right].\end{array}

A basis state |k⟩ in a 2^n-dimensional Hilbert space and its dual state ⟨k| are defined as

(2)\begin{array}{r}\{\begin{array}{l}|k⟩=|k_{n-1}⟩\otimes |k_{n-2}⟩\otimes \cdots \otimes |k_0⟩=|k_{n-1}{k}_{n-2}\cdots k_0⟩,\\ ⟨k|=⟨k_{n-1}|\otimes ⟨k_{n-2}|\otimes \cdots \otimes ⟨k_0|=⟨k_{n-1}{k}_{n-2}\cdots k_0|,\end{array}\end{array}

where the decimal number k (k=0,1,\dots ,2^n-1) is expressed as k={\sum }_{j=0}^{n-1}{k}_j\times 2^j with k_0,k_1,\dots ,k_{n-1}\in \{0,1\}, and \otimes is a tensor product symbol.

A 2^n\times 2^m\times 2^h video can be represented by NASS as follows:

(3)\begin{array}{r}|{\mathrm{\Psi }}_{n,m,h}⟩=\sum _{x=0}^{2^n-1}\sum _{y=0}^{2^m-1}\sum _{t=0}^{2^h-1}{\theta }_{x,y,t}|x⟩|y⟩|t⟩,\end{array}

where |x⟩, |y⟩, and |t⟩ denote the video’s X-axis, Y-axis, and time-axis. {\theta }_{x,y,t} encodes the value of the pixel on the coordinate (x,y,t).

NASS can be prepared by the initialization method based on quantum circuits [30]. A quantum circuit consists of quantum gates [7]. Some basic gates and their corresponding matrices are shown in Fig.1 [23].

Fig.1 Notations for some basic gates

Full size|PPT slide

Two controlled gates with n control qubits and m target qubits are defined by [23,31,32]

(4)\begin{array}{r}{C}_n^j\left(U_{2^m}\right)=(|j⟩⟨j|)\otimes U_{2^m}+\sum _{i=0,i\ne j}^{2^n-1}\left((|i⟩⟨i|)\otimes I_{2^m}\right),\end{array}

and

(5)\begin{array}{r}{V}_n^j\left(U_{2^m}\right)=\left(U_{2^m}\otimes |j⟩⟨j|\right)+\sum _{i=0,i\ne j}^{2^n-1}\left(I_{2^m}\otimes (|i⟩⟨i|)\right),\end{array}

where U_{2^m} and I_{2^m} are 2^m\times 2^m unitary and identity matrices, respectively.

When n=1, m=1, and {\mathrm{U}}_{2^m}=X in Eqs. (4) and (5), we obtain controlled-NOT gates in Fig.2. Furthermore, C_2^3\left(X\right) is a Toffoli gate that can be used to realize quantum algorithms such as quantum arithmetic operations [33,34].

Fig.2 Quantum controlled-NOT gates. Control quantum bits can be 0 (indicated by white dots) or 1 (indicated by black dots)

Full size|PPT slide

2.2 Perfect shuffle permutations and generalized tensor products

A perfect shuffle permutation P_{n,m} is defined by [22]

(6)\begin{array}{r}(P_{n,m}{)}_{k,l}={\delta }_{v,z^{\prime }}{\delta }_{z,v^{\prime }},\end{array}

with k=vn+z, l=v^{\prime }m+z^{\prime }, 0\le v, , 0\le v^{\prime }, and . {\delta }_{x,y} is the Kronecker delta function, i.e., {\delta }_{x,y}=0 if x\ne y, otherwise {\delta }_{x,y}=1.

We give two examples of the perfect shuffle permutation as follows:

(7)\begin{array}{r}\{\begin{array}{l}{P}_{2^{n-1},2}=(P_{2^{n-2},2}\otimes I_2)(I_{2^{n-2}}\otimes P_{2,2}),\\ P_{2,2^{n-1}}=(I_2\otimes P_{2,2^{n-2}})(P_{2,2}\otimes I_{2^{n-2}}),\end{array}\end{array}

where P_{2,2} is a Swap gate. The implementation circuits for P_{2^{n-1},2} and P_{2,2^{n-1}} are presented in Fig.3.

Fig.3 The implementation circuits of P_{2^{n-1},2} and P_{2,2^{n-1}}. Circuits in the dashed boxes in (a) and (b) realize P_{2^{n-2},2} and P_{2,2^{n-2}}, respectively

Full size|PPT slide

A generalized tensor product \mathcal{A}\otimes \mathcal{B} is given by [22]

(8)\mathcal{A}\otimes \mathcal{B}=P_{m,n}Diag(\mathcal{A})P_{n,m}Diag(\mathcal{B}),

where the two sets \mathcal{A}=\left\{A^0,A^1,\dots ,A^{m-1}\right\} and \mathcal{B}= \left\{B^0,B^1,\dots ,B^{n-1}\right\} contain m matrices with the size n\times n and n matrices with the size m\times m, respectively. Diag(\mathcal{A}) and Diag(\mathcal{B}) are block-diagonal matrices.

2.3 1D quantum wavelet transforms

A single-level 1D-HQWT and its inverse are defined by [17,18,20,23] di

(9)\begin{array}{r}\{\begin{array}{l}{W}_{2^n}^H=P_{2^{n-1},2}\left(I_{2^{n-1}}\otimes H\right),\\ (W_{2^n}^H{)}^{-1}=\left(I_{2^{n-1}}\otimes H\right)P_{2,2^{n-1}},\end{array}\end{array}

with n>1 and W_2^H={(W_2^H)}^{-1}=H. The circuits for W_{2^n}^H and (W_{2^n}^H{)}^{-1} are presented in Fig.4.

Fig.4 The circuits for the single-level 1D-HQWT and its inverse. (a) W_{2^n}^H; (b) (W_{2^n}^H{)}^{-1}

Full size|PPT slide

We give a single-level 1D-D4QWT and its inverse as follows [17,23]:

(10)\begin{array}{r}\{\begin{array}{l}{F}_{2^n}=P_{2^{n-1},2}{D}_{2^n}^p,\\ F_{2^n}^{-1}=(D_{2^n}^p{)}^{-1}{P}_{2,2^{n-1}},\\ D_{2^n}^p=(I_{2^{n-1}}\otimes S_1)Q_{2^n}(I_{2^{n-1}}\otimes S_0)Q_{2^n}^{-1},\\ (D_{2^n}^p{)}^{-1}=Q_{2^n}(I_{2^{n-1}}\otimes S_0)Q_{2^n}^{-1}(I_{2^{n-1}}\otimes S_1),\end{array}\end{array}

with Q_{2^n}=(I_{2^{n-1}}\otimes X)(\{Q_{2^{n-1}},I_{2^{n-1}}\},\otimes I_2), Q_{2^n}^{-1}=(\{Q_{2^{n-1}}^{-1},I_{2^{n-1}}\}\otimes I_2)(I_{2^{n-1}}\otimes X), Q_2=Q_2^{-1}=X, and

S_0=\left[\begin{array}{cc}\sin {\displaystyle \frac{2\pi }{3}}& \cos {\displaystyle \frac{2\pi }{3}}\\ \cos {\displaystyle \frac{2\pi }{3}}& -\sin {\displaystyle \frac{2\pi }{3}}\end{array}\right],S_1=\left[\begin{array}{cc}-\sin {\displaystyle \frac{5\pi }{12}}& \cos {\displaystyle \frac{5\pi }{12}}\\ \cos {\displaystyle \frac{5\pi }{12}}& \sin {\displaystyle \frac{5\pi }{12}}\end{array}\right].

The circuits for the single-level 1D-D4QWT and its inverse are presented in Fig.5.

Fig.5 The circuits for the single-level 1D-D4QWT and its inverse. (a) D_{2^n}^p; (b) F_{2^n}; (c) (D_{2^n}^p{)}^{-1}; (d) F_{2^n}^{-1}

Full size|PPT slide

3 Multi-level 3D quantum wavelet transforms

The section gives the general theory for the multi-level 3D-QWT and the explicit forms of the multi-level 3D-HQWT and 3D-D4QWT.

3.1 The theory for the multi-level 3D-QWT

A video consisting of 2^h frames of the size 2^n\times 2^m can be represented as

(11)\begin{array}{r}{A}_{2^n,2^m,2^h}=({\mathrm{\Lambda }}_{2^n,2^m}^1,{\mathrm{\Lambda }}_{2^n,2^m}^2,\dots ,{\mathrm{\Lambda }}_{2^n,2^m}^{2^h}),\end{array}

where the matrix {\mathrm{\Lambda }}_{2^n,2^m}^p encodes the p-th frame.

Let a 2^n\times 2^m\times 2^h video A_0 be the input. Then, as an example of the multi-level 3D wavelet transform, we illustrate the decomposition scheme of a 2-level 3D classical wavelet transform in Fig.6 [35].

Fig.6 The decomposition scheme of the classical 2-level 3D wavelet transform

Full size|PPT slide

Applying a single-level 3D classical wavelet transform named wt3D to the video A_0, we obtain

(12)\begin{array}{r}wt3D(A_0)=\{A_1,B_1,C_1,D_1,E_1,F_1,G_1,L_1\},\end{array}

where A_1, B_1, C_1, D_1, E_1, F_1, G_1 and L_1 are 2^{n-1}\times 2^{m-1}\times 2^{h-1} sub-videos shown in Fig.6.

Similarly, we have

(13)\begin{array}{r}wt3D(A_{j-1})=\{A_j,B_j,C_j,D_j,E_j,F_j,G_j,L_j\}.\end{array}

Thus, the successive applications of the single-level wavelet transform implement the multi-level 3D wavelet transform. For instance, applying the 2-level 3D wavelet transform to the video A_0, we get

(14)\begin{array}{r}{A}_0\to \{\{A_2,B_2,C_2,D_2,E_2,F_2,G_2,L_2\},B_1,C_1,\dots ,L_1\}.\end{array}

To realize the multi-level 3D-QWT, we firstly define T_{n,m,h}^j and R_{n,m,h}^j as follows:

(15)\begin{array}{rl}{T}_{n,m,h}^j=& Diag(W_{2^{n-j+1}}\otimes W_{2^{m-j+1}}\otimes W_{2^{h-j+1}},I_{2^{s-3j+3}},I_{2^{s-3j+4}},I_{2^{s-3j+5}})\\ & \times (I_2\otimes P_{2^{n+m-2j+3},2}\otimes I_{2^{h-j+1}})(I_2\otimes P_{2^{n-j+1},2}\otimes I_{2^{m+h-2j+3}})\\ =& (I_2\otimes \{I_2\otimes \{I_2\otimes \{W_{2^{n-j+1}}\otimes W_{2^{m-j+1}}\otimes W_{2^{h-j+1}},I_{2^{s-3j+3}}\},\\ & I_{2^{s-3j+4}}\},I_{2^{s-3j+5}}\})(I_2\otimes P_{2^{n+m-2j+3},2}\otimes I_{2^{h-j+1}})\\ & \times (I_2\otimes P_{2^{n-j+1},2}\otimes I_{2^{m+h-2j+3}}),\end{array}

and

(16)\begin{array}{r}\begin{array}{l}{R}_{n,m,h}^j=(I_2\otimes P_{2,2^{n-j+1}}\otimes I_{2^{m+h-2j+3}})(I_2\otimes P_{2,2^{n+m-2j+3}}\otimes I_{2^{h-j+1}}),\end{array}\end{array}

with s=n+m+h and j\ge 2, where W_{2^{n-j+1}}, W_{2^{m-j+1}} and W_{2^{h-j+1}} are 2^{n-j+1}\times 2^{n-j+1}, 2^{m-j+1}\times 2^{m-j+1}, and 2^{h-j+1}\times 2^{h-j+1} wavelet kernel matrices.

The inverses of T_{n,m,h}^j and R_{n,m,h}^j are calculated by

(17)\begin{array}{rl}(T_{n,m,h}^j{)}^{-1}=& (I_2\otimes P_{2,2^{n-j+1}}\otimes I_{2^{m+h-2j+3}})(I_2\otimes P_{2,2^{n+m-2j+3}}\otimes I_{2^{h-j-1}})\\ & \times (I_2\otimes \{I_2\otimes \{I_2\otimes \{W_{2^{n-j+1}}^{-1}\otimes W_{2^{m-j+1}}^{-1}\otimes W_{2^{h-j+1}}^{-1},\\ & I_{2^{s-3j+3}}\},I_{2^{s-3j+4}}\},I_{2^{s-3j+5}}\}),\end{array}

and

(18)\begin{array}{r}\begin{array}{l}(R_{n,m,h}^j{)}^{-1}=(I_2\otimes P_{2^{n+m-2j+3},2}\otimes I_{2^{h-j+1}})(I_2\otimes P_{2^{n-j+1},2}\otimes I_{2^{m+h-2j+3}}),\end{array}\end{array}

with s=n+m+h.

Then, we design circuits for T_{n,m,h}^j and R_{n,m,h}^j and their inverses in Fig.7.

Fig.7 Circuits for T_{n,m,h}^j and R_{n,m,h}^j and their inverses. (a) T_{n,m,h}^j; (b) R_{n,m,h}^j; (c) (T_{n,m,h}^j{)}^{-1}; (d) (R_{n,m,h}^j{)}^{-1}

Full size|PPT slide

Two operators for i-level quantum wavelet transform are given by

(19)\begin{array}{r}\{\begin{array}{l}{Q}_f^i(2^n,2^m,2^h)=D_{n,m,h}^i\cdots D_{n,m,h}^2{D}_{n,m,h}^1,\\ Q_s^i(2^n,2^m,2^h)=L_{n,m,h}^1{L}_{n,m,h}^2\cdots L_{n,m,h}^i,\end{array}\end{array}

with s=n+m+h and

(20)\begin{array}{r}\{\begin{array}{l}{D}_{n,m,h}^1=W_{2^n}\otimes W_{2^m}\otimes W_{2^h},\\ D_{n,m,h}^2=T_{n,m,h}^2,\\ D_{n,m,h}^j=Diag(\tau )forj\ge 3,\\ \tau =\{T_{n,m,h}^j,I_{2^{s-3j+6}},\dots ,I_{2^{s-2}},I_{2^{s-1}}\},\\ L_{n,m,h}^1=I_{2^{n+m+h}},\\ L_{n,m,h}^2=R_{n,m,h}^2,\\ L_{n,m,h}^j=Diag(\ell )forj\ge 3,\\ \ell =\{R_{n,m,h}^j,I_{2^{s-3j+6}},\dots ,I_{2^{s-2}},I_{2^{s-1}}\}.\end{array}\end{array}

Assume that the function f(\cdot ) is equivalent to the quantum circuit implementing the storage of the video A_{2^n\times 2^m\times 2^h}. I.e., we store the video in the NASS state |{\mathrm{\Psi }}_{n,m,h}⟩ (see Eq. (3)) using

(21)\begin{array}{r}\begin{array}{l}|{\mathrm{\Psi }}_{n,m,h}⟩=f(A_{2^n,2^m,2^h})\\ =[u_{0,0}\cdots u_{0,2^m-1}{u}_{1,0}\cdots u_{1,2^m-1}\cdots u_{2^n-1,0}\cdots u_{2^n-1,2^m-1}{]}^T,\end{array}\end{array}

with the vector

(22)\begin{array}{r}{u}_{x,y}=\left[{\theta }_{x,y}^1{\theta }_{x,y}^2\cdots {\theta }_{x,y}^{2^h}\right],\end{array}

where {\theta }_{x,y}^j encodes the element of the matrix {\mathrm{\Lambda }}_{2^n,2^m}^j on the position (x,y).

We give the following theorem for an i-level 3D-QWT with i\ge 1:

Theorem 1. The i-level 3D quantum wavelet transform can be expressed by Q_s^i(2^n,2^m,2^h)Q_f^i(2^n,2^m,2^h), i.e.,

(23)\begin{array}{r}\begin{array}{l}f(W_{3D}^i(A_{2^n,2^m,2^h}))=Q_s^i(2^n,2^m,2^h)Q_f^i(2^n,2^m,2^h)f(A_{2^n,2^m,2^h}),\end{array}\end{array}

where W_{3D}^i(A_{2^n,2^m,2^h}) denotes an i-level 3D classical wavelet transform.

Proof From Eqs. (19) and (20), we obtain that Q_s^1(2^n,2^m,2^h)Q_f^1(2^n,2^m,2^h)=W_{2^n}\otimes W_{2^m}\otimes W_{2^h}. Therefore, Q_s^1(2^n,2^m,2^h)Q_f^1(2^n,2^m,2^h) is a single-level 3D-QWT, and it is also a single-level 3D quantum wavelet packet transform in [32], i.e.,

(24)\begin{array}{rl}f(W_{3D}^1(A_{2^n,2^m,2^h}))& =Q_s^1(2^n,2^m,2^h)Q_f^1(2^n,2^m,2^h)f(A_{2^n\times 2^m\times 2^h})\\ & =(W_{2^n}\otimes W_{2^m}\otimes W_{2^h})f(A_{2^n\times 2^m\times 2^h})\\ & =f\{A_1,B_1,C_1,D_1,E_1,F_1,G_1,L_1\}.\end{array}

Set

(25)\begin{array}{r}\{\begin{array}{l}{\mathrm{\Delta }}_i=\{A_i,B_i,C_i,D_i,E_i,F_i,G_i,L_i\},\\ {\mathrm{\Omega }}_i=\left[\begin{array}{l}f(B_i)\\ f(C_i)\\ f(D_i)\\ f(E_i)\\ f(F_i)\\ f(G_i)\\ f(L_i)\end{array}\right],\end{array}\end{array}

where the matrices A_i, B_i, C_i, D_i, E_i, F_i, G_i and L_i are shown in Fig.6.

For i\ge 2, we give the proof of the following equation:

(26)\begin{array}{r}{Q}_f^i(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})=\left[\begin{array}{c}f({\mathrm{\Delta }}_i)\\ {\mathrm{\Omega }}_{i-1}\\ {\mathrm{\Omega }}_{i-2}\\ ⋮\\ {\mathrm{\Omega }}_1\end{array}\right].\end{array}

Using Eqs. (7), (8), and (21), we calculate

(27)\begin{array}{r}\begin{array}{l}(I_2\otimes P_{2^{n+m-1},2}\otimes I_{2^{h-1}})(I_2\otimes P_{2^{n-1},2}\otimes I_{2^{m+h-1}})f({\mathrm{\Delta }}_1)=\left[\begin{array}{l}f(A_1)\\ {\mathrm{\Omega }}_1\end{array}\right],\end{array}\end{array}

and obtain

(28)\begin{array}{r}{Q}_f^2(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})=\left[\begin{array}{l}f({\mathrm{\Delta }}_2)\\ {\mathrm{\Omega }}_1\end{array}\right].\end{array}

It means that the Eq. (26) holds for i=2.

Thus, for j\ge 2, we have

(29)\begin{array}{r}{T}_{n,m,h}^{j}f({\mathrm{\Delta }}_{j-1})=\left[\begin{array}{l}f({\mathrm{\Delta }}_j)\\ {\mathrm{\Omega }}_{j-1}\end{array}\right].\end{array}

Suppose that Q_f^{i-1}(2^n,2^m,2^h)f(A_{2^n,2^m,2^h}) satisfies Eq. (26) for i\ge 3, we infer

(30)\begin{array}{r}\begin{array}{l}{Q}_f^i(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})\\ =D_{n,m,h}^i{Q}_f^{i-1}(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})\\ =D_{n,m,h}^i\left[\begin{array}{c}f({\mathrm{\Delta }}_{i-1})\\ {\mathrm{\Omega }}_{i-2}\\ {\mathrm{\Omega }}_{i-3}\\ ⋮\\ {\mathrm{\Omega }}_1\end{array}\right].\end{array}\end{array}

Combining Eqs. (20), (29), and (30), we conclude that the Eq. (26) holds.

Due to

(31)\begin{array}{r}{R}_{n,m,h}^j\left[\begin{array}{c}f(A_{j-1})\\ {\mathrm{\Omega }}_{j-1}\end{array}\right]=f({\mathrm{\Delta }}_{j-1}),\end{array}

using Eq. (26), we obtain

(32)\begin{array}{rl}& Q_s^i(2^n,2^m,2^h)Q_f^i(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})\\ & =Q_s^{i-1}(2^n,2^m,2^h)L_{n,m,h}^i{Q}_f^i(2^n,2^m,2^h)f(A_{2^n,2^m,2^h})\\ & =Q_s^{i-1}(2^n,2^m,2^h)\\ & \times \left[\begin{array}{c}f({\mathrm{\Delta }}_i,B_{i-1},C_{i-1},D_{i-1},E_{i-1},F_{i-1},G_{i-1},L_{i-1})\\ {\mathrm{\Omega }}_{i-2}\\ {\mathrm{\Omega }}_{i-3}\\ ⋮\\ {\mathrm{\Omega }}_1\end{array}\right]\\ & =f(W_{3D}^i(A_{2^n,2^m,2^h}))\end{array}

with i\ge 2.

Therefore, Q_s^i(2^n,2^m,2^h)Q_f^i(2^n,2^m,2^h) is an i-level 3D-QWT.　　　　　　　　　　　　　　　　　　　　　　□

According to Eqs. (19), (20), and Theorem 1, we design circuits for D_{n,m,h}^j, L_{n,m,h}^j, and the i-level 3D-QWT in Fig.8. Fig.8 shows that the i-level 3D-QWT is implemented by a non-iterative method.

Fig.8 Circuits for the i-level 3D-QWT. (a) D_{n,m,h}^j; (b) L_{n,m,h}^j; (c) The i-level 3D-QWT

Full size|PPT slide

3.2 Implementations of the multi-level 3D-HQWT and 3D-D4QWT

The Haar and Daubechies D4 wavelet transforms are the two well-known wavelet transforms. Therefore, this section gives an iterative method for constructing the multilevel 3D-HQWT and 3D-D4QWT.

3.2.1 The multi-level 3D-HQWT

Substituting the Haar wavelet kernel matrix W_{2^n}^H (see Eq. (9)) into Eqs. (15) and (20), we obtain the iterative version of D_{n,m,h}^j for 3D-HQWT:

(33)\begin{array}{r}\{\begin{array}{l}{D}_{n,m,h}^{H1}=W_{2^n}^H\otimes W_{2^m}^H\otimes W_{2^h}^H,\\ D_{n,m,h}^{H2}=(I_2\otimes \{I_2\otimes \{I_2\otimes \{D_{n-1,m-1,h-1}^{H1},I_{2^{s-3}}\},I_{2^{s-2}}\},I_{2^{s-1}}\})\\ \times (I_2\otimes P_{2^{n+m-1},2}\otimes I_{2^{h-1}})(I_2\otimes P_{2^{n-1},2}\otimes I_{2^{m+h-1}}),\\ D_{n,m,h}^{Hj}=Diag(D_{n,m,h}^{H(j-1)},I_{2^{s-3}},I_{2^{s-2}},I_{2^{s-1}}),\end{array}\end{array}

with s=n+m+h and j\ge 3.

Replacing D_{n,m,h}^j in Eq. (19) with D_{n,m,h}^{Hj}, we obtain

(34)\begin{array}{rl}{Q}_{fH}^i(2^n,2^m,2^h)& =D_{n,m,h}^{Hi}\cdots D_{n,m,h}^{H2}{D}_{n,m,h}^{H1}\\ & =Diag(Q_{fH}^{i-1}(2^{n-1},2^{m-1},2^{h-1}),I_{2^{s-3}},I_{2^{s-2}},\\ & I_{2^{s-1}})(I_2\otimes P_{2^{n+m-1},2}\otimes I_{2^{h-1}})(I_2\otimes P_{2^{n-1},2}\\ & \otimes I_{2^{m+h-1}})(W_{2^n}^H\otimes W_{2^m}^H\otimes W_{2^h}^H),\end{array}

with s=n+m+h.

Similarly, we also have

(35)\begin{array}{rl}{Q}_{sH}^i(2^n,2^m,2^h)=& R_{n,m,h}^{2}Diag(Q_{sH}^{i-1}(2^{n-1},2^{m-1},\\ & 2^{h-1}),I_{2^{n+m+h-3}},I_{2^{n+m+h-2}},I_{2^{n+m+h-1}}).\end{array}

Thus, the iteration of the i-level 3D-HQWT is given by

(36)\begin{array}{rl}{H}_{n,m,h}^i& =Q_{sH}^i(2^n,2^m,2^h)Q_{fH}^i(2^n,2^m,2^h)\\ & =(I_2\otimes P_{2,2^{n-1}}\otimes I_{2^{m-1}}\otimes P_{2^{h-1},2})(I_2\otimes \{I_2\\ & \otimes \{\{H_{n-1,m-1,h-1}^{i-1},I_{2^{s-3}}\}\otimes I_2,I_{2^{s-2}}\},I_{2^{s-1}}\})\\ & \times (I_2\otimes P_{2^{n+m-2},2}\otimes I_{2^{\mathrm{h}}})(P_{2^{n-1},2}{I}_{2^{m+h}})\\ & \times (I_{2^{n-1}}\otimes H\otimes I_{2^{m-1}}\otimes H\otimes I_{2^{h-1}}\otimes H)\end{array}

with s=n+m+h and the initial value

H_{n-i+1,m-i+1,h-i+1}^1=W_{2^{n-i+1}}^H\otimes W_{2^{m-i+1}}^H\otimes W_{2^{h-i+1}}^H.

Using Eq. (36), we design the circuit for the multi-level 3D-HQWT in Fig.9. We from Fig.9 infer the inverse transform of the 3D-HQWT in Fig.10.

Fig.9 The implementation circuits for the multi-level 3D-HQWT. (a) H_{n,m,h}^i,i\ge 2; (b) H_{n-i+1,m-i+1,h-i+1}^1

Full size|PPT slide

Fig.10 The implementation circuits for the inverse of the multi-level 3D-HQWT. (a) (H_{n,m,h}^i{)}^{-1},i\ge 2; (b) (H_{n-i+1,m-i+1,h-i+1}^1{)}^{-1}

Full size|PPT slide

For instance, we present the detailed circuit for H_{4,5,5}^3 in Fig.11.

Fig.11 The circuit for H_{4,5,5}^3. The circuit in the dashed box implements H_{3,4,4}^2

Full size|PPT slide

3.2.2 The multi-level 3D-D4QWT

Compared with the Haar wavelet, Daubechies wavelets, such as the Daubechies D4 wavelet, can be used to identify the missing frequency change part of the Haar wavelet transform. Similarly to the 3D-HQWT, we give the iterative formula of the i-level 3D-D4QWT as follows:

(37)\begin{array}{rl}{F}_{n,m,h}^i=& (I_2\otimes P_{2,2^{n-1}}\otimes I_{2^{m-1}}\otimes P_{2^{h-1},2})\\ & \times (I_2\otimes \{I_2\otimes \{\{F_{n-1,m-1,h-1}^{i-1},I_{2^{s-3}}\}\otimes I_2,I_{2^{s-2}}\},I_{2^{s-1}}\})\\ & \times (I_2\otimes P_{2^{n-1},2}\otimes I_{2^{m+h-1}})(F_{2^n}\otimes F_{2^m}\otimes D_{2^h}^p),\end{array}

with s=n+m+h and the initial value

F_{n-i+1,m-i+1,h-i+1}^1=F_{2^{n-i+1}}\otimes F_{2^{m-i+1}}\otimes F_{2^{h-i+1}}.

The circuits for the multi-level 3D-D4QWT and its inverse transform are presented in Fig.12 and Fig.13. For clarity, we illustrate an example of the 3-level 3D-D4QWT with n=4,m=5,h=5 in Fig.14.

Fig.12 The implementation circuits for the multi-level 3D-D4QWT. (a) F_{n,m,h}^i with i\ge 2; (b) F_{n-i+1,m-i+1,h-i+1}^1

Full size|PPT slide

Fig.13 The implementation circuits for the inverse of the multi-level 3D-D4QWT. (a) (F_{n,m,h}^i{)}^{-1} with i\ge 2; (b) (F_{n-i+1,m-i+1,h-i+1}^1{)}^{-1}

Full size|PPT slide

Fig.14 The circuit for F_{4,5,5}^3. The circuit in the dashed box implements F_{3,4,4}^2

Full size|PPT slide

3.3 The complexity analysis and comparison

3.3.1 The complexity analysis

A quantum circuit may consist of basic operations, such as single-qubit gates and controlled not-gates (CNOT) [7,31]. Therefore, the complexity of the quantum circuit can be regarded as the total number of basic operations [17,31]. For instance, the complexity analysis in [17] shows that the complexities of the controlled-H, controlled-S_0, controlled-S_1, and controlled-Swap gates with n qubits are all O(n).

Through the analysis for circuits in Fig.9 and Fig.11, we conclude that the i-level 3D-HQWT at most comprises O((n+m+h{)}^2) controlled-Swap gates and O((n+m+h)) controlled-H gates. Therefore, the complexity of the multi-level 3D-HQWT is O((n+m+h{)}^3). Similarly, we calculate that the complexity of the multi-level 3D-D4QWT is also O((n+m+h{)}^3). In contrast, the fast classical wavelet transform needs at least the linear complexity for 2^{n+m+h} data [25]. I.e., the complexity of the fast classical wavelet transform is greater than O(2^{n+m+h}). Thus, our proposed multi-level 3D-QWTs can offer an exponential speed-up over classical wavelet transforms.

3.3.2 The comparison of multi-level 3D-QWTs and 2D-QWTs

For clarity, we give two 3-level 1D-HQWTs H_4^3 and H_5^3 in Fig.15 [23], and a 3-level 2D-HQWT H_{4,5}^3 in Fig.16 [17].

Fig.15 The circuits for 3-level 1D-HQWTs H_4^3 and H_5^3. (a) H_4^3; (b) H_5^3

Full size|PPT slide

Fig.16 The circuit for the 3-level 2D-HQWT H_{4,5}^3

Full size|PPT slide

Comparing circuits in Fig.11, Fig.15, and Fig.16, we infer that the multi-level 3D-HQWT cannot be decomposed into three 1D-HQWTs, or a 1D-HQWT and a 2D-HQWT. The reason is that controlled operations entangle three dimensions of 3D-HQWT. Therefore, the proposed method for the multi-level 3D-HQWT is different from the technique for the 2D-HQWT in [17]. A similar conclusion can be drawn for the multi-level 3D-D4QWT.

4 Primary application: quantum video compression

Quantum state estimation (QSE) is an essential technique for quantum information processing [36]. The task of QSE is to retrieve the information of a quantum state by a series of measurements. Similarly, quantum image compression algorithms based on the multi-level 2D-QWTs were presented to reduce the number of quantum measurements [17]. We propose a method for quantum video compression in Algorithm 1 by modifying the quantum image compression algorithm.

Quantum compression ratio (QCR) is defined by

(38)\begin{array}{r}{Q}_r=\frac{2^{n+m+h}}{m_1},\end{array}

where m_1 amplitudes of the compressed state |{\mathrm{\Psi }}_{n,m,h}^c⟩ must be retrieved accurately from quantum systems. Therefore, Algorithm 1 can reduce the number of quantum measurements by about (1-1/Q_r)\times 100 percent to retrieve a classical video from quantum systems.

Full size|PPT slide

5 Simulations

5.1 Simulations of the multi-level 3D-QWTs in MATLAB

In this section, we simulate multi-level 3D-QWTs with a classical computer running in MATLAB R2017a and Windows 10 with 128GB RAM.

Suppose that the NASS state |{\mathrm{\Psi }}_{6,6,5}⟩=f({\mathrm{\Lambda }}_{2^6,2^6,2^5}) stores a 64\times 64\times 32 video {\mathrm{\Lambda }}_{2^6,2^6,2^5}. Q_1^i and Q_2^i are the matrix forms of quantum circuits for the i-level 3D-HQWT and 3D-D4QWT, respectively. Q_3^i and Q_4^i denote the inverses of Q_1^i and Q_2^i. Applying Q_1^i and Q_2^i to |{\mathrm{\Psi }}_{6,6,5}⟩, we implement the i-level wavelet decompositions of 3D-HQWT and 3D-D4QWT, respectively. Simulation results of a 64\times 64\times 8 video are illustrated in Fig.17 and Fig.18, which has done two levels of transformation. Applying Q_3^i and Q_4^i to transformed videos, we realize the wavelet reconstructions of 3D-HQWT and 3D-D4QWT.

Fig.17 Simulation results of the first two levels of the 3D-HQWT. (a) A 64\times 64\times 8 original video; (b) the transformed video for the 1-level 3D-HQWT; (c) the transformed video for the 2-level 3D-HQWT

Full size|PPT slide

Fig.18 Simulation results of the first two levels of the 3D-D4QWT. (a) A 64\times 64\times 8 original video; (b) the transformed video for the 1-level 3D-D4QWT; (c) the transformed video for the 2-level 3D-D4QWT

Full size|PPT slide

Comparisons of the proposed QWTs and corresponding classical wavelet transforms for a 64\times 64\times 32 video presented in Tab.1 reveal that the results for our proposed 3D-HQWT and 3D-D4QWT are equal to the corresponding classical wavelet transforms, disregarding machine computational truncation errors. Combining the complexity analysis in Section 3 and comparisons in Tab.1, we conclude that the proposed quantum wavelet transforms obtain the same results as their classical counterparts with an exponential speed-up.

Tab.1 Comparisons of the proposed QWTs and the corresponding classical wavelet transforms

Level	\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(V_1-W_1)	\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(V_2-{\mathrm{\Lambda }}_{2^6,2^6,2^5})	\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(V_3-W_3)	\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(V_4-{\mathrm{\Lambda }}_{2^6,2^6,2^5})
1	7\times {10}^{-12}	3.3\times {10}^{-11}	3.19\times {10}^{-9}	3.47\times {10}^{-11}
2	3.2\times {10}^{-11}	5.9\times {10}^{-11}	5.72\times {10}^{-9}	8.16\times {10}^{-11}
3	4.05\times {10}^{-10}	3.34\times {10}^{-10}	8.24\times {10}^{-9}	2.371\times {10}^{-10}
4	1.527\times {10}^{-9}	1.636\times {10}^{-9}	1.238\times {10}^{-8}	5.515\times {10}^{-10}
5	7.746\times {10}^{-9}	7.876\times {10}^{-9}	−	−

Note: symbols in Tab.1 are listed as follows,

\begin{array}{}\text{(40)}& \{\begin{array}{l}{V}_1=f^{-1}(Q_1^i|{\mathrm{\Psi }}_{6,6,5}⟩),\\ V_2=f^{-1}(Q_3^i{Q}_1^i{|{\mathrm{\Psi }}_{6,6,5}⟩}_1),\\ W_1=W_{3D}^i({\mathrm{\Lambda }}_{2^6,2^6,2^5},i{,}^{\prime }db{1}^{\prime }),\\ V_3=f^{-1}(Q_2^k|{\mathrm{\Psi }}_{6,6,5}⟩),\\ V_4=f^{-1}(Q_4^k{Q}_2^k{|{\mathrm{\Psi }}_{6,6,5}⟩}_3),\\ W_3=W_{3D}^k({\mathrm{\Lambda }}_{2^6,2^6,2^5},k{,}^{\prime }db{2}^{\prime }),\end{array}\end{array}

with 1\le i\le 5 and 1\le k\le 4, where W_{3D}^i({\mathrm{\Lambda }}_{2^6,2^6,2^5},i{,}^{\prime }db{1}^{\prime }) and W_{3D}^k({\mathrm{\Lambda }}_{2^6,2^6,2^5},k{,}^{\prime }db{2}^{\prime }) denote the classical 3D Haar and D4 wavelet transforms, respectively. f^{-1}(\cdot ) is the inverse operation of f(\cdot ) in (21). For instance, we can retrieve the transformed videos V_1 and V_3 from quantum systems using f^{-1}(\cdot ). norm() is a 2-norm function.

5.2 Simulation experiments of the multi-level 3D-QWTs on IBM quantum experience cloud platform

Since the quantum simulation must be more attractive to readers, we conduct experiments on 3D-HQWT and 3D-D4QWT on the IBM quantum experience (IBM-Q) cloud platform. We obtain probability results through quantum measurement operation to verify the feasibility of the 3D quantum wavelet transform.

The IBM-Q cloud platform currently offers a quantum information software toolkit Qiskit, an open-source quantum computing software development framework, to simulate quantum experiments based on python. The results can be expressed in probability histograms after the quantum circuits run on the quantum simulator and IBM quantum hardware.

Suppose that an 8\times 8\times 8 video in Fig.19 is stored in the following NASS state

Fig.19 An 8\times 8\times 8 original video

Full size|PPT slide

\begin{array}{}\text{(41)}& |{\mathrm{\Psi }}_{3,3,3}⟩=\sum _{x=0}^7\sum _{y=0}^7\sum _{t=0}^7{\theta }_{x,y,t}|x⟩|y⟩|t⟩.\end{array}

Then, the NASS state |{\mathrm{\Psi }}_{3,3,3}⟩ is performed by two-level 3D-HQWT and 3D-D4QWT. Nine qubits are required for the quantum circuit. Here, we experiment on IBM-Q’s Qiskit based on python, using IBM-Q’s 32-Qubits ibmq_qasm_simulator and setting the number of executions to a maximum of 8192 shots. The quantum circuit for the 2-level 3D-HQWT is illustrated in Fig.20. The probability histogram of the transformed video is presented in Fig.21.

Fig.20 Quantum circuit of an 8\times 8\times 8 video with 2-level 3D-HQWT. (a) The first part of the circuit; (b) the second part of the circuit

Full size|PPT slide

The symbol swap in Fig.20 denotes the Swap gate in Fig.1. Qiskit uses the “append” operation to add the controlled-Swap gates. The input |q{24}_0⟩|q{24}_1⟩\cdots |q{24}_8⟩ in Fig.20 corresponds to |x⟩|y⟩|t⟩ in (41). It shows that the input for IBM-Q’s Qiskit is the inverse order of the NASS state |{\mathrm{\Psi }}_{3,3,3}⟩. Therefore, we reverse the output binary string for IBM-Q’s Qiskit to get consistent results with the NASS state. For instance, the position “100000000” is the inverse of the fifth value “000000001” along the horizontal axis in Fig.21. It denotes the first pixel's coordinate in the second frame image of the transformed video. Therefore, the probabilities in the histogram denote normalized pixel values on the eight positions “000000000”, “000001001”, “000001000”, “000000001”, “001000001”, “001000000”, “001001000”, and “001001001”. The pixel values on the rest positions of the transformed video are approximately zero. From Eq. (41) and Fig.21, we can infer that the NASS state for the transformed video is

Fig.21 Probability histogram of an 8\times 8\times 8 video with 2-level 3D-HQWT after 8192 quantum measurements

Full size|PPT slide

\begin{array}{}\text{(42)}& \begin{array}{rl}& |{{\mathrm{\Psi }}_T}_{3,3,3}⟩\\ & =\sqrt{0.122}|000000000⟩+\sqrt{0.131}|001000000⟩\\ & +\sqrt{0.126}|000001000⟩+\sqrt{0.125}|001001000⟩\\ & +\sqrt{0.116}|000000001⟩+\sqrt{0.129}|001000001⟩\\ & +\sqrt{0.123}|000001001⟩+\sqrt{0.129}|001001001⟩.\end{array}\end{array}

Similarly, we give the quantum circuit and the probability histogram for the 2-level 3D-HQWT on IBM-Q’s Qiskit in Fig.22 and Fig.23. Results in Fig.21 and Fig.23 show that proposed 3D-QWTs are feasible on the IBM-Q cloud platform.

Fig.22 Quantum circuit of an 8\times 8\times 8 video with 2-level 3D-D4QWT. The symbols circuit401, circuit393, and circuit397 represent the NOT, S0, and S1 gates, respectively. (a) The first part of the circuit; (b) the second part of the circuit; (c) the third part of the circuit

Full size|PPT slide

Fig.23 Probability histogram of an 8\times 8\times 8 video with 2-level 3D-D4QWT after 8192 quantum measurements

Full size|PPT slide

5.3 Simulation of quantum video compressions

We simulate the quantum video compressions with a classical computer running in MATLAB R2017a and Windows 10 with 128GB RAM.

Consider the 128\times 128\times 32 video in Fig.21(a) as an example of quantum video compressions of multi-level 3D-HQWT (QVC-3D-HQWT) and 3D-D4QWT (QVC-3D-D4QWT). To further compare the multi-level 3D-QWTs and 2D-QWTs, we implement quantum video compressions by quantum image compressions based on the multi-level 2D-HQWT (QIC2DHQWT) and 2D-D4QWT (QIC2DD4QWT) performed separately for 32 frames [17].

Let H_M^3 and H_M^2 be the average values of the transformed video for the multilevel 3D-HQWT and 2D-HQWT, respectively. Then, thresholds {\lambda }_j^H for QVC-3D-HQWT and {\beta }_j^H for QIC2DHQWT can be calculated by

\begin{array}{}\text{(43)}& {\lambda }_j^H=a_j{H}_M^3,{\beta }_j^H=b_j{H}_M^2,\end{array}

with j=1,2,\dots ,10, a_j\in {\lambda }_a, b_j\in {\beta }_b, {\lambda }_a=\{5.95,5.64,5.35,5.05,4.75,4.45,4.15,3.85,3.55,3.25\}, and {\beta }_b=\{3.90,3.60,3.30,3.00,2.70,2.40,2.10,1.80,1.50,1.20\}.

Comparisons of QVC-3D-HQWT and QIC2DHQWT are presented in Fig.24. The horizontal and vertical coordinates denote the peak signal-to-noise ratio (PSNR) and quantum compression ratio (QCR). In addition, each solid line contains ten points corresponding to threshold values {\lambda }_j^H with j=1,2,\dots ,10. Similarly, each dashed line comprises ten points related to threshold values {\beta }_j^H with j=1,2,\dots ,10.

Fig.24 Comparisons of QVC-3D-HQWT and QIC2DHQWT. HW1=i and HW2=i (i=1,2,3,4,5) denote the i-level 3D-HQWT and 2D-HQWT, respectively

Full size|PPT slide

We calculate thresholds {\lambda }_j^D and {\beta }_j^D for QVC-3D-D4QWT and QIC2DD4QWT using

\begin{array}{}\text{(44)}& {\lambda }_j^D=a_j{D}_M^3,{\beta }_j^D=b_j{D}_M^2,\end{array}

where D_M^3 and D_M^2 are the average values of the transformed videos by the multilevel 3D-D4QWT and 2D-D4QWT, respectively. Then, we give comparisons of QVC-3D-D4QWT and QIC2DD4QWT in Fig.25.

Fig.25 Comparisons of QVC-3D-D4QWT and QIC2DD4QWT. DW1=k and DW2=k (k=1,2,3,4) denote the k-level 3D-D4QWT and 2D-D4QWT, respectively

Full size|PPT slide

We summarize the maximal QCRs with PSNR\approx 30 for simulation results in Tab.2. Simulation results for QVC-3D-HQWT and QVC-3D-D4QWT are presented in Fig.26.

Tab.2 QCR and PSNR for simulation results

QWTs	3D-HQWT	2D-HQWT	3D-D4QWT	2D-D4QWT
PSNR	30.39	30.40	30.14	30.81
QCR	29.08	12.94	22.06	11.61
Threshold	{\lambda }_6^H	{\beta }_4^H	{\lambda }_1^D	{\beta }_2^D
Level	5	5	4	4

Fig.26 Simulation results for QVC-3D-HQWT and QVC-3D-D4QWT. (a) An original video; (b) the compressed video by QVC-3D-HQWT; (c) the compressed video by QVC-3D-D4QWT

Full size|PPT slide

Finally, from Fig.24, Fig.25, and Tab.2, we conclude that the proposed 3D-QWTs have better compression performance than 2D-QWTs [17].

6 Conclusions and future works

In this paper, we have proposed the theory of the multi-level three-dimensional quantum wavelet transform. Then, we have designed the circuits for the multi-level 3D-HQWT and 3D-D4QWT by iterative methods. The complexity analysis showed that the proposed wavelet transforms for videos can be realized with the complexity O((n+m+h{)}^3). Therefore, they can exponentially speed up the wavelet transform computation compared to their classical counterparts. In addition, we have presented a quantum video compression algorithm based on the proposed three-dimensional quantum wavelet transforms. The simulation results revealed that the proposed 3D quantum wavelet transforms are superior to the existing 2D quantum wavelet transforms for quantum video compression. It implies that the proposed 3D wavelet transforms have great potential in quantum video processing.

For future works, we will extend the results to implement quantum versions of other wavelet transforms such as Daubechies D8 wavelet transform [37] and cross wavelet transform [38]. Furthermore, we will integrate the proposed quantum wavelet transforms with quantum machine learning to solve machine learning problems.

Acknowledgements

This work was supported by the Science and Technology Project of Guangxi (2020GXNSFDA238023), and the National Natural Science Foundation of China (Grant No .61762012).

References

1 Stajic J . The future of quantum information processing. Science, 2013, 339( 6124): 1163

2 Monroe C . Quantum information processing with atoms and photons. Nature, 2002, 416( 6877): 238–246

3 Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 124−134

4 Huang C, Zhang D, Song G . A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization. Frontiers of Computer Science, 2017, 11( 4): 622–631

5 Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 212−219

6 Long G, Liu Y . Search an unsorted database with quantum mechanics. Frontiers of Computer Science in China, 2007, 1( 3): 247–271

7 Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000

8 Yan F, Jiao S, Iliyasu A M, Jiang Z . Chromatic framework for quantum movies and applications in creating montages. Frontiers of Computer Science, 2018, 12( 4): 736–748

9 Li H S, Zhu Q, Zhou R G, Li M C, Song L, Ian H . Multidimensional color image storage, retrieval, and compression based on quantum amplitudes and phases. Information Sciences, 2014, 273: 212–232

10 Yan F, Iliyasu A M, Guo Y, Yang H . Flexible representation and manipulation of audio signals on quantum computers. Theoretical Computer Science, 2018, 752: 71–85

11 Li H S, Fan P, Xia H, Peng H, Long G L . Efficient quantum arithmetic operation circuits for quantum image processing. Science China Physics, Mechanics & Astronomy, 2020, 63( 8): 280311

12 Li H S, Fan P, Xia H Y, Peng H, Song S . Quantum implementation circuits of quantum signal representation and type conversion. IEEE Transactions on Circuits and Systems I: Regular Papers, 2019, 66( 1): 341–354

13 Wei S, Chen Y, Zhou Z, Long G . A quantum convolutional neural network on NISQ devices. AAPPS Bulletin, 2022, 32( 1): 2

14 Mallat S G . A theory for multiresolution signal decomposition: the wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11( 7): 674–693

15 Makbol N M, Khoo B E, Rassem T H, Loukhaoukha K . A new reliable optimized image watermarking scheme based on the integer wavelet transform and singular value decomposition for copyright protection. Information Sciences, 2017, 417: 381–400

16 Song X H, Wang S, Liu S, El-Latif A A A, Niu X M . A dynamic watermarking scheme for quantum images using quantum wavelet transform. Quantum Information Processing, 2013, 12( 12): 3689–3706

17 Li H S, Fan P, Peng H, Song S, Long G L . Multilevel 2-D quantum wavelet transforms. IEEE Transactions on Cybernetics, 2022, 52( 8): 8467–8480

18 Hoyer P. Efficient quantum transforms. 1997, arXiv preprint arXiv: quant-ph/9702028

19 Klappenecker A. Wavelets and wavelet packets on quantum computers. In: Proceedings of SPIE 3813, Wavelet Applications in Signal and Image Processing VII. 1999, 703−713

20 Fijany A, Williams C P. Quantum wavelet transforms: fast algorithms and complete circuits. In: Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications. 1998, 10−33

21 Terraneo M, Shepelyansky D L . Imperfection effects for multiple applications of the quantum wavelet transform. Physical Review Letters, 2003, 90( 25): 257902

22 Fino B J, Algazi V R . A unified treatment of discrete fast unitary transforms. SIAM Journal on Computing, 1977, 6( 4): 700–717

23 Li H S, Fan P, Xia H Y, Song S . Quantum multi-level wavelet transforms. Information Sciences, 2019, 504: 113–135

24 Li H S, Fan P, Xia H Y, Song S, He X . The multi-level and multi-dimensional quantum wavelet packet transforms. Scientific Reports, 2018, 8( 1): 13884

25 Beylkin G, Coifman R, Rokhlin V. Fast wavelet transforms and numerical algorithms. In: Heil C, Walnut D F, eds. Fundamental Papers in Wavelet Theory. Princeton: Princeton University Press, 2006, 741−783

26 Boopathiraja S, Kalavathi P . A near lossless three-dimensional medical image compression technique using 3D-discrete wavelet transform. International Journal of Biomedical Engineering and Technology, 2021, 35( 3): 191–206

27 Zhang Y, Wang S, Phillips P, Dong Z, Ji G, Yang J . Detection of Alzheimer’s disease and mild cognitive impairment based on structural volumetric MR images using 3D-DWT and WTA-KSVM trained by PSOTVAC. Biomedical Signal Processing and Control, 2015, 21: 58–73

28 Anand R, Veni S, Aravinth J . Robust classification technique for hyperspectral images based on 3D-discrete wavelet transform. Remote Sensing, 2021, 13( 7): 1255

29 Chen Z, Ning R . Breast volume denoising and noise characterization by 3D wavelet transform. Computerized Medical Imaging and Graphics, 2004, 28( 5): 235–246

30 Long G L, Sun Y . Efficient scheme for initializing a quantum register with an arbitrary superposed state. Physical Review A, 2001, 64( 1): 014303

31 Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A, Weinfurter H . Elementary gates for quantum computation. Physical Review A, 1995, 52( 5): 3457–3467

32 Liu Y, Long G L, Sun Y . Analytic one-bit and CNOT gate constructions of general n-qubit controlled gates. International Journal of Quantum Information, 2008, 6( 3): 447–462

33 Muñoz-Coreas E, Thapliyal H . Quantum circuit design of a T-count optimized integer multiplier. IEEE Transactions on Computers, 2019, 68( 5): 729–739

34 Li H S, Fan P, Xia H, Long G L . The circuit design and optimization of quantum multiplier and divider. Science China Physics, Mechanics & Astronomy, 2022, 65( 6): 260311

35 Moyano E, Quiles F J, Garrido A, Orozco-Barbosa T, Duato J. Efficient 3D wavelet transform decomposition for video compression. In: Proceedings of the 2nd International Workshop on Digital and Computational Video. 2001, 118−125

36 Wu C, Qi B, Chen C, Dong D . Robust learning control design for quantum unitary transformations. IEEE Transactions on Cybernetics, 2017, 47( 12): 4405–4417

37 Daubechies I . Orthonormal bases of compactly supported wavelets. Communications on Pure and Applied Mathematics, 1988, 41( 7): 909–996

38 More S A, Deore P J . Gait recognition by cross wavelet transform and graph model. IEEE/CAA Journal of Automatica Sinica, 2018, 5( 3): 718–726