本期继续解读文献[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操作来计算内积。

关于swap-test,可以参考往期文章: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在量子客对本文的再次整理、校验与编辑。

量子图像处理及其应用:边缘检测(三)-量子客