搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于奇异值分解的矩阵低秩近似量子算法

王芙蓉 杨帆 张亚 李世中 王鹤峰

引用本文:
Citation:

基于奇异值分解的矩阵低秩近似量子算法

王芙蓉, 杨帆, 张亚, 李世中, 王鹤峰

Matrix low-rank approximate quantum algorithm based on singular value decomposition

Wang Fu-Rong, Yang Fan, Zhang Ya, Li Shi-Zhong, Wang He-Feng
PDF
HTML
导出引用
  • 在大数据时代, 高效的数据处理至关重要, 量子计算具有平行计算能力, 为方便处理数据提供了新的解决途径. 本文提出了一个基于奇异值分解的矩阵低秩近似量子算法, 复杂度为$O[\log(pq)]$. 在核磁共振量子计算系统完成了算法的原理演示, 选择一个$8\times8$维的图像矩阵, 实现共振跃迁算法的哈密顿量$\mathcal{H}$的时间演化, 用量子态层析法分别读出密度矩阵的不同成分, 对密度矩阵进行重构, 保真度为99.84%, 在误差范围内验证了本文提出的矩阵低秩近似量子算法的正确性. 而通过奇异值分解计算低秩矩阵的经典算法的复杂度是$O[\mathrm{poly}(p q)]$, 量子算法与经典算法相比, 实现了指数加速.
    In the era of big data, efficient data processing is crucial. Quantum computing has the capability of parallel computing, which provides a new solution for convenient data processing. We propose a matrix low-rank approximate quantum algorithm based on singular value decomposition with a complexity of $O[{\rm{poly}}(p q)]$. We conduct the principle demonstration of the algorithm in the NMR quantum computing system. In the experiment, $^{13}{\rm C}$ labeled cromaric acid is used as a four-bit sample, dissolved in d6-acetone, and $^1 {\rm H }$ is decoupled in the whole process. In the case of a large number of bits, quantum principal component analysis, quantum recommendation algorithm, and other quantum algorithms can achieve the same goal, and their time complexities are basically the same. In this paper, the resonance transition algorithm is used to effectively replace the phase estimation algorithm in this kind of problem, which greatly reduces the need of auxiliary bits. Only one auxiliary bit is used and a singular value is retained to better restore the image, which is currently unable to be achieved by other algorithms based on phase estimation. Firstly, an $8\times8$-dimensional image matrix is selected, and the pseudo-pure state is prepared by using the spatial averaging method. The quantum state reaches the target state by using gradient descent pulse to complete the preparation of the initial state. Then the shape pulse is used to apply the time-evolution operator to the initial state several times to realize the time evolution of the Hamiltonian $ \mathcal{H} $ of the resonance transition algorithm. Finally, the quantum state chromatography is used to read out the different components of the density matrix and reconstruct the density matrix. The experimental results are analyzed by quantum state chromatography, and the experimental values are in agreement with the theoretical ones. The fidelity is 99.84%, and the error comes mainly from the experimental equipment and the gradient pulse’s optimization algorithm. This verifies the correctness of the matrix low-rank approximate quantum algorithm proposed in this paper within the error range. For the classical algorithm, it usually takes $O[{\rm{poly}}(p q)]$ to solve the low-rank matrix on the classical computer. Compared with the classical algorithm, the quantum algorithm achieves exponential acceleration.
      通信作者: 张亚, zy@nuc.edu.cn
    • 基金项目: 山西省研究生教育创新项目(批准号: 2020SY344)、国家重点研发计划(批准号: 2017YFA0303700)、国家自然科学基金(批准号: 11774197)和广东省重点基础研究发展计划(批准号: 2018B030325002)资助的课题
      Corresponding author: Zhang Ya, zy@nuc.edu.cn
    • Funds: Project supported by the Graduate Education Innovation Program of Shanxi Province, China (Grant No. 2020SY344), the National Key R&D Program of China (Grant No. 2017YFA0303700), the National Natural Science Foundation of China (Grant No. 11774197), and the Key Basic Research and Development Program of Guangdong Province, China (Grant No. 2018B030325002)
    [1]

    Seghouane A K, Shokouhi N, Koch I 2019 IEEE Trans. Image Process. 28 3274Google Scholar

    [2]

    Does M D, Olesen J L, Harkins K D, Teresa S D, Gochberg D F, Jespersen S N, Shemesh N 2019 Magn. Reson. Med. 81 3503Google Scholar

    [3]

    Viviani R, Gr N G, Spitzer M 2005 Hum. Brain Mapp. 24 109Google Scholar

    [4]

    Chan T H, Jia K, Gao S, Lu J, Zeng Z, Ma Y 2015 IEEE Trans. Image Process. 24 5017Google Scholar

    [5]

    Zhang L, Lukac R, Wu X L 2009 IEEE Trans. Image Process. 18 16Google Scholar

    [6]

    Huang Yan, Liao G, Xiang Y, Zhang L, Li J 2019 IEEE Trans. Image Process. 29 2244Google Scholar

    [7]

    Donoho D L 2006 IEEE Trans. Inform. Theory. 52 1289Google Scholar

    [8]

    Yang J, Zhang D, Frangi A F, Yang J Y 2004 IEEE Trans. Pattern Anal. 26 131Google Scholar

    [9]

    Lin J, Bao W S, Zhang S, Wang X 2019 Phys. Lett. A 383 2862Google Scholar

    [10]

    Tipping M, Bishop C 2014 Neural Comput. 11 443

    [11]

    徐梦珂 2017 硕士学位论文 (贵阳: 贵州大学)

    Xu M K 2017 M. S. Thesis (Guiyang: Guizhou University) (in Chinese)

    [12]

    Tsuge S, Shishibori M, Kuroiwa S, Kita K 2001 IEEE International Conference on Systems, Man and Cybernetics Tucson, AZ, USA, October 7−10, 2001 p960

    [13]

    Lee D D, Seung H S 1999 Nature 401 788Google Scholar

    [14]

    Harrow A, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502Google Scholar

    [15]

    Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503Google Scholar

    [16]

    Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 108Google Scholar

    [17]

    Rebentrost P, Steffens A, Marvian I, Lloyd S 2018 Phys. Rev. A 97 012327Google Scholar

    [18]

    周志华 2016 机器学习 (北京: 清华大学出版社) 第235页

    Zhou Z H 2016 Machine Learing (Beijing: Tsinghua University Press) p235 (in Chinese)

    [19]

    Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. Lett. 100 160501Google Scholar

    [20]

    Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. A 78 052310Google Scholar

    [21]

    Li H S, Fan P, Xia H, Peng H, Long G L 2020 Sci. China Phys. Mech. Astron. 63 280311Google Scholar

    [22]

    Kitaev A Yu 1995 arXiv: 9511026 v1 [quant-ph]

    [23]

    Benioff P 1980 J. Statist. Phys. 22 563Google Scholar

    [24]

    Long G L 2006 Commun. Theor. Phys 45 825Google Scholar

    [25]

    Long G L, Liu Y 2008 Commun. Theor. Phys. 50 1303Google Scholar

    [26]

    Long G L 2011 Int. J. Theor. Phys. 50 1305Google Scholar

    [27]

    Schuld M, Sinayskiy I, Petruccione F 2016 Phys. Rev. A 94 022342Google Scholar

    [28]

    Khaneja N, Reiss T, Kehlet C 2005 J. Magn. Reson. 172 296Google Scholar

    [29]

    Ryan C A, Negrevergne C, Laforest M, Knill E, Laflamme R 2008 Phys. Rev. A 78 012328Google Scholar

    [30]

    Wang H 2016 Phys. Rev. A 93 052334Google Scholar

    [31]

    Li Z, Liu X, Wang H, Ashhab S, Cui J, Chen H, Peng X, Du J 2019 Phys. Rev. Lett. 122 090504Google Scholar

    [32]

    Cory D G, Price M D, Havel T F 1998 Physica D 120 82Google Scholar

    [33]

    Hou S Y, Sheng Y B, Feng G R 2014 Sci. Rep. 4 6857Google Scholar

    [34]

    Li H, Gao X, Xin T 2017 Sci. Bull. 62 497Google Scholar

    [35]

    Xin T, Hao L, Hou S Y, Feng G R, Long G L 2019 Sci. China Phys. Mech. Astron. 62 960312Google Scholar

    [36]

    Wen J W, Qiu X C, Kong X Y, Chen X Y, Yang F, Long G L 2020 Sci. China Phys. Mech. Astron. 63 230321Google Scholar

    [37]

    Lee J S 2002 Phys. Lett. A 305 349Google Scholar

    [38]

    Feng G, Xu G Long G 2013 Phys. Rev. Lett. 110 190501Google Scholar

    [39]

    Leskowitz G M, Mueller L J 2004 Phys. Rev. A 69 052302Google Scholar

    [40]

    Feng G, Long G L, Laflamme R 2013 Phys. Rev. A 88 022305Google Scholar

    [41]

    Li J, Huang S, Luo Z, Li K, Lu D, Zeng B 2017 Phys. Rev. A 96 032307Google Scholar

  • 图 1  共振跃迁. 一个本征值未知的系统与另一个二能级辅助系统存在相互作用. $H_{\rm s}$是左边系统的哈密顿量, 假设$ E_0 = 0 $. 当辅助系统的激发态能级$ \varepsilon $接近任意特征值$ E_i $时, 两个系统之间会发生共振跃迁

    Fig. 1.  Resonant transition. A system with unknown eigenvalues interacts with another two-level auxiliary system. $H_{\rm s }$ is the Hamiltonian of the system on the left. Assuming $ E_0 = 0 $, when the excited state energy level $ \varepsilon $ of the auxiliary system is close to any eigenvalue $ E_i $, a resonance transition will occur between the two systems

    图 2  共振跃迁量子算法数值模拟 (a)$ 300\times 300 $的原图像; (b), (c), (d)分别是前10, 30, 50个奇异值恢复的图像. 50个奇异值已经可以很好地恢复图像, 可以辨认校徽的细节、文字

    Fig. 2.  Numerical simulation of resonance transition by quantum algorithm. Panel (a) is the original image of $ 300\times 300 $. Panels (b), (c) and (d) are the images recovered by the first 10, 30 and 50 singular values respectively. 50 singular values can be a good restoration of the image, the details and words of the school emblem are legible.

    图 3  数字1的灰度图像, 共$ 8\times 8 $个像素

    Fig. 3.  A grayscale image of the number 1, with a total of $ 8\times 8 $ pixels

    图 4  $ ^{13} {\rm{C}}$标记巴豆酸的分子结构和参数. C1是辅助量子比特, C2—C4是目标量子比特. 在整个实验中, $ ^1 {\rm{H}}$是解耦的. 对角元素和非对角元素是化学位移和J耦合(单位: Hz). 最下面是相干弛豫时间$ T_2 $(单位: s).

    Fig. 4.  Molecular structure and parameters of crotonic acid are labeled $ ^{13}{\rm{C}} $. C1 is the auxiliary qubit and C2−C4 is the target qubit. $ ^1 {\rm{H}}$ is decoupled throughout the experiment. The diagonal and off-diagonal elements are chemical shifts and J coupling (in Hertz). At the bottom is the coherent relaxation time $ T_2 $ (in seconds).

    图 5  简要量子电路图. 制备好赝纯态后, 将经过GRAPE优化好的形状脉冲作用于第2个寄存器, 完成初始化. 之后将时间演化算符${\rm e}^{-{\rm i} \mathcal H t_{0}}$作用于初始态N次, 再测量第1个比特, 结果为$ |1\rangle $时得到目标态$ \left|\psi_{{\boldsymbol{A}}'}\right\rangle $

    Fig. 5.  A brief quantum circuit diagram. After the pseudomorphic state is prepared, the shape pulse optimized by GRAPE is applied to the second register to complete the initialization. Then, the time evolution operator ${\rm e}^{-{\rm i} \mathcal H t_{0}}$ is applied to the initial state for N times, and the first bit is measured. When the result is $ |1\rangle $, the target state $ \left|\psi_{{\boldsymbol{A}}'}\right\rangle $ is obtained.

    图 6  (a)通过实验得到的密度矩阵; (b)理论计算的结果; (c)最大的奇异值恢复的矩阵对应图像; 由于辅助比特是$ | 1\rangle $时才给出有意义的结果, 所以这里只考虑其为$ | 1\rangle $的子空间, 忽略其余部分

    Fig. 6.  (a) Density matrix obtained by experiment; (b) the result of theoretical calculation; (c) the corresponding image of the matrix with the maximum singular value recovery. Since the auxiliary bit is $ | 1\rangle $ and gives a meaningful result, only consider subspaces whose values are $ | 1\rangle $ and the rest are ignored.

  • [1]

    Seghouane A K, Shokouhi N, Koch I 2019 IEEE Trans. Image Process. 28 3274Google Scholar

    [2]

    Does M D, Olesen J L, Harkins K D, Teresa S D, Gochberg D F, Jespersen S N, Shemesh N 2019 Magn. Reson. Med. 81 3503Google Scholar

    [3]

    Viviani R, Gr N G, Spitzer M 2005 Hum. Brain Mapp. 24 109Google Scholar

    [4]

    Chan T H, Jia K, Gao S, Lu J, Zeng Z, Ma Y 2015 IEEE Trans. Image Process. 24 5017Google Scholar

    [5]

    Zhang L, Lukac R, Wu X L 2009 IEEE Trans. Image Process. 18 16Google Scholar

    [6]

    Huang Yan, Liao G, Xiang Y, Zhang L, Li J 2019 IEEE Trans. Image Process. 29 2244Google Scholar

    [7]

    Donoho D L 2006 IEEE Trans. Inform. Theory. 52 1289Google Scholar

    [8]

    Yang J, Zhang D, Frangi A F, Yang J Y 2004 IEEE Trans. Pattern Anal. 26 131Google Scholar

    [9]

    Lin J, Bao W S, Zhang S, Wang X 2019 Phys. Lett. A 383 2862Google Scholar

    [10]

    Tipping M, Bishop C 2014 Neural Comput. 11 443

    [11]

    徐梦珂 2017 硕士学位论文 (贵阳: 贵州大学)

    Xu M K 2017 M. S. Thesis (Guiyang: Guizhou University) (in Chinese)

    [12]

    Tsuge S, Shishibori M, Kuroiwa S, Kita K 2001 IEEE International Conference on Systems, Man and Cybernetics Tucson, AZ, USA, October 7−10, 2001 p960

    [13]

    Lee D D, Seung H S 1999 Nature 401 788Google Scholar

    [14]

    Harrow A, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502Google Scholar

    [15]

    Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503Google Scholar

    [16]

    Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 108Google Scholar

    [17]

    Rebentrost P, Steffens A, Marvian I, Lloyd S 2018 Phys. Rev. A 97 012327Google Scholar

    [18]

    周志华 2016 机器学习 (北京: 清华大学出版社) 第235页

    Zhou Z H 2016 Machine Learing (Beijing: Tsinghua University Press) p235 (in Chinese)

    [19]

    Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. Lett. 100 160501Google Scholar

    [20]

    Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. A 78 052310Google Scholar

    [21]

    Li H S, Fan P, Xia H, Peng H, Long G L 2020 Sci. China Phys. Mech. Astron. 63 280311Google Scholar

    [22]

    Kitaev A Yu 1995 arXiv: 9511026 v1 [quant-ph]

    [23]

    Benioff P 1980 J. Statist. Phys. 22 563Google Scholar

    [24]

    Long G L 2006 Commun. Theor. Phys 45 825Google Scholar

    [25]

    Long G L, Liu Y 2008 Commun. Theor. Phys. 50 1303Google Scholar

    [26]

    Long G L 2011 Int. J. Theor. Phys. 50 1305Google Scholar

    [27]

    Schuld M, Sinayskiy I, Petruccione F 2016 Phys. Rev. A 94 022342Google Scholar

    [28]

    Khaneja N, Reiss T, Kehlet C 2005 J. Magn. Reson. 172 296Google Scholar

    [29]

    Ryan C A, Negrevergne C, Laforest M, Knill E, Laflamme R 2008 Phys. Rev. A 78 012328Google Scholar

    [30]

    Wang H 2016 Phys. Rev. A 93 052334Google Scholar

    [31]

    Li Z, Liu X, Wang H, Ashhab S, Cui J, Chen H, Peng X, Du J 2019 Phys. Rev. Lett. 122 090504Google Scholar

    [32]

    Cory D G, Price M D, Havel T F 1998 Physica D 120 82Google Scholar

    [33]

    Hou S Y, Sheng Y B, Feng G R 2014 Sci. Rep. 4 6857Google Scholar

    [34]

    Li H, Gao X, Xin T 2017 Sci. Bull. 62 497Google Scholar

    [35]

    Xin T, Hao L, Hou S Y, Feng G R, Long G L 2019 Sci. China Phys. Mech. Astron. 62 960312Google Scholar

    [36]

    Wen J W, Qiu X C, Kong X Y, Chen X Y, Yang F, Long G L 2020 Sci. China Phys. Mech. Astron. 63 230321Google Scholar

    [37]

    Lee J S 2002 Phys. Lett. A 305 349Google Scholar

    [38]

    Feng G, Xu G Long G 2013 Phys. Rev. Lett. 110 190501Google Scholar

    [39]

    Leskowitz G M, Mueller L J 2004 Phys. Rev. A 69 052302Google Scholar

    [40]

    Feng G, Long G L, Laflamme R 2013 Phys. Rev. A 88 022305Google Scholar

    [41]

    Li J, Huang S, Luo Z, Li K, Lu D, Zeng B 2017 Phys. Rev. A 96 032307Google Scholar

  • [1] 王美红, 郝树宏, 秦忠忠, 苏晓龙. 连续变量量子计算和量子纠错研究进展. 物理学报, 2022, 71(16): 160305. doi: 10.7498/aps.71.20220635
    [2] 王晨旭, 贺冉, 李睿睿, 陈炎, 房鼎, 崔金明, 黄运锋, 李传锋, 郭光灿. 量子计算与量子模拟中离子阱结构研究进展. 物理学报, 2022, 71(13): 133701. doi: 10.7498/aps.71.20220224
    [3] 周宗权. 量子存储式量子计算机与无噪声光子回波. 物理学报, 2022, 71(7): 070305. doi: 10.7498/aps.71.20212245
    [4] 王宁, 王保传, 郭国平. 硅基半导体量子计算研究进展. 物理学报, 2022, 71(23): 230301. doi: 10.7498/aps.71.20221900
    [5] 张结印, 高飞, 张建军. 硅和锗量子计算材料研究进展. 物理学报, 2021, 70(21): 217802. doi: 10.7498/aps.70.20211492
    [6] 张诗豪, 张向东, 李绿周. 基于测量的量子计算研究进展. 物理学报, 2021, 70(21): 210301. doi: 10.7498/aps.70.20210923
    [7] 何映萍, 洪健松, 刘雄军. 马约拉纳零能模的非阿贝尔统计及其在拓扑量子计算的应用. 物理学报, 2020, 69(11): 110302. doi: 10.7498/aps.69.20200812
    [8] 范桁. 量子计算与量子模拟. 物理学报, 2018, 67(12): 120301. doi: 10.7498/aps.67.20180710
    [9] 孔祥宇, 朱垣晔, 闻经纬, 辛涛, 李可仁, 龙桂鲁. 核磁共振量子信息处理研究的新进展. 物理学报, 2018, 67(22): 220301. doi: 10.7498/aps.67.20180754
    [10] 潘健, 余琦, 彭新华. 多量子比特核磁共振体系的实验操控技术. 物理学报, 2017, 66(15): 150302. doi: 10.7498/aps.66.150302
    [11] 李俊, 崔江煜, 杨晓东, 罗智煌, 潘健, 余琦, 李兆凯, 彭新华, 杜江峰. 核磁共振中的量子控制. 物理学报, 2015, 64(16): 167601. doi: 10.7498/aps.64.167601
    [12] 苏海晶, 王启光, 杨杰, 钱忠华. 基于奇异值分解对中国夏季降水模式误差订正的研究. 物理学报, 2013, 62(10): 109202. doi: 10.7498/aps.62.109202
    [13] 尹柏强, 何怡刚, 吴先明. 心磁信号广义S变换域奇异值分解滤波方法. 物理学报, 2013, 62(14): 148702. doi: 10.7498/aps.62.148702
    [14] 郑安总, 冷永刚, 范胜波. 基于奇异值分解的随机共振特征提取研究. 物理学报, 2012, 61(21): 210503. doi: 10.7498/aps.61.210503
    [15] 姚淅伟, 曾碧榕, 刘钦, 牟晓阳, 林星程, 杨春, 潘健, 陈忠. 基于核磁共振的子空间量子过程重构. 物理学报, 2010, 59(10): 6837-6841. doi: 10.7498/aps.59.6837
    [16] 宋伟, 侯建军, 李赵红, 黄亮. 一种基于Logistic混沌系统和奇异值分解的零水印算法. 物理学报, 2009, 58(7): 4449-4456. doi: 10.7498/aps.58.4449
    [17] 叶 宾, 须文波, 顾斌杰. 量子Harper模型的量子计算鲁棒性与耗散退相干. 物理学报, 2008, 57(2): 689-695. doi: 10.7498/aps.57.689
    [18] 郭成豹, 肖昌汉, 刘大明. 基于积分方程法和奇异值分解的磁性目标磁场延拓技术研究. 物理学报, 2008, 57(7): 4182-4188. doi: 10.7498/aps.57.4182
    [19] 叶 宾, 谷瑞军, 须文波. 周期驱动的Harper模型的量子计算鲁棒性与量子混沌. 物理学报, 2007, 56(7): 3709-3718. doi: 10.7498/aps.56.3709
    [20] 白 云, 刘新元, 何定武, 汝鸿羽, 齐 亮, 季敏标, 赵 巍, 谢飞翔, 聂瑞娟, 马 平, 戴远东, 王福仁. 在SQUID心磁测量中基于奇异值分解和自适应滤波的噪声消除法. 物理学报, 2006, 55(5): 2651-2656. doi: 10.7498/aps.55.2651
计量
  • 文章访问数:  4287
  • PDF下载量:  128
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-03-03
  • 修回日期:  2021-03-29
  • 上网日期:  2021-06-07
  • 刊出日期:  2021-08-05

/

返回文章
返回