线性卷积是科学工程上的重要工具, 在图像处理中发挥了重要作用, 例如基于均值滤波器和高斯滤波器实现图像平滑^[1], 基于拉普拉斯算子实现图像锐化^[1], 基于索伯梯度算子实现图像边缘检测, 使用基于对称式扩充卷积的残差网络进行图像去噪^[2]. 对于$ M\times M $图像和$ N\times N $滤波器, 其卷积操作的时间复杂度是${\rm{O}}({M}^{2}{N}^{2})$. 虽然经典计算能求出线性卷积结果, 但是在处理海量高分辨率图像时, 求解线性卷积会消耗大量计算资源. 量子计算为解决该问题提供了一种新的解决方案.

量子力学的量子叠加和量子纠缠特性使得量子计算在处理某些特定问题上具有显著的速度优势, 例如大数因子分解算法(Shor算法)^[3], 数据库搜索算法(Grover算法)^[4], 线性方程求解算法(HHL算法)^[5], 粗糙集核属性求解算法^[6], 映射量子模型^[7], 孪生支持向量机^[8]和量子主成分分析^[9-10]. 目前关于量子线性卷积的研究集中在量子一维卷积(Quantum one-dimensional convolution, QOC)和量子二维卷积(Quantum two-dimensional convolution, QTC). Lomont^[11]证明, 如果使用振幅编码将两个一维序列制备成两个量子态, 那么在允许使用线性算子(酉算子和测量算子)和辅助量子比特的情况下, 基于量子力学不能计算它们的量子循环卷积$ \left|c\right\rangle\otimes \left|g\right\rangle $, 其中$ \left| c \right\rangle $表示卷积结果, $ \left| g \right\rangle $表示垃圾项. 闫茜茜等^[12]提出量子一维窄卷积, 首先使用振幅编码信息, 利用量子态张量积性质获取振幅的乘积, 接着使用置换矩阵实现振幅的置换, 然后使用哈达玛门(Hadamard, H)量子门进行加法计算, 最终获得量子态$ \left|c\right\rangle\otimes \left|0\right\rangle + \left|g\right\rangle\otimes {\left|0\right\rangle}^{\perp } $, $ \left| c \right\rangle $是卷积结果.随后闫茜茜等^[13]又提出量子二维窄卷积, 其实现过程同量子一维窄卷积相似. 另外, 量子图像滤波^[14-17]和量子图像边缘检测^[18-29]等算法使用量子算术计算线性卷积. 虽然上面三种方案都可以实现量子线性卷积, 但各有不足. 闫茜茜等提出的量子一维和二维线性卷积方法不适用于求解量子线性宽卷积和量子线性等宽卷积, 量子图像滤波和量子图像边缘检测中的量子二维线性卷积算法需要消耗大量的量子比特资源.

本文研究内容包括量子线性卷积的实现和应用两方面. 首先提出单通道, 单位步长, 零补充情况的量子一维宽卷积(Quantum one-dimensional wide convolution, QOWC), 量子一维等宽卷积(Quantum one-dimensional equal-width convolution, QOEC), 量子一维窄卷积(Quantum one-dimensional narrow convolution, QONC), 量子二维宽卷积(Quantum two-dimensional wide convolution, QTWC), 量子二维等宽卷积(Quantum two-dimensional equal-width convolution, QTEC), 量子二维窄卷积(Quantum two-dimensional narrow convolution, QTNC). 然后实现多通道, 非单位步长, 非零补充情况的QOWC, 同样适用于QOEC, QONC, QTWC, QTEC, QTNC. 最后基于量子二维线性卷积实现量子图像平滑(Quantum image smoothing, QISM), 量子图像锐化(Quantum image sharpening, QISH)和量子图像边缘检测(Quantum image edge detection, QIED)算法, 并在Qiskit上进行仿真实验. 理论分析证明了在时间和资源消耗方面量子线性卷积相比于经典线性卷积呈指数下降.

本文后续部分组织结构如下. 第1节介绍线性卷积和量子计算的相关知识. 第2节实现QOWC, QOEC, QONC, QTWC, QTEC, QTNC. 第3节实现QTC在QISM, QISH和QIED上的应用. 第4节总结和展望. 附录A给出置换电路的优化方法. 附录B给出量子态制备方法.

1.   预备知识及符号说明

1.1   线性卷积

为避免因读者研究背景不同导致的对相关术语理解存在部分歧义的问题, 本文将在此节中对相关学术名词及符号做合理规范, 读者的阅读请务必参考此规范开展. 根据维度$ d $, 补充$ p $, 步长$ s $, 通道数$ c $参数的不同, 线性卷积存在多种变体. 本节重点介绍单通道, 零补充, 单位步长的一维, 二维线性卷积. 在单通道, 单位步长, 零补充情况下, 线性卷积根据补零的数量又可以划分成宽线性卷积(宽卷积), 等宽线性卷积(等宽卷积)和窄线性卷积(窄卷积).

1.1.1   一维线性卷积

令输入序列$\boldsymbol{X}=\left[{x}_{0}, {x}_{1}, \cdots, {x}_{M-1}\right]$, 卷积核$\boldsymbol{Y}= [{y}_{0}, {y}_{1}, \cdots, {y}_{N-1}]$, $ M > N $. 当$ M < N $, 则将$ \boldsymbol{Y} $作为输入序列, $ \boldsymbol{X} $作为卷积核.

一维宽卷积结果是${\boldsymbol{Z}}_{\rm{w}}=\left[{z}_{0}, {z}_{1}, \cdots, {z}_{M + N-2}\right]$, 满足$ z\left(i\right)=\sum _{j=0}^{M-1}{x}_{j}{y}_{i-j} ,$ $ i=0, 1, \cdots ,M + N-2 .$ 展开成矩阵形式可以写成${\boldsymbol{U}}_{\rm{w}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{w}}^{\rm{T}}$ ,

其中${\boldsymbol{U}}_{\rm{w}}\in {\mathbf{R}}^{(M + N-1)\times M}$.

一维等宽卷积结果是${\boldsymbol{Z}}_{\rm{e}}=[{z}_{0},{z}_{1},\cdots, {z}_{M-1}]$, 满足$ z\left(i\right)=\sum _{j=0}^{M-1}{x}_{j}{y}_{-j + i + (N-1)/2} $, $i=0, 1, \cdots , M-1$. 展开成矩阵形式可以写成${\boldsymbol{U}}_{\rm{e}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{e}}^{\rm{T}}$.

一维窄卷积结果是${\boldsymbol{Z}}_{\rm{n}}=[{z}_{0},{z}_{1},\cdots ,{z}_{M-N}]$,满足$z\left(i\right)=\sum _{j=0}^{M-1}{x}_{j}{y}_{-j + i + N-1},$ $ i=0, 1, \cdots ,M-N .$ 展开成矩阵形式可以写成${\boldsymbol{U}}_{\rm{n}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{n}}^{\rm{T}}.$

1.1.2   二维线性卷积

二维卷积是一维卷积的扩展, 可以看成是在行和列上分别做一维卷积. 在不影响上下文理解的情况下, 我们使用与一维卷积相同的变量表示物理含义. 令输入序列 $ \boldsymbol{X}={\left[{x}_{{i}_{1},{i}_{2}}\right]}_{M\times M} $, 卷积核 $\boldsymbol{Y}= {\left[{y}_{{j}_{1},{j}_{2}}\right]}_{N\times N}$, $ M > N $. 当$ M < N $时, 将$ \boldsymbol{Y} $作为输入序列, $ \boldsymbol{X} $作为卷积核即可.

二维宽卷积结果${\boldsymbol{Z}}_{\rm{w}}={\left[{z}_{{k}_{1},{k}_{2}}\right]}_{\left(M + N-1\right)\times (M + N-1)}$满足$ {z}_{{k}_{1},{k}_{2}}=\sum _{{i}_{1}=0}^{M-1}\sum _{{i}_{2}=0}^{M-1}{x}_{{i}_{1},{i}_{2}}{y}_{{k}_{1}-{i}_{1},{k}_{2}-{i}_{2}} $, 展开成矩阵形式是${\boldsymbol{U}}_{\rm{w}}{\boldsymbol{X}}={{\boldsymbol{Z}}_{\rm{w}}}$, ${\boldsymbol{X}}$和${{\boldsymbol{Z}}_{\rm{w}}}$分别是$ \boldsymbol{X} $和${\boldsymbol{Z}}_{\rm{w}}$的行向量化(矩阵按行展开成向量形式), 即

二维等宽卷积结果是${\boldsymbol{Z}}_{\rm{e}}={\left[{z}_{{k}_{1},{k}_{2}}\right]}_{M\times M}$满足${z}_{{k}_{1},{k}_{2}}=\sum _{{i}_{1}=0}^{M-1}\sum _{{i}_{2}=0}^{M-1}{x}_{{i}_{1},{i}_{2}}{y}_{{k}_{1}-{i}_{1} + (N-1)/2,{k}_{2}-{i}_{2} + (N-1)/2} ,$ 展开成矩阵形式是${\boldsymbol{U}}_{\rm{e}}{\boldsymbol{X}}={{\boldsymbol{Z}}_{\rm{e}}}$.

二维窄卷积结果是${\boldsymbol{Z}}_{\rm{n}}={[{z}_{{k}_{1},{k}_{2}}]}_{(M-N + 1)\times (M-N + 1)}$满足${z}_{{k}_{1},{k}_{2}}=\sum _{{i}_{1}=0}^{M-1}\sum _{{i}_{2}=0}^{M-1}{x}_{{i}_{1},{i}_{2}}{y}_{{k}_{1}-{i}_{1} + N-1,{k}_{2}-{i}_{2} + N-1},$ 展开成矩阵形式是${\boldsymbol{U}}_{\rm{n}}{\boldsymbol{X}}={{\boldsymbol{Z}}_{\rm{n}}}.$

1.2   量子计算

量子计算模型有很多, 例如量子电路模型, 量子绝热计算, 量子图灵机, 拓扑量子计算等^[30], 这些量子计算模型是等价的. 本文采用量子电路模型, 其模型易理解且接受范围最广. 量子比特用于存储信息, 它除了可以表示$ \left| 0 \right\rangle $, $ \left| 1 \right\rangle $, 还可以是$ \left| 0 \right\rangle $和$ \left| 1 \right\rangle $的叠加态. 常用的基础门有单量子比特门X, Y, Z, H, S, T和双量子比特门受控非门(Controlled-not gate, CNOT). 这些基础门之间存在等价性关系, 例如XZX = −Z. 任意一种酉操作能以任意精度分解成一系列基础门. 利用这些等价关系和分解方法可以简化复杂的量子电路^[31]. 量子测量是不可逆的过程, 它会引发量子态坍缩, 通过量子态层析, 量子过程层析, 量子压缩感知等技术可以重构出量子态和量子操作的相关信息^[31-32]. 本文使用时间复杂度和空间复杂度来衡量量子电路的性能. 下面给出几种后续行文必需的量子操作:

引理 1. (量子随机存取存储器(Quantum random access memory, QRAM)^[33-36]) 量子随机存取存储器可以以相干量子叠加形式执行内存访问. 如果量子计算机需要访问一个叠加的存储单元, 地址寄存器$ a $必须包含一个地址的叠加$ \sum _{j}{\psi }_{j}{\left|j\right\rangle}_{a}\left| 0 \right\rangle $, 量子随机存取存储器将在${\rm{O}}\left(\mathrm{log}(MN)\right)$时间内, 返回数据寄存器$ d $中与地址寄存器相关的数据的叠加$ \sum _{j}{\psi }_{j}{\left|j\right\rangle}_{a}{\left|{D}_{j}\right\rangle}_{d} $.

引理 2. (量子振幅放大(Quantum amplitude amplification, QAA)^[37]) 设$ U $是酉操作, $ a $是期望量子态的振幅. 令$ a > 0 $, $ m=\left\lfloor {\pi /4{\theta }_{a}} \right\rfloor $, 其中$ {\theta }_{a} $满足$ {\mathrm{sin}}^{2}\left({\theta }_{a}\right)=a $, $ 0 < {\theta }_{a}\le \pi /2 $. 如果在量子系统中执行酉操作$ {Q}^{m}U\left| 0 \right\rangle $并测量它, 那么测量结果是期望量子态的概率至少是$ \mathrm{m}\mathrm{a}\mathrm{x}(1-a,a) $.

引理 3. (实数量子模拟数字转换器(Real quantum analog-to-digital conversion, Real QADC)^[38]) 设${{\tilde{r}}_{j}} $是一串$ m $比特数字$ {{\tilde{r}}_{j}}^{\left(1\right)}, \cdots ,{{\tilde{r}}_{j}}^{\left(m\right)} $, 写成$ \sum _{k=1}^{m}{{\tilde{r}}_{j}}^{\left(k\right)}{2}^{-k} $, 它近似于$ {c}_{j} $的实数部分. 一个$ m $比特实数量子模拟数字转换器可以将模拟量子态$\sum _{j=1}^{N}{c}_{j}|j\rangle{|0\rangle}^{\otimes m}$转化成数字量子态$\frac{1}{\sqrt{N}}\sum _{j=1}^{N}| j \rangle| {{{\tilde{r}}}_{j}} \rangle$. 该转换器需要使用${\rm{O}}(1/\varepsilon )$受控$ {U}_{A} $操作和${\rm{O}}(({\mathrm{log}}^{2}N)/\varepsilon )$个单、双量子比特门, 并以$1-{\rm{O}}(poly(\varepsilon ))$的保真度输出结果, 其中$ \varepsilon $表示输出精度.

2.   量子线性卷积算法

本节研究单通道, 单位步长, 零补充情况下的量子一维和二维线性卷积, 包括宽卷积, 等宽卷积和窄卷积. 第2.1节实现了量子一维宽线性卷积, 分析了它的时间复杂度和空间复杂度, 并将其扩展到量子一维等宽卷积, 量子一维窄卷积. 第2.2节实现了量子二维宽线性卷积, 分析了它的时间复杂度和空间复杂度, 并将其扩展到量子二维等宽卷积, 量子二维窄卷积. 我们在第2.3节讨论了多通道, 非单位步长, 非零补充的情况.

2.1   量子一维线性卷积

如式(1)所示, 一维宽卷积计算过程可以写成矩阵形式${\boldsymbol{U}}_{\rm{w}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{w}}^{\rm{T}}$, 其中${\boldsymbol{U}}_{\rm{w}}\in {\mathbf{R}}^{\left(M + N-1\right)\times M}$是一般矩阵. 为了能使量子计算加速求解计算过程, 需要对输入序列和卷积核变换. 在行向量${\boldsymbol{X}}$的前端补$ N-1 $个零, 后端补$N-1 + {L}_{{\rm{t}}}-{{{L}}}_{{\rm{w}}}$个零构造出行向量${\boldsymbol{X}}_{\rm{w}}$:

其中${L}_{{\rm{w}}}=M + 2N-2$, ${L_{\rm{t}}} = {2^{\left\lceil {\log {L_{\rm{w}}}} \right\rceil }}$. 令

把$ {\boldsymbol{R}}_{{\text{0}}} $作为首行向量构造出一个$ {L}_{{\rm{t}}}\times {L}_{{\rm{t}}} $的循环矩阵$ {\widehat{\boldsymbol{U}}}_{\rm{w}} $:

根据循环矩阵的性质, 矩阵$ {\widehat{\boldsymbol{U}}}_{\rm{w}} $可以简写成:

当$ i > N $时, $ {y}_{N-1-i}=0 $, $\boldsymbol{P}\in {\mathbf{R}}^{{L}_{{\rm{t}}}\times {L}_{{\rm{t}}}}$是一个置换矩阵, 矩阵形式是:

$ {\boldsymbol{P}}^{\dagger} $是它的共轭转置矩阵. 那么一维宽卷积计算过程可以改写成${\widehat{\boldsymbol{U}}}_{\rm{w}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{w}}^{\rm{T}}$, 其中

行向量${\boldsymbol{Z}}_{\rm{w}}$的前$ M + N-1 $个元素是所求的宽卷积结果, 后${L}_{{\rm{t}}}-M-N + 1$个元素都是0, 本文中称之为垃圾元素. 将修改后的输入序列${\boldsymbol{X}}_{\rm{w}}$与首行向量$ {\boldsymbol{R}}_{{{0}}} $存储到量子随机存取存储器中.

循环矩阵${\widehat{\boldsymbol{U}}}_{\rm{w}}$可以写成置换矩阵的线性组合(见式(6)), 基于该性质, 我们使用线性酉组合方法(Linear combination of unitaries, LCU)^[39]来求解${\widehat{\boldsymbol{U}}}_{\rm{w}}{\boldsymbol{X}}_{\rm{w}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{w}}^{\rm{T}}$. 图1(a)给出了量子电路实现过程, 需要注意的是, 图中上面的量子比特是低位, 下面的量子比特表示高位. 量子算法具体描述如下: 首先初始化两个量子寄存器 $Q{R}_{1}\;\otimes\; Q{R}_{0}= {\left|0\right.\rangle}^{\otimes \left\lceil\mathrm{log}N\right\rceil}\otimes {\left|0\right\rangle}^{\otimes \mathrm{log}{L}_{{\rm{t}}}}$. 接着, 令 $ {\xi }_{1}=\sum _{i=0}^{N-1}\left|{y}_{N-1-i}\right| $, $\left\| {{\boldsymbol{X}}}_{\rm{w}} \right\|=\sum _{j=0}^{{L}_{{\rm{t}}}-1}{X}_{{\rm{w}},j}^{2}$, 两个酉操作 $ {\cal{O}}_{0} $和$ {\cal{O}}_{1} $分别表示通过量子随机存取存储器将经典数据$ {\boldsymbol{X}}_{\rm{w}} $和$ \boldsymbol{Y} $映射到量子态中:

图 1  量子一维线性卷积实现电路

Fig. 1  Quantum circuit of one-dimensional linear convolution

下载: 全尺寸图片 幻灯片

在$ Q{R}_{1}\otimes Q{R}_{0} $上分别执行酉操作$ {\cal{O}}_{1}\otimes {\cal{O}}_{0} $:

设${{\rm{e}}}^{\iota {\theta }_{i}}={y}_{N-1-i}/\left|{y}_{N-1-i}\right|$表示${\boldsymbol{R}}_{{\text{0}}}$中每个元素的符号位信息, 在$ Q{R}_{1} $上执行受控相位操作($ CP $):

执行受控置换操作$ {\left({P}^{\dagger}\right)}^{i} $, 其量子电路详见附录A:

最后执行逆操作$ {\cal{O}}_{1}^{\dagger} $:

其中子空间$ \left| \perp \right\rangle $正交于子空间$\dfrac{1}{{\xi }_{1}}\left|0\right\rangle\sum _{i=0}^{{L}_{{\rm{t}}}-1}{{\boldsymbol{U}}}_{{\rm{w}}}\left|{{\boldsymbol{X}}}_{{\rm{w}}}\right\rangle$, 满足$\left({\left| 0 \right\rangle \left\langle 0 \right|}\otimes {\boldsymbol{I}}\right)\left|\perp \right\rangle=0$.

使用测量算子 $\left({\left|0\right\rangle}^{\otimes \left\lceil\mathrm{log}N\right\rceil}{\left.\langle0\right|}^{\otimes \left\lceil\mathrm{log}N\right\rceil}\right)\otimes {\boldsymbol{I}}$ 对量子系统进行测量, 当量子寄存器$ Q{R}_{1} $测量结果是$ {\left|0\right\rangle}^{\otimes \left\lceil\mathrm{log}N\right\rceil} $时, 那么量子寄存器$ Q{R}_{0} $存储的量子态是${{\boldsymbol{Z}}}_{{\rm{w}}}/{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|$, 它与期望的卷积结果${{\boldsymbol{Z}}}_{{\rm{w}}}$成正比例关系. 由式(13)可得量子寄存器$ Q{R}_{1} $中测量得到$ {\left|0\right\rangle}^{\left\lceil\mathrm{log}N\right\rceil} $的概率是${\left\| {{\boldsymbol{U}}}_{{\rm{w}}}\left|{{\boldsymbol{X}}}_{{\rm{w}}}\right\rangle \right\|}^{2}/{\xi }_{1}^{2}$, 可以看出概率依赖于卷积核元素和输入序列元素, 与卷积核元素绝对值的和成反比, 与输入序列的范数成正比. 为提高量子寄存器$ Q{R}_{1} $是0的结果, 可使用振幅放大算法(QAA).

基于量子一维宽卷积的实现框架, 有两种不同的方法可以实现量子一维等宽卷积和量子一维窄卷积. 第一种方法是在量子一维宽卷积的量子电路上再增加若干个置换操作, 对于量子一维等宽卷积而言, 额外增加$ \left\lfloor {N} \right\rfloor $个$ {P}^{\dagger} $操作(图1(b)所示), 对于量子一维窄卷积而言, 额外增加$ N-1 $个$ {P}^{\dagger} $操作(图1(c)所示). 第二种方法是仿照量子一维宽卷积算法, 对于量子一维等宽卷积, 重新制备${\boldsymbol{X}}_{\rm{e}}$和${\widehat{\boldsymbol{U}}}_{\rm{e}}$, 对于量子一维窄卷积, 重新制备${\boldsymbol{X}}_{\rm{n}}$和${\widehat{\boldsymbol{U}}}_{\rm{n}}$, 使用它们替代${\boldsymbol{X}}_{\rm{w}}$和${\widehat{\boldsymbol{U}}}_{\rm{w}}$. 方法一是基于量子一维宽卷积, 会保留一些垃圾元素, 而方法二不会保留垃圾元素.

通常输入序列的尺寸$ M $和卷积核的尺寸$ N $满足$ M\gg N $. 量子一维线性卷积算法的空间复杂度是${\rm{O}}\left(\mathrm{log}M\right)$. 由于酉操作$ {\cal{O}}_{0} $和$ {\cal{O}}_{1} $的时间复杂度分别是${\rm{O}}\left(\mathrm{log}M\right)$和${\rm{O}}\left(\mathrm{log}N\right)$, 受控相位$ CP $操作的时间复杂度是${\rm{O}}\left(\mathrm{log}N\right)$, 受控置换操作的时间复杂度是${\rm{O}}\left({\mathrm{log}}^{2}M\right)$, 逆操作$ {\cal{O}}_{1}^{\dagger} $的时间复杂度是${\rm{O}}\left(\mathrm{log}N\right)$, 故量子一维线性卷积算法的时间复杂度是${\rm{O}}\left({\mathrm{log}}^{2}M\right)$.

相对于经典卷积时间复杂度${\rm{O}}\left(M\right)$, 量子一维线性卷积算法实现了指数加速. 文献[12]从卷积定义角度出发, 首先以卷积核长度向输入序列截取对应长度进行内积计算, 之后保持输入序列不变, 卷积核进行一步移位操作, 直到短向量最后一个元素与输入序列最后一个元素对齐并计算其内积, 最终得到量子一维窄卷积结果. 它的时间复杂度是${\rm{ O}}\left({\mathrm{log}}^{2}M\right)$, 但算法无法扩展到量子一维宽卷积和等宽卷积. 而本文从线性代数的角度出发, 首先给出了量子一维宽卷积算法, 并且可以很容易地将其推广到量子一维等宽卷积和量子一维窄卷积上.

2.2   量子二维线性卷积

如式(2)所示, 二维宽卷积可以写成矩阵形式${\boldsymbol{U}}_{\rm{w}}{\boldsymbol{X}}={{\boldsymbol{Z}}}_{\rm{w}}$, 其中${\boldsymbol{U}}_{\rm{w}}$是一般矩阵, 为了使量子计算能够求解该线性方程组, 我们需要重新调整该数据结构形式. 在矩阵${\boldsymbol{X}}$四周进行补0操作得到矩阵$ \widehat{\boldsymbol{X}} $, 然后将其向量化

令

其中前$ {N}^{2} $个元素来自于卷积核${\boldsymbol{Y}}$行向量化, 把$ {\boldsymbol{R}}_{{{0}}} $作为首行向量, 构造循环矩阵

其中, ${\widehat{\boldsymbol{X}}}\in {\mathbf{R}}^{{L}_{{\rm{t}}}^{2}}$, ${\widehat{\boldsymbol{U}}}_{\rm{w}}\in {\mathbf{R}}^{{L}_{{\rm{t}}}^{2}\times {L}_{{\rm{t}}}^{2}}$, ${L}_{{\rm{t}}}={2}^{\left\lceil\mathrm{log}(M + 2N-2)\right\rceil}$. 于是二维宽卷积可以重新写成线性方程 ${\widehat{\boldsymbol{U}}}_{\rm{w}}{\widehat{\boldsymbol{X}}}= {{\widehat{\boldsymbol{Z}}}}_{\rm{w}}$, 其中

将$ {\widehat{\boldsymbol{X}}} $, $ {\boldsymbol{R}}_{{{0}}} $相关信息存储到量子随机存取存储器.

$ {\widehat{\boldsymbol{U}}}_{\rm{w}}{\widehat{\boldsymbol{X}}}={{\widehat{\boldsymbol{Z}}}}_{\rm{w}} $求解过程与量子一维线性卷积中的方法相似, 实现电路也是与图1(a)相似. 不同之处主要在于, 一方面, 图中酉操作$ {\cal{O}}_{0} $和$ {\cal{O}}_{1} $重新定义为

其中$ {{\widehat{X}}}_{i} $表示$ {\widehat{\boldsymbol{X}}} $的第$ i $个元素, $ {R}_{0,j} $表示向量$ {\boldsymbol{R}}_{{{0}}} $中第$ j $个元素. 另一方面, 图中受控相位操作和置换操作根据卷积核和输入序列的结构需要做出对应的调整.

使用测量算子$\left({\left|0\right\rangle}^{\otimes 2\left\lceil\mathrm{log}N\right\rceil}\left\langle 0 \right|^{\otimes 2\left\lceil\mathrm{log}N\right\rceil}\right)\otimes {\boldsymbol{I}}$对量子寄存器进行测量, 当$ Q{R}_{1} $测量结果是$ {\left|0\right\rangle}^{2\left\lceil\mathrm{log}N\right\rceil} $时, $ Q{R}_{0} $存储的量子态与我们想要获取的卷积结果${\boldsymbol{Z}}_{\rm{w}}$成正比. 为提高$ Q{R}_{1} $获取结果是0的概率, 可使用振幅放大算法(QAA).

量子二维宽卷积的实现方法可以直接扩展到量子二维等宽卷积和量子二维窄卷积的量子实现上, 有两种不同的实现方法.第一种方法是重新制备${{\widehat{\boldsymbol{X}}}}_{\rm{e}}$和${\widehat{\boldsymbol{U}}}_{\rm{e}}$(${{\widehat{\boldsymbol X}}}_{\rm n}$和${\widehat{\boldsymbol{U}}}_{\rm{n}}$)以替代${{\widehat{\boldsymbol{X}}}}_{\rm{w}}$和${\widehat{\boldsymbol{U}}}_{\rm{w}}$. 第二种方法是基于量子二维宽卷积的量子电路, 分别在水平方向向左平移$ \left\lfloor {N} \right\rfloor $($ N-1 $)次, 垂直方向向上平移$ \left\lfloor {N} \right\rfloor $($ N- 1 $)次, 这种平移操作可以使用$ {P}^{\dagger} $操作来实现.

通常输入序列的尺寸$ M $和卷积核的尺寸$ N $满足$ M\gg N $. 量子二维线性卷积的空间复杂度是${\rm{O}}\left(2\mathrm{log}M\right)$, 时间复杂度是${\rm{O}}\left(4{\mathrm{log}}^{2}M\right)$. 相对于经典二维线性卷积时间复杂度${\rm{O}}\left({M}^{2}\right)$, 量子二维线性卷积展现了其指数加速的优势. 文献[13]给出了量子二维窄卷积算法, 输入序列的量子态与卷积核的量子态进行张量积计算, 使用两种置换操作共同完成量子卷积振幅置换, 对置换后的卷积核量子态的量子比特执行H门操作, 输入序列量子态的量子比特执行单位矩阵操作, 对卷积核量子态进行测量. 该算法的空间复杂度和时间复杂度与本文相同, 但其思考角度与本文不同, 且其实现不适用于量子二维宽卷积和量子二维等宽卷积.

2.3   量子卷积算法讨论及扩展

上文介绍了单通道, 单位步长, 零填充情况下的量子一维宽卷积, 等宽卷积, 窄卷积, 量子二维宽卷积, 等宽卷积, 窄卷积的量子实现. 下面我们重点讨论量子一维宽卷积算法的实现和扩展, 其他几种量子卷积实现和扩展与它相似.

在没有对输入序列进行填充的情况下, 一维宽线性卷积可以写成线性方程${\boldsymbol{U}}_{\rm{w}}{\boldsymbol{X}}^{\rm{T}}={\boldsymbol{Z}}_{\rm{w}}^{\rm{T}}$形式(见式(1)), 其中${\boldsymbol{U}}_{\rm{w}}\in {\mathbf{R}}^{(M + N-1)\times M}$.有三种量子算法可以求解这样的线性方程. 第一种方法是使用类HHL算法^[5,40], 首先将矩阵${\boldsymbol{U}}_{\rm{w}}$变成厄米矩阵$\widetilde {{{\boldsymbol{U}}_{\rm{w}}}}$:

然后对该厄米矩阵进行有效哈密顿模拟${\mathrm{e}}^{-{\rm{i}}\widetilde {{U_{\rm{w}}}}t}$, 最后使用类HHL算法的量子电路实现. 这种方法要求哈密顿量可以有效模拟, 且需要使用到量子相位估计算法. 第二种方法是使用交换测试(swap test)^[41], 将矩阵$ {\boldsymbol{U}}_{\rm{w}} $的每一行与列向量$ {\boldsymbol{X}}^{\rm{T}} $做内积计算, 由于内积结果隐藏在概率中, 所以需要进行大量的量子测量. 文献[42]中给出了一种使用swap test的量子矩阵乘法算法, 但它同样需要用到量子相位估计算法. 第三种方法是基于线性酉组合方法(LCU). 虽然三种方法都可以实现量子计算求解, 但是前两种方法时间复杂度高且均以高昂的量子比特资源为代价. 因此本文使用第三种方法. 此外, 线性酉组合方法的实现有多种, 但是相对于其他LCU方法, 本文使用的LCU方法^[39]构造简单, 易于实现, 且时间复杂度低, 所需量子比特数少.

本文提出的量子一维宽线性卷积适用于扩展到多通道, 非单位步长, 非零补充的情况. 以三通道为例, 量子电路实现如图2(a)所示, 在量子一维宽卷积的量子电路的基础上, 额外再添加一个两量子比特的量子寄存器$ Q{R}_{2} $, 此时$ Q{R}_{0} $用于存储输入序列信息, $ Q{R}_{1} $用于存储卷积核信息, $ Q{R}_{2} $用于存储通道信息. 实现步骤如下, 首先应用两个H门在$ Q{R}_{2} $, 接着根据通道信息在图像上使用不同的卷积核, 最后再在$ Q{R}_{2} $使用两个H门, 实现卷积结果融合. 以步长为2为例, 量子电路见图2(b)在量子一维宽卷积的量子电路基础上, 再增加一个置换矩阵:

图 2  三通道/两步长的量子一维宽卷积实现电路

Fig. 2  Three-channel/two-stride quantum one-dimensional wide convolution realization circuit

下载: 全尺寸图片 幻灯片

图A1(d)给出了${\boldsymbol{\varGamma }}_{{{1}}}\in {\mathbf{R}}^{8\times 8}$时的量子电路. 以补充值是1为例, 此时式(3)改写成

3.   量子卷积在图像处理中的应用

本节研究量子二维线性卷积在量子图像中的应用, 例如量子图像平滑, 量子图像锐化和量子图像边缘检测, 旨在验证量子卷积算法本身的正确性及基于量子卷积实现量子图像处理算法的可行性. 首先分别给出它们的量子算法, 然后在Qiskit^[43]上使用QasmSimulator进行模拟, 最后将它们和已有的量子图像处理算法比较. 仿真平台的参数是操作系统Ubuntu 20.04.2 LTS 64位, 处理器CPU I9-10900X 10核20进程3.70 GHz, 内存是62.5 GB, Qiskit版本是0.26.2.

3.1   量子图像平滑

图像平滑常见操作有模糊处理和降噪处理, 通常用于图像预处理任务中. 模糊处理可在大目标之前去除图像中的一些琐碎细节, 连接直线或曲线的缝隙. 通过线性滤波和非线性滤波模糊处理, 可以降低噪声. 本节研究量子图像平滑, 其基本流程是首先编码量子图像和卷积核(见附录B), 接着使用量子二维线性卷积实现量子图像平滑.

以图3为例, 图3(a)是含有泊松噪声的实验图像$ {{{I}}}_{{\rm{p}}} $, 图3 (c)是含有高斯噪声(均值为0, 方差为0.01)的实验图像$ {{{I}}}_{{\rm{g}}} $, 它们的尺寸是$ 60\times 60 $. 图3 (b)是均值滤波器, 图3 (d)是高斯滤波器, 它们的尺寸是$ 3\times 3 $. 量子图像平滑算法对应的量子电路图如图4 (a)所示, 最上面的10个量子比特($ Q{R}_{0} $)用于存储量子图像信息, 最下面的4个量子比特($ Q{R}_{1} $)用于存储卷积核信息, 最后一个是经典寄存器($ CR $), 它有四个比特用于存储量子测量后坍缩的经典信息. 需要特别指出, 不同于前面描述的量子卷积的量子电路, 由于本节使用的两个平滑滤波器的元素都是正数, 因此在量子电路设计过程中, 受控相位操作被省略. 我们使用Qiskit的QasmSimulator模拟量子图像平滑算法, 其中参数$ shots $设置为1 024, 实现代码见^{①, ②}. 模拟结果输出状态向量(状态向量的前1024个元素表示平滑滤波后的图像)以及量子寄存器$ Q{R}_{1} $是全0的概率.

图 3  量子图像平滑的实验图像和平滑滤波器

Fig. 3  Experimental image and smoothing filter for quantum image smoothing

下载: 全尺寸图片 幻灯片

图 4  量子图像平滑的仿真电路和仿真结果

Fig. 4  Simulation circuit and simulation results of quantum image smoothing

下载: 全尺寸图片 幻灯片

图4(b)表明了均值滤波时输出0的概率是0.935, 图4(c)显示了量子模拟器输出的均值滤波后的图像, 图4(d)显示了经典计算机使用SciPy^③输出的均值滤波后的图像. 两者在视觉上没有差异且抑制了泊松噪声. 同样地, 图4(e)表明了高斯滤波器时输出0的概率是0.905, 图4(f)显示了量子模拟器输出的高斯滤波后的图像, 图4(g)显示了经典计算机使用SciPy输出的高斯滤波后的图像, 两者在视觉上没有差异且能抑制了高斯噪声. 相比于均方误差(Mean-square error, MSE)和峰值信噪比(Peak signal-to-noise ratio, PSNR), 结构相似性(Structural similarity, SSIM)的评价性能有明显提高^[44],所以本文使用SSIM评估两幅图像的相似性. 均值滤波后的两幅图像的SSIM是0.9998567, 高斯滤波后的两幅图像的SSIM是0.9999233, 这表明两幅图像相同, 同时, 验证了量子图像平滑算法和量子卷积算法的可行性和正确性.

3.2   量子图像锐化

图像锐化可以补偿图像的轮廓, 增强图像的边缘及灰度跳变的部分, 使图像变得清晰. 本节研究量子图像锐化, 其基本步骤是首先对图像和卷积核编码, 接着使用量子二维卷积算法对图像滤波, 需要注意的是, 与平滑滤波算子全是正数元素不同, 锐化滤波算子存在负数元素, 需要使用受控相位操作给负数元素项增加相对相位, 可以得到量子态:

其中${{\boldsymbol{Z}}}_{{\rm{w}}}=\sum _{\left(i,j\right)}{z}_{{\rm{w}},i,j} \left| ij \right\rangle$是卷积滤波后的结果. 然后使用Real QADC方法将卷积结果从振幅提取到基态中, 可以得到量子态:

最后添加额外辅助量子比特, 使用量子比较器^[45]分别比较$\dfrac{{z}_{{\rm{w}},i,j}}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$与0, $\dfrac{{z}_{{\rm{w}},i,j}}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$与$\dfrac{255}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$, 如果$\dfrac{{z}_{{\rm{w}},i,j}}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$小于0, 则将其置为0; 如果$\dfrac{{z}_{{\rm{w}},i,j}}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$大于$\dfrac{255}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$, 则将其置为$\dfrac{255}{{\xi }_{1}\left\| {{\boldsymbol{X}}}_{{\rm{w}}} \right\|}$.

以图5为例, 图5(a)是实验图像, 尺寸是$ 60\times 60 $, 图5(b)是锐化算子, 尺寸是$ 3\times 3 $. 经典计算机模拟量子计算时, 它的内存资源消耗和运行时间随量子电路深度、电路宽度变化呈指数增长. 受现有量子实验设备以及仿真平台环境的约束, 我们只能使用Qiskit仿真实现步骤1, 至于步骤2、3将在步骤一的基础上按照逻辑进行经典运算, 实现代码见^④. 量子图像锐化算法步骤一对应的量子电路图如图6(a)所示, 未优化分解之前量子电路的电路宽度是20, 电路深度是23. 值得注意的是, 受控相位操作中, 除了量子态(下标是1, 3, 5, 7)的相对相位翻转, 还有其他量子态(下标是2, 4, 6, 8)的相对相位也偏转成负值. 相对相位对量子算法的结果影响很大, 因此需要额外的受控相位门将量子态(下标是2, 4, 6, 8)的相对相位恢复成正相位. 我们使用Qiskit的QasmSimulator模拟量子图像锐化算法, 其中参数$ shots $设置为1024. 模拟结果输出状态向量(状态向量的前1024个元素表示锐化后的图像)以及量子寄存器$ Q{R}_{1} $是全0的概率. 图6(b)表明输出0的概率是0.026, 图6(c)显示了量子模拟器输出的锐化后图像, 图6(d)显示了经典计算机使用SciPy输出的锐化后图像. 两者在视觉上没有差异, 且两幅图像的SSIM是1.0, 这表明两幅图像相同, 同时, 验证了量子图像锐化算法和量子卷积算法的可行性和正确性.

图 5  量子图像锐化的实验图像和锐化滤波器

Fig. 5  Experimental image and sharpening filter for quantum image sharpening

下载: 全尺寸图片 幻灯片

图 6  量子图像锐化的仿真电路和仿真结果

Fig. 6  Simulation circuit and simulation results of quantum image sharpening

下载: 全尺寸图片 幻灯片

3.3   量子图像边缘检测

边缘检测是图像处理和计算机视觉中的基本问题, 边缘检测的目的是标识数字图像中亮度变化明显的点. 图像边缘检测可大幅度地减少数据量, 剔除不相关的信息, 保留图像重要的结构属性. 本节研究量子图像边缘检测, 使用水平和垂直方向的Sobel算子, 最终获得的梯度图像是${{Z_{xy}}}= \sqrt {Z_x^2 + Z_y^2}$ 量子图像边缘检测的实现过程如下:

步骤 1. 准备6个量子寄存器, 最左边表示第1个量子寄存器, 最右边表示第6个量子寄存器, $ {q}_{1} $表示存储卷积核所需量子比特数, $ {q}_{2} $表示存储图像所需量子比特数:

步骤 2. 对第2个量子寄存器执行H门操作:

步骤 3. 当第2个量子寄存器是$ \left| 0 \right\rangle $时, 对第3个和第4个量子寄存器执行量子卷积操作, 卷积核是水平方向Sobel算子(Sobelx), 在第5和6个量子寄存器执行同样的量子卷积操作; 当第2个量子寄存器是$ \left| 1 \right\rangle $时, 对第3个和第4个量子寄存器执行量子卷积操作, 卷积核是垂直方向Sobel算子(Sobely), 在第5和6个量子寄存器上执行同样的量子卷积操作:

步骤 4. 第2个量子寄存器执行H门操作:

步骤 5. 把第6个量子寄存器中量子比特作为控制比特, 第4个量子寄存器中的量子比特作为目标比特, 执行$ {q}_{2} $个受控非门操作:

其中, $ x = {x}_{1} = {x}_{2} ,$ $ y = {y}_{1}={y}_{2} ,$ $ \xi = {\xi }_{x} = {\xi }_{y} ,$ $\rho = x = y = 0, \cdots ,{L}_{{\rm{t}}} - 1,$ 该量子态对应的状态向量的前${L}_{{\rm{t}}}$个元素就是$ {Z}_{xy}^{2} $.

步骤 6. 使用Real QADC方法将振幅添加到基态中:

步骤 7. 使用量子比较器^[45]比较第1个量子寄存器与预设的阈值thre, 如果大于阈值则第1个量子寄存器设置为1, 否则第1个量子寄存器置为0:

以图7为例, 图7(a)是实验图像, 尺寸是$ 12\times 12 $, 图7(b)是水平方向的Sobel算子, 尺寸是$ 3\times 3 $, 图7(c)是垂直方向的Sobel算子, 尺寸是$ 3\times 3 $. 受仿真平台环境约束, 我们只使用Qiskit仿真实现步骤1至5, 步骤6、7将在此基础上按逻辑进行经典运算, 实现代码见^⑤. 图8(a)给出了量子图像边缘检测步骤1到5的量子电路图, 使用QasmSimulator对它进行模拟, 参数$ shots $设置为1024. 模拟结果输出状态向量(状态向量的前256个元素是边缘检测后的图像)以及量子寄存器$ Q{R}_{1} $是0的概率. 图8(b)显示了输出是0的概率, 图8(c)显示量子模拟器输出的图像, 图8(d)显示了经典计算机使用SciPy输出的图像. 两者在视觉上没有差异且两幅图像的SSIM是1.0, 这说明两幅图像相同, 同时, 验证了量子卷积算法的正确性和量子图像边缘检测算法的可行性.

图 7  量子图像边缘检测的实验图像和 Sobel 算子

Fig. 7  Experimental image and Sobel operator of quantum image edge detection

下载: 全尺寸图片 幻灯片

图 8  量子图像边缘检测的仿真电路和仿真结果

Fig. 8  Simulation circuit and simulation results of quantum image edge detection

下载: 全尺寸图片 幻灯片

量子图像边缘检测的效果受许多因素影响, 例如算子, 方向, 阈值等. 本节提出的基于水平垂直两个方向Sobel算子的量子图像检测算法可以很容易扩展到四个方向Sobel算子.

3.4   量子图像处理的讨论

基于量子卷积操作的量子图像处理算法已被广泛研究, 主要涉及量子图像滤波, 量子图像特征提取, 量子图像边缘检测. 这些算法实现量子卷积操作的思路大致如下, 首先获取邻域像素值, 接着根据滤波器的元素, 使用量子算术实现卷积计算. 其中邻域像素值获取方法可以细分为三类. 假设卷积核算子的尺寸为$ 3\times 3 $, 图像尺寸是$ M\times M $, $ M = {2}^{m} $, 图像灰度值范围是$ \left[0,{2}^{q}-1\right] $, $ q = 1 $表示二值图像, $ q = 8 $表示灰度图像, $ q = 24 $表示彩色图像. 第一类方法是制备9份完全相同的量子图像, 将循环操作分别作用于8份量子图像, 坐标信息相同的量子态构成邻域像素. 第二类方法是制备1份量子图像和用于存储像素值的8个量子寄存器, 依次使用循环操作和复制操作来获取相邻像素值. 第三类方法是制备1份量子图像和用于存储量子图像的8个量子寄存器, 依次使用量子比较器和复制操作获取相邻像素值. 如表1所示, 这些算法的空间复杂度和时间复杂度都比较高. 此外, 第二类算法存在错误, 量子图像的位置信息和像素值信息是纠缠的, 移位后再复制的像素值都是相同的, 通过理论推导或Qiskit仿真可以验证. 文献[27]中给出的量子图像检测算法只适用于二值图像,因此这里不做比较.

表 1  已被提出的量子图像滤波和量子图像特征边缘检测算法. 假设卷积核算子的尺寸为3 × 3,图像尺寸是 $M \times M$, $M = {2^m}$, q表示图像的灰度值范围

Table 1  Quantum image filtering and quantum image feature edge detection algorithms have been proposed. Suppose the size of the convolution kernel operator is 3 × 3, and the image size is $M \times M$, $M = {2^m}$, q represents the range of gray values

图像处理	图像编码	卷积核算子	邻域获取	空间复杂度	时间复杂度	论文
图像滤波(平滑,锐化)	NEQR	任意卷积核	第一种	18m + 9q	O(9m2 + 9q2)	[14]
	NEQR	Gaussian核	第一种	20m+10q + 1	O(m222m + q222m)	[15]
	NEQR	任意卷积核	第一种	18m + 9q	O(9m2 + 9q2)	[16]
量子图像边缘检测	NEQR	Sobel	第二种	4m+18q	O(m2 + q2)	[18]
	NEQR	Kirsch	第一种	18m + 9q	O(m2 + 2q+3)	[19]
	NEQR	Zero-cross	第二种	2m + 9q	O(m2 + q2)	[20]
	GQIR	Sobel	第一种	18m + 9q	O(m2 + 2q+5 + q2)	[21]
	NEQR	Prewitt	第一种	18m + 9q	O(m2 + 2q+3)	[22]
	NEQR	Sobel	第二种	2m + 9q	O(m2 + 2q+4)	[23]
	NEQR	Sobel	第二种	2m + 9q	O(10m2 + 4q2)	[24]
	NEQR	Sobel	第一种	18m + 9q	O(qm2 + 9q3)	[25]
	FRQ	Sobel	第二种	2m + 9q	O(10m2 + q2)	[26]
	FRQI	Sobel	第二种	4m + 10	O(10m2 + q2)	[28]
	NEQR	Canny	第三种	18m + 9q	O(48m2 + 4q2)	[29]

下载: 导出CSV 

| 显示表格

量子图像平滑算法需要$ 2m + 4 $个量子比特, 时间复杂度是${\rm{ O}}\left(4{m}^{2}\right)$; 量子图像锐化算法需要$ 2m + 2\mathrm{log}\left(1/\varepsilon \right) + 5 $个量子比特, 时间复杂度是${\rm{O}}\left(4{m}^{2}/\varepsilon + 16\mathrm{log}\left(1/\varepsilon \right)-3\right)$, $ \varepsilon $是计算精度; 量子图像边缘检测需要$ 4m + 2\mathrm{log}\left(1/\varepsilon \right) + 7 $个量子比特, 时间复杂度是${\rm{O}}\left(16{m}^{2}/\varepsilon + 16\mathrm{log}\left(1/\varepsilon \right)-3\right)$. 本文提出的量子图像滤波(平滑和锐化)算法, 量子图像边缘检测算法相比于其对应的经典算法, 在存储能力和计算效率上都实现了指数加速; 对比表1中量子算法, 在时间复杂度方面处于相同数量级, 在消耗的量子比特数方面占有明显优势, 使得它更有希望在目前的量子计算机上实现. 但是基于本文提出的量子二维卷积操作的量子图像处理算法不适用于非线性量子图像滤波情况^[46-50].

4.   总结及未来工作

本文提出了单通道, 单位步长和零补充情况下的QOWC, QOEC, QONC, QTWC, QTEC, QTNC. 当通道, 步长, 补充值等参数发生变化时, 其对应的算法实现只需轻微调整. 理论分析证明量子线性卷积的空间复杂度$ {\rm{O}}\left(\mathrm{log}M\right) $和时间复杂度$ {\rm{O}}\left({\mathrm{log}}^{2}M\right) $较经典线性卷积有指数级下降. 另外, 本文基于量子线性卷积和振幅编码方式提出了QISM, QISH, QIED三种量子图像处理算法. 理论分析证明了提出的量子图像处理算法相比于经典算法, 在存储能力和计算效率上都实现了指数加速, 相比于其他编码方式的量子图像处理算法, 在消耗的量子比特数方面占有明显优势.

研究过程中我们发现两种情况, 一是量子图像锐化的获取概率较低, 为0.026, 二是最高获取概率0.367对应的量子态也能重构出锐化效果的量子图像. 因此, 未来思考如何提高获取概率以及探究最高概率对应量子态能重构出锐化效果量子图像的背后原因. 另外, 量子卷积操作是量子神经网络的重要步骤, 如量子卷积网络和量子生成对抗网络^[51], 这些都是未来值得深入研究的方向.

附录A.   置换矩阵的量子电路及优化

任意置换矩阵的量子电路可使用量子可逆逻辑方法获得^[52-53]. 置换矩阵$ \boldsymbol{P} $的量子电路如图A1(a)所示, $ {\boldsymbol{P}}^{\dagger} $的量子电路如图A1(b)所示, ${\boldsymbol{\varGamma }}_{{{1}}}\in {\mathbf{R}}^{8\times 8}$的量子电路如图A1(d)所示, 置换矩阵$ \boldsymbol{Q8} $ (文献[12, 13]使用它置换振幅)的正确量子电路应该是如图A1(c)所示. 量子电路图中, 低位量子比特在上面, 高位量子比特在下面.由文献[54]可以推导出下面的结论:

图 A1  置换矩阵的量子电路

Fig. A1  Quantum circuit of permutation matrix

下载: 全尺寸图片 幻灯片

推论 1. 假设输入量子态是 $ \left|a\right\rangle=\left|{a}_{n-1}{a}_{n-2}\cdots {a}_{1}{a}_{0}\right\rangle $, 执行$ b={b}_{n-1}{b}_{n-2}\cdots {b}_{0} $次置换操作${{\boldsymbol{P}}}^{\dagger}\in {\mathbf{R}}^{{2}^{n}\times {2}^{n}}$后, 那么输出的量子态$\left|\widehat{a}\right\rangle={\left({{\boldsymbol{P}}}^{\dagger}\right)}^{b}\left|a\right\rangle=\sum _{k=0}^{n-1}\left({a}_{k}-{b}_{k}\right){2}^{k}{\rm{mod}}{2}^{k + 1}$. 当$ b $可以写成指数形式$ b={2}^{m} $, $ m=0, 1, 2, \cdots ,n-1 $时, $\left|\widehat{a}\right\rangle=\left({a}_{h}-1\right){\rm{mod}}{2}^{n-m} + {a}_{l}$, 其中 $ {a}_{h} $ 和 $ {a}_{l} $ 满足 $a= {a}_{h}* {2}^{m} + {a}_{l}$.

证明. 当b不可以写成指数形式时,

其中$ \bigvee $表示或运算, $ \bigwedge $表示与运算. 当b可以写成指数形式时,

□

推论1可用于简化量子电路, 降低电路深度, 例如${\boldsymbol{P}}^{\dagger}\in {\mathbf{R}}^{64\times 64}$时, $ {\left({\boldsymbol{P}}^{\dagger}\right)}^{64} $对应的量子电路可以简化成图A1(e), $ {\left({\boldsymbol{P}}^{\dagger}\right)}^{130} $对应的量子电路可以简化成图A1(f), 它们将用于Qiskit仿真实验中, 可以简化量子电路, 缩短模拟仿真时间.

附录B.   量子态制备和量子图像编码

根据已知的经典信息制备相应的量子态, 是量子算法设计过程中重要的步骤. 一方面, 量子态制备过程有时会统治整个量子算法的时间复杂度, 另一方面, 量子态制备方法决定了后续采取什么样的量子操作. 量子态的一般形式可以写成$\left|\psi \right\rangle=\mathrm{cos}\dfrac{\theta }{2}\left|0\right\rangle + {{\rm{e}}}^{i\varphi }\mathrm{sin}\dfrac{\theta }{2}\left| 1 \right\rangle$, 经典信息可以存储在基态$ \left| 0 \right\rangle $, $ \left| 1 \right\rangle $, 相对相位$\varphi$, 还有振幅$\mathrm{cos}\dfrac{\theta }{2}$、$\mathrm{sin}\dfrac{\theta }{2}$中. 根据存储位置的不同, 量子态制备方法分为三类, 基态编码(Basic code, BC)^[33,55-56], 相位编码(Phase code, PC)^[57]和振幅编码(Amplitude code, AC)^{[26, 57-60]}. 对于相同类型的量子态制备方法, 不同的研究领域里使用的定义存在差异.

在量子图像处理研究领域, 量子图像编码方法有基态编码, 如新型数字图像增强量子表示(A novel enhanced quantum representation of digital images, NEQR)^[55], 广义量子图像表示(The generalized quantum image representation, GQIR)^[61]), 振幅编码, 如灵活表示的量子图像 (A flexible representation of quantum images, FRQI)^[58], 量子概率图像编码(Quantum probability image encoding, QPIE)^[27], $ {\rm{n}} $-qubit 正常任意叠加态(n-qubit normal arbitrary superposition state, NASS)^[57]. 其中NEQR, FRQI, NASS最为常用, 三种方法各有优劣^[62]. 假设图像的尺寸是$ M\times M $, 灰度值的范围是$ \left[{\mathrm{0,2}}^{q}-1\right] $. NEQR时间复杂度 $( {\rm{O}}(2q{M}^{2}\mathrm{log}M + 1) )$低, 酉操作方便, 但空间复杂度 $({\rm{O}}(2\mathrm{log} M + q))$ 高; FRQI的时间复杂度 $( {\rm{O}}(2{M}^{2}\mathrm{log}M))$ 和空间复杂度 $( {\rm{O}}(2\mathrm{log}M + 1) )$都低, 但是酉操作不方便; NASS的空间复杂度 $( {\rm{O}}(2\mathrm{log}M) )$低, 但是它的时间复杂度$({\rm{O}}(2{M}^{2} {\mathrm{log}}^{2}M))$ 高. 为了充分利用三者的优劣, 有时我们会将三种编码变法进行转换, 文献[63]中首先使用QDAC^[38]方法将NEQR转化成FRQI, 然后在FRQI基础上实现频域滤波.

QRAM在量子机器学习中常被使用^[10]. 此处我们考虑使用QRAM方法来降低量子图像编码的时间复杂度. 首先将图像通过QRAM存储制备成量子态$\dfrac{1}{{M}^{2}}\sum _{i}\left|i\right\rangle|{\psi }_{i}\rangle$, $ \left| i \right\rangle $表示位置信息, $|{\psi }_{i}\rangle$表示像素值信息, 时间复杂度是$ {\rm{O}}\left(2\mathrm{log}M\right) $, 然后使用QADC方法^[38]制备量子态$\dfrac{1}{\sqrt{\sum _{i}{\psi }_{i}^{2}}}\sum _{i}{\psi }_{i}\left|i\right\rangle$, 时间复杂度是$ {\rm{O}}\left(2\mathrm{log}M\right) $, 故总的时间复杂度是$ {\rm{O}}\left(4\mathrm{log}M\right) $.