本期继续解读文献[1]：量子图像处理及其应用：边缘检测。
量子图像处理及其应用：边缘检测（一）：量子图像处理的研究背景。
量子图像处理及其应用：边缘检测（二）：量子图像处理模型及表示方法。
本期介绍量子图像变换，主要包括以下三个方面：
1. 经典与量子变换； 2. 输出量子态的信息提取； 3. 基础变换及其量子实现。
量子计算机上的图像处理过程相当于对输入量子态|f〉执行一个合适的Hamiltonian变换。
量子变换
在经典计算中，许多图像处理操作均是线性的；这些线性变换在量子计算环境下可以表示为酉变换：
其中，在经典图像中常用的基础图像变换（如：Fourier、Hadamard、Haar wavelet等），这些变换均可以表示成G=PFQ的形式（G是最终得到的图像，P/Q是行/列变换矩阵）：
在量子计算中，实现G=PFQ的酉算子为U=Q^T⊗P。
从上图我们可以观察到在经典计算和量子计算中，变换矩阵是不同的：
- 在经典计算中，输入和输出均是矩阵；
- 在量子计算中，输入和输出部分通过向量化操作将矩阵转换成了向量。
因此对应的变换矩阵需要扩充相应的维度，即在量子计算中，酉算子转换为Q的转置和P的张量积，这两个矩阵分别作用在l=logL比特和m=logM比特。
输出量子态的信息提取
QImP的最后一步是提取有用信息。显然如果希望得到输出图像状态|g>的全部信息，需要O(2^n)的时间复杂度。
在一些情况下，我们不需要得到|g>的全部信息，而只关注|g>的统计信息或者全局信息，比如在模式匹配和识别中，有时只需要一个二元结果。此时所需要读取输出的操作的复杂度就会相当低。
例如，评估|g>和|g’>的相似性，可以通过swap-test操作来计算内积。
基础变换及其量子实现
在数字媒体和信号处理中，有一些基本操作：
实时处理的运行时间随着数据量的增加而剧增，量子图像变换有可能实现经典变换的指数加速。
文献[1]中在QIP的模型下介绍了3个基本的2D图像的变换操作：
- Fourier
- Hadamard
- Haar wavelet transforms
在上述3个变换中，P是Q的转置。
在量子计算中，1维傅立叶变换QFT、Hadamard变换和Haar wavelet变换需要O[poly(m)]的时间复杂度，其中m是qubits的比特数；而对应的经典计算的时间复杂度为O(m2^m)。
当输入数据的准备和输出数据的提取复杂度不高于O[poly(n)]时，QImP（例如2维Fourier, Hadamard和Haar wavelet变换）在原则上能够实现经典算法的指数加速。
下图比较了经典和量子算法所需要的资源（包括寄存器大小及操作步数）：
图片来源：文献[1]的图2
图(a)比较了经典与量子图像处理的时空资源消耗。其中，图像有N=M*L个像素，d比特深度。
图(b)表示空间复杂度的对比：顶/底部曲线分别表示经典/量子算法，其中d=36。
图(c)表示时间复杂度的对比：顶部的2条曲线表示经典算法，底部的4条曲线表示量子算法。
可以看到量子算法的时空效率都有相当大的提升。
本期介绍了基础的经典/量子图像变换操作及其理论上的时空资源，下一期将围绕这些操作的物理实现进行解读，主要包括基于NMR实验平台验证3个基本的图像变换操作，相比经典计算达到指数加速。
参考文献
[1] Yao X W, Wang H, Liao Z, et al. Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment[J]. Physical Review X, 2017, 7(3).
注：
作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆
本文原创，首发在《量子机器学习》微信公众号，欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。
