陕西师范大学，陕西 西安

收稿日期：2020年11月27日；录用日期：2020年12月22日；发布日期：2020年12月30日

摘要

本文基于小波变换理论及其在图像水印算法中的应用，给出了利用量子Daubechies D⁽⁴⁾小波变换分解FRQI量子图像的量子线路设计以及基于量子Daubechies D⁽⁴⁾小波变换的分块量子水印算法。该算法首先将经典图像用量子图像形式表示，其次利用Daubechies D⁽⁴⁾小波变换对其进行一级分解，最后将量子水印信息插入到高频段的对角小波系数中。对载体图像影响较小，同时具有较强的嵌入容量以及嵌入质量。

关键词

量子小波变换，数字水印，量子图像

Quantum Image Watermarking Algorithm Based on Daubechies D⁽⁴⁾ Wavelet Transform

Shiyang Sun, Wanshe Li

Department of Advances in Applied Mathematics, Shaanxi Normal University, Xi’an Shaanxi

Received: Nov. 27^th, 2020; accepted: Dec. 22^nd, 2020; published: Dec. 30^th, 2020

ABSTRACT

Based on wavelet transform theory and its applications in image watermarking algorithm, a watermarking algorithm based on the application of Quantum Daubechies D⁽⁴⁾ Wavelet Transform (QDWT) to decompose quantum images represented by FRQI and the design of quantum circuit based on QDWT are proposed. Algorithm firstly shows classic image by using the quantum image representation, then the first decomposition is performed using DWT, and lastly watermarking information is embedded into ten carrier image’s diagonal wavelet coefficients of the high frequency subband. It has little influence on the carrier image, and has strong embedding capacity and embedding quality.

Keywords:Quantum Wavelet Transform, Digital Watermarking, Quantum Image

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

小波变换是傅里叶变换发展史上的里程碑式的进展，其优越性在于在时域和频域均具有良好的局部化性质，除了能够显示信号瞬时频率成分的特点外，还具有多分辨率的性质。目前小波变换在信号检测、图像分析、图像压缩等方面均有着十分重要的应用 [1]。

水印技术是1993年提出的一种信息融合技术，主要应用于数字图像、文本、影音等内容中，目的是为了保护产权或证明产品真实性 [2]。本文着重研究的是量子水印技术，与经典水印技术相比，量子水印仍处于初始阶段。目前，量子图像水印主要分为基于空间域和频域两种。基于空间域的水印算法是直接将水印信息嵌入到载体图像，基于频域的算法是在载体图像的频域上叠加水印信号，频域水印算法主要有量子傅里叶变换(Quantum Fourier transform, QFT)、量子余弦变换(Quantum cosine transform, QCT)和量子小波变换(Quantum wavelet transform, QWT) [3] [4] [5] [6]。

本文基于1999年，Fijany等提出的量子信号处理中的量子Daubechies D⁽⁴⁾小波变换(Quantum Daubechies D⁽⁴⁾ wavelet transform, QDWT)的线路设计 [7]，给出了利用量子Daubechies D⁽⁴⁾小波变换分解FRQI量子图像相关的量子线路设计以及基于QDWT的分块量子水印算法。

2. 预备知识

2.1. FRQI量子图像表示法

2011年，Le等提出了灵活的量子表示方法 [8]，将位置信息和灰度信息利用量子纠缠态表示在一起，即FRQI量子图像表示法。一个的经典图像的量子表示形式为 [9] [10] [11]

$|I\left(\theta \right)\rangle =\frac{1}{2^n}{\displaystyle \underset{i=0}{\overset{2^{2n}-1}{\sum }}|C_i\rangle |i\rangle =}\frac{1}{2^n}{\displaystyle \underset{i=0}{\overset{2^{2n}-1}{\sum }}\left(\cos {\theta }_i|0\rangle +\sin {\theta }_i|1\rangle \right)|i\rangle }$ (1)

${\theta }_i\in \left[0,\frac{\pi }{2}\right],i=0,1,2,\cdots ,2^{2n}-1$

其中 $|C_i\rangle =\cos {\theta }_i|0\rangle +\sin {\theta }_i|1\rangle$ 编码的是 $|i\rangle$ 位置上的灰度信息， $|0\rangle$ 和 $|1\rangle$ 是二维空间的一组基，FRQI用图像中的两个变量 $|Y\rangle$ 和 $|X\rangle$ 来表示像素点的位置信息 $|i\rangle$，$|Y\rangle$ 代表垂直方向， $|X\rangle$ 代表水平方向，其中

$|i\rangle =|y\rangle |x\rangle =|y_{n-1}{y}_{n-2}\cdots y_0\rangle |x_{n-1}{x}_{n-2}\cdots x_0\rangle$ (2)

$x,y\in \left\{0,1,\cdots ,2^n-1\right\}$，$|y_j\rangle ,|x_j\rangle \in \left\{|0\rangle ,|1\rangle \right\},j=0,1,\cdots ,n-1$

2.2. 量子逻辑门

量子计算是通过量子逻辑门实现，对一个或多个量子比特进行的量子操作可以通过酉矩阵表示，这就使得量子逻辑门是可逆的 [12] [13] [14]，本文在水印图像的嵌入过程中会使用到一个非常重要的单量子比特门，矩阵形式如下：

$R_y\left(2\phi \right)=\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)$

作用于一个单量子比特 $|\psi \rangle =\cos \xi |0\rangle +\sin \xi |1\rangle ={\left(\begin{array}{cc}\cos \xi & \sin \xi \end{array}\right)}^{\text{T}}$ 时，结果为 $R_y\left(2\phi \right)$ 将 $\xi$ 变为 $\xi +\phi$。

酉矩阵 $R_y\left(2\phi \right)$ 对于多量子比特的受控操作如图1，其中白色和黑色圆点分别代表量子基础态 $|0\rangle$ 和 $|1\rangle$，当量子序列与控制序列相同时 $R_y\left(2\phi \right)$ 才会作用于最后一个量子比特，也就是说当量子序列为 $a_{n-1}{a}_{n-2}{a}_{n-3}\cdots a_2{a}_1=101\cdots 01$ 时， $|a_0\rangle$ 将会变成 $R_y\left(2\phi \right)|a_0\rangle$，量子序列与控制序列不相同时，则对其进行单位门操作。

图1. 多量子比特控制下 $R_y\left(2\phi \right)$ 的量子线路

3. 量子Daubechies D⁽⁴⁾小波变换的线路图以及FRQI图像的分解

小波变换作为信号处理的一种多尺度结构描述，在图像处理中有着非常重要的作用。本文我们选取Daubechies D⁽⁴⁾小波用于量子水印算法中的量子图像分解 [15] [16]。

量子线路设计的本质是将变换矩阵分解为一系列基本的酉矩阵，在本节中，我们将会给出量子Daubechies D⁽⁴⁾小波变换的完备的量子线路以及FRQI图像的量子多尺度分解。

3.1. 量子Daubechies D⁽⁴⁾小波变换的有效线路

基于正移置换矩阵 ${\Pi }_{2^n}$ 以及比特逆转置换矩阵 $P_{2^n}$ 两个基本置换矩阵 [7] [17]，再考虑 $2^n$ 维的Daubechies D⁽⁴⁾小波核， $D_{2^n}^{\left(4\right)}$ 的传统矩阵表示不适用于量子实现，Hoyer [18] 提出了一种 $D_{2^n}^{\left(4\right)}$ 的分解形式为

$D_{2^n}^{\left(4\right)}=\left(I_{2^{n-1}}\otimes C_1\right)S_{2^n}\left(I_{2^{n-1}}\otimes C_0\right)$ (3)

其中

$C_0=2\left(\begin{array}{cc}{c}_4& -c_2\\ -c_2& c_4\end{array}\right)$，$C_1=\frac{1}{2}\left(\begin{array}{cc}{c}_0/c_4& 1\\ 1& c_1/c_2\end{array}\right)$

$c_0=\frac{1+\sqrt{3}}{4\sqrt{2}}$，$c_1=\frac{3+\sqrt{3}}{4\sqrt{2}}$，$c_2=\frac{3-\sqrt{3}}{4\sqrt{2}}$，$c_3=\frac{1-\sqrt{3}}{4\sqrt{2}}$

其中置换矩阵 $S_{2^n}$ 可以由两个置换矩阵 $Q_{2^n}$ 和 $R_{2^n}$ 的乘积表示：

$S_{2^n}=Q_{2^n}{R}_{2^n}$ (4)

其中 $Q_{2^n}$ 是下平移置换矩阵 [19]， $R_{2^n}$ 可写为

$R_{2^n}=I_{2^{n-1}}\otimes N$ (5)

将(4) (5)式代入(3)式中可以得到 $D_{2^n}^{\left(4\right)}$ 的新分解式如下：

$D_{2^n}^{\left(4\right)}=\left(I_{2^{n-1}}\otimes C_1\right)Q_{2^n}\left(I_{2^{n-1}}\otimes N\right)\left(I_{2^{n-1}}\otimes C_0\right)=\left(I_{2^{n-1}}\otimes C_1\right)Q_{2^n}\left(I_{2^{n-1}}\otimes {C^{\prime }}_0\right)$ (6)

其中

$N=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$，${C^{\prime }}_0=N{C}_0=2\left(\begin{array}{cc}-c_2& c_4\\ c_4& -c_2\end{array}\right)$

接下来为了进一步得到 $D_{2^n}^{\left(4\right)}$ 的分解，我们将利用正移置换矩阵 ${\Pi }_{2^n}$ 对置换矩阵 $Q_{2^n}$ 进行直接的递归分解：

${\Pi }_{2^n}^{\text{T}}{Q}_{2^n}{\Pi }_{2^n}=\left(\begin{array}{cc}0& I_{2^{n-1}}\\ I_{2^{n-1}}& 0\end{array}\right)\left(\begin{array}{cc}{Q}_{2^{n-1}}& 0\\ 0& I_{2^{n-1}}\end{array}\right)=\left(N\otimes I_{2^{n-1}}\right)\left(Q_{2^{n-1}}\oplus I_{2^{n-1}}\right)$ (7)

则根据(7)式， $Q_{2^n}$ 可以表示为

$Q_{2^n}={\Pi }_{2^n}\left(N\otimes I_{2^{n-1}}\right)\left(Q_{2^{n-1}}\oplus I_{2^{n-1}}\right){\Pi }_{2^n}^{\text{T}}$ (8)

将 $Q_{2^{n-1}}$ 的分解代入上式有

$Q_{2^n}={\Pi }_{2^n}\left(N\otimes I_{2^{n-1}}\right)\left({\Pi }_{2^{n-1}}\left(N\otimes I_{2^{n-2}}\right)\left(Q_{2^{n-2}}\oplus I_{2^{n-2}}\right){\Pi }_{2^{n-1}}^{\text{T}}\oplus I_{2^{n-1}}\right){\Pi }_{2^n}^{\text{T}}$ (9)

对于任意的矩阵 $A\in R^{2^{n-1}\times 2^{n-1}}$，存在以下恒等式 [7]

${\Pi }_{2^{n-1}}A{\Pi }_{2^{n-1}}^{\text{T}}\oplus I_{2^{n-1}}=\left(I_2\otimes {\Pi }_{2^{n-1}}\right)\left(A\oplus I_{2^{n-1}}\right)\left(I_2\otimes {\Pi }_{2^{n-1}}^{\text{T}}\right)$ (10)

则(9)式可以表示为

$Q_{2^n}={\Pi }_{2^n}\left(N\otimes I_{2^{n-1}}\right)\left(I_2\otimes {\Pi }_{2^{n-1}}\right)\left(\left(N\otimes I_{2^{n-2}}\right)\times \left(Q_{2^{n-2}}\oplus I_{2^{n-2}}\right)\oplus I_{2^{n-1}}\right)\left(I_2\otimes {\Pi }_{2^{n-1}}^{\text{T}}\right){\Pi }_{2^n}^{\text{T}}$ (11)

再利用恒等式 [7]

$\left(N\otimes I_{2^{n-2}}\right)\left(Q_{2^{n-2}}\oplus I_{2^{n-2}}\right)\oplus I_{2^{n-1}}=\left(N\otimes I_{2^{n-2}}\oplus I_{2^{n-1}}\right)\left(Q_{2^{n-2}}\oplus I_{2^n-2^{n-2}}\right)$ (12)

(11)式可以进一步表示为

$Q_{2^n}={\Pi }_{2^n}\left(N\otimes I_{2^{n-1}}\right)\left(I_2\otimes {\Pi }_{2^{n-1}}\right)\left(N\otimes I_{2^{n-2}}\oplus I_{2^{n-1}}\right)\left(Q_{2^{n-2}}\oplus I_{2^n-2^{n-2}}\right)\left(I_2\otimes {\Pi }_{2^{n-1}}^{\text{T}}\right){\Pi }_{2^n}^{\text{T}}$ (13)

依次对 $Q_{2^i}$，i从n-3到1，进行重复迭代， $Q_2=N$，则 $Q_{2^n}$ 可迭代表示为

$\begin{array}{l}{Q}_{2^n}={\Pi }_{2^n}\left(I_2\otimes {\Pi }_{2^{n-1}}\right)\left(I_4\otimes {\Pi }_{2^{n-2}}\right)\cdots \left(I_{2^{n-2}}\otimes {\Pi }_4\right)\left(N\otimes I_{2^{n-1}}\right)\cdots \\ \times \left(N\otimes I_2\oplus I_{2^n-4}\right)\left(N\oplus I_{2^n-2}\right)\left(I_{2^{n-2}}\otimes {\Pi }_4^{\text{T}}\right)\cdots \left(I_2\otimes {\Pi }_{2^{n-1}}^{\text{T}}\right){\Pi }_{2^n}^{\text{T}}\end{array}$ (14)

根据对 $P_{2^n}$ 的分解，我们有

$Q_{2^n}=P_{2^n}\left(N\otimes I_{2^{n-1}}\right)\left(N\otimes I_{2^{n-2}}\oplus I_{2^{n-1}}\right)\cdots \left(N\otimes I_2\oplus I_{2^n-4}\right)\left(N\oplus I_{2^n-2}\right)P_{2^n}$ (15)

将(15)式带入(6)式并进行整理有

$\begin{array}{c}{D}_{2^n}^{\left(4\right)}=P_{2^n}\left(C_1\otimes I_{2^{n-1}}\right)\left(N\otimes I_{2^{n-1}}\right)\left(N\otimes I_{2^{n-2}}\oplus I_{2^n-2^{n-1}}\right)\cdots \left(N\otimes I_{2^{n-i}}\oplus I_{2^n-2^{n-i+1}}\right)\\ \times \left(N\otimes I_2\oplus I_{2^n-2^2}\right)\left(N\oplus I_{2^n-2}\right)\left({C^{\prime }}_0\otimes I_{2^{n-1}}\right)P_{2^n}\end{array}$ (16)

通过对 $Q_{2^n}$ 进行迭代分解可以得到 $D_{2^n}^{\left(4\right)}$ 的量子线路如图2：

图2. $D_{2^n}^{\left(4\right)}$ 的迭代分解量子线路

3.2. FRQI图像的分解

对于一个二维数字图像的db4小波分解采用标准分解，利用一维db4小波变换将图像的像素点权值转化到每一行，对行操作结束后，再对列进行相同的操作。

FRQI图像表示方法是利用量子基态编码所有的像素点信息，并且将它储存成量子叠加态。因此基于QDWT的量子变换的标准分解在量子线路的应用方面比不标准分解更加简单合适 [20]。

利用图2中的 $D_{2^n}^{\left(4\right)}$ 的n级量子线路对FRQI图像进行分解，主要分为两步：

第一步(行分解)：行分解是将 $D_{2^n}^{\left(4\right)}$ 矩阵组合作用于FRQI图像的水平方向的量子比特 $|X\rangle =|x_{n-1}{x}_{n-2}\cdots x_1{x}_0\rangle$ 上，我们将这一步的矩阵记为 $D_{row}$，则行分解矩阵可表示为

$D_{row}=I_2\otimes I_2^{\otimes n}\otimes D_{2^n}^{\left(4\right)}$ (17)

第二步(列分解)：列分解是将 $D_{2^n}^{\left(4\right)}$ 矩阵组合作用于FRQI图像的垂直方向的量子比特 $|Y\rangle =|y_{n-1}{y}_{n-2}\cdots y_1{y}_0\rangle$ 上，我们将这一步的矩阵记为 $D_{column}$，则列分解矩阵可表示为

$D_{column}=I_2\otimes D_{2^n}^{\left(4\right)}\otimes I_2^{\otimes n}$ (18)

因此，基于量子Daubechies D⁽⁴⁾小波变换的FRQI图像分解对应的矩阵形式为

$D=D_{row}{D}_{column}=\left(I_2\otimes I_2^{\otimes n}\otimes D_{2^n}^{\left(4\right)}\right)\left(I_2\otimes D_{2^n}^{\left(4\right)}\otimes I_2^{\otimes n}\right)$ (19)

4. 量子图像水印算法设计

在本节中，将会给出将 $2^{n-1}\times 2^{n-1}$ 的灰度水印图像插入到 $2^n\times 2^n$ 的灰度携带图像中的分块量子水印方案。还会给出量子水印图像的插入和提取算法以及有效线路。

4.1. 分块1级分解(Block 1^st-Level Decomposition)

基于图2中的 $D_{2^n}^{\left(4\right)}$ 的n + 2级迭代分解量子线路，FRQI图像的分块1级分解量子线路如图3所示

图3. FRQI图像的分块1级分解量子线路

如图3所示，FRQI图像的分块1级分解包括两个部分：行分解以及列分解，因此我们可以推断出分块1级分解的矩阵表达形式如下：

$\left(I_2^{\otimes n}\otimes {C^{\prime }}_0\otimes I_2^{\otimes n}\right)\left(I_2\otimes P_{2^n}\otimes I_2^{\otimes n}\right)\times \left(I_2^{\otimes 2n}\otimes {C^{\prime }}_0\right)\left(I_2^{\otimes n+1}\otimes P_{2^n}\right)$ (20)

对于分块1级分解，图像被分为四个部分，近似部分、水平细节、垂直细节以及对角细节，每一个分块都是 $2^{n-1}\times 2^{n-1}$ 大小。

我们知道近似频段频率较低但是包含原始图像中的大量信息能量，细节频段频率较高，并且能够更好地表示图像的细节信息，同时与近似频段相比它具有更少的能量。特别的，水平和垂直细节比对角细节能表现更多的边缘子图像的小波系数和差异，因此，我们选取对图像重构过程影响更小的对角频段作为水印信息的插入区 [17]。

4.2. 分块量子水印图像的嵌入算法和量子线路设计

根据FRQI图像的分块1级分解，分块量子水印的嵌入步骤如图4所示：

图4. 分块量子水印的嵌入步骤

一个 $2^{n-1}\times 2^{n-1}$ 大小的二进制水印图像WI是以下形式：

$\text{WI}={\displaystyle \underset{Y=0}{\overset{2^{n-1}-1}{\sum }}{\displaystyle \underset{X=0}{\overset{2^{n-1}-1}{\sum }}f\left(Y,X\right)}}$ (21)

$Y=y_{n-2}{y}_{n-3}\cdots y_1{y}_0$，$X=x_{n-2}{x}_{n-3}\cdots x_1{x}_0$

基于每一个点 $\left(Y,X\right)$ 的权值 $f\left(Y,X\right)$，我们可以定义一个酉矩阵 $R_y\left(2{\phi }_K\right)$ 如下

$R_y\left(2{\phi }_K\right)=\left[\begin{array}{cc}\cos \left({\phi }_K\right)& -\sin \left({\phi }_K\right)\\ \sin \left({\phi }_K\right)& \cos \left({\phi }_K\right)\end{array}\right]$，${\phi }_K=0$，$\frac{5\times \pi }{2\times 255}$ (22)

其中 ${\phi }_K=0$，和 ${\phi }_K=\frac{5\times \pi }{2\times 255}$，分别代表二进制水印图像WI中的像素点信息 $f\left(Y,X\right)=0$ 和 $f\left(Y,X\right)=1$，并且 $K=YX=0,1,2,\cdots ,2^{2n-2}-1$ 表示水印图像WI中的像素点位置信息。分块量子水印图像的嵌入算法步骤如下：

第一步：根据图3所示，利用QDWT对量子携带图像进行分块1级分解，可以得到中间态的量子图像表示：

$|C_{B1}\rangle =\left(I_2^{\otimes n}\otimes {C^{\prime }}_0\otimes I_2^{\otimes n}\right)\left(I_2\otimes P_{2^n}\otimes I_2^{\otimes n}\right)\times \left(I_2^{\otimes 2n}\otimes {C^{\prime }}_0\right)\left(I_2^{\otimes n+1}\otimes P_{2^n}\right)|C\rangle$ (23)

中间量子态 $|C_{B1}\rangle$ 可以被分为近似部分、水平细节、垂直细节以及对角细节四个部分。

第二步：是将水印信息嵌入的关键一步，我们可以根据酉矩阵 $R_y\left(2{\phi }_K\right)$ 设计一个多量子比特的控制酉变换 $U_K^C$

$U_K^C=R_y\left(2{\phi }_K\right)\otimes |Y\rangle |X\rangle \langle X|\langle Y|$

$|CB\rangle =U_K^E|C_{B1}\rangle =\left({\displaystyle \underset{K=0}{\overset{2^{2n-2}-1}{\prod }}{U}_K^C}\right)|C_{B1}\rangle$ (24)

其中 $U_K^E$ 是由 $U_K^C$ 构成，目的是作用于中间量子态 $|C_{B1}\rangle$ 中的对角细节信息。 $|Y\rangle =|y_{n-1}{y}_{n-2}\cdots y_1{y}_0\rangle$ 和 $|X\rangle =|x_{n-1}{x}_{n-2}\cdots x_1{x}_0\rangle$ 有最高的量子比特 $|y_{n-1}\rangle =|1\rangle$ 和 $|x_{n-1}\rangle =|1\rangle$，中间量子态的对角细节可以通过最高量子比特 $|y_{n-1}\rangle =|1\rangle$ 和 $|x_{n-1}\rangle =|1\rangle$ 来筛选。因此，通过 $U_K^E$，水印图像的像素信息被嵌入到携带图像的对角小波系数中，一方面，当水印图像的像素点权值为0 bit时，相对应的对角小波系数不改变；另一方面，当水印图像的像素点权值为1 bit时，将会通过多量子受控门 $R_y\left(2{\phi }_K\right)$ 对相关对角小波系数产生细微的改变。

第三步：含水印图像 $|C{W}_B\rangle$ 可以通过对量子态 $|CB\rangle$ 进行逆变换得到，酉矩阵表示如下

$|C{W}_B\rangle ={\left[\left(I_2^{\otimes 2n}\otimes {C^{\prime }}_0\right)\left(I_2^{\otimes n+1}\otimes P_{2^n}\right)\right]}^{\ast }$

${\left[\left(I_2^{\otimes n}\otimes {C^{\prime }}_0\otimes I_2^{\otimes n}\right)\left(I_2\otimes P_{2^n}\otimes I_2^{\otimes n}\right)\right]}^{\ast }|CB\rangle$ (25)

其中 ${\left[\right]}^{\ast }$ 表示的是共轭转置 $A^{\ast }={\left(\bar{A}\right)}^{\text{T}}=\overline{A^{\text{T}}}$。

第四步：利用量子测量实现从量子叠加态图像到传统含水印图像的转换 [21]。量子测量是为了获悉系统的状态，使量子叠加态坍缩，从量子寄存器中获取到传统图像的信息 [22]。

基于上述分析，完整的分块量子水印图像嵌入量子线路第一步到第三步如图5所示。

4.3. 算法复杂度分析

在量子计算中，任何复杂的量子线路都可以被分解为一系列包含1、2量子比特的酉量子门 [13] [14]，在本文中，完整的量子线路的复杂度是由其中包含的基本量子门个数决定的。

图5. 分块量子水印图像嵌入量子线路

量子携带图像和量子水印图像的大小分别为 $2^n\times 2^n$ 、 $2^{n-1}\times 2^{n-1}$，本文的量子水印算法复杂度主要体现在图5的量子线路复杂度上，本节将会对其进行详细分析。

图5的分块量子水印图像嵌入线路可以分为三个部分：1) 利用QDWT对量子携带图像进行分块1级分解；2) 一系列的多量子比特控制循环操作；3) 逆分块1级分解。

因此我们可以分别分析这三个步骤来确定嵌入方案的算法复杂度。

第一部分：分块1级分解的量子线路如图3所示，其中包括两个 ${C^{\prime }}_0$ 和两个置换算子 $P_{2^n}$，$P_{2^n}$ 的矩阵分解如(12)式所示，其中 ${\Pi }_{2^n}$ 包括 $n-1$ 个交换门， ${\Pi }_{2^{n-1}}$ 包括 $n-2$ 个交换门，则 $P_{2^n}$ 一共包括 $\left(n-1\right)+\left(n-2\right)+\cdots +1=\frac{n\left(n-1\right)}{2}$ 个交换算子，综上，第一部分的算法复杂度为 $2+2\times \frac{n\left(n-1\right)}{2}=n^2-n+2$。

第二部分：对2n个量子比特进行 $2^{2n-2}$ 的条件循环门操作，根据文献 [14] 中的7.12定理，n量子比特的控制循环门 $R_y\left(2\phi \right)$ 的量子复杂度为 $O\left(n\right)$，因此这一系列循环门操作的复杂度不会超过 $O\left(n{2}^{2n-2}\right)$。

第三部分：因为所有的量子操作都是通过量子酉门进行的，所以量子变换是可逆的，因此，逆分块1级变换的量子线路相当于对分块1级分解求逆，所以与第一部分的算法复杂度相同，均为 $n^2-n+2$。

将以上三个部分的算法复杂度相加可以得到分块量子水印图像嵌入算法总体的算法复杂度为 $O\left(n{2}^{2n-2}\right)$。

文章引用

孙师阳,李万社. 基于量子Daubechies D⁽⁴⁾小波的图像水印算法
Quantum Image Watermarking Algorithm Based on Daubechies D⁽⁴⁾ Wavelet Transform[J]. 应用数学进展, 2020, 09(12): 2292-2300. https://doi.org/10.12677/AAM.2020.912268

参考文献