-
在大数据时代, 高效的数据处理至关重要, 量子计算具有平行计算能力, 为方便处理数据提供了新的解决途径. 本文提出了一个基于奇异值分解的矩阵低秩近似量子算法, 复杂度为
$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.-
Keywords:
- low rank approximation /
- singular value decomposition /
- quantum computing /
- resonant transition
[1] Seghouane A K, Shokouhi N, Koch I 2019 IEEE Trans. Image Process. 28 3274
Google 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 3503
Google Scholar
[3] Viviani R, Gr N G, Spitzer M 2005 Hum. Brain Mapp. 24 109
Google Scholar
[4] Chan T H, Jia K, Gao S, Lu J, Zeng Z, Ma Y 2015 IEEE Trans. Image Process. 24 5017
Google Scholar
[5] Zhang L, Lukac R, Wu X L 2009 IEEE Trans. Image Process. 18 16
Google Scholar
[6] Huang Yan, Liao G, Xiang Y, Zhang L, Li J 2019 IEEE Trans. Image Process. 29 2244
Google Scholar
[7] Donoho D L 2006 IEEE Trans. Inform. Theory. 52 1289
Google Scholar
[8] Yang J, Zhang D, Frangi A F, Yang J Y 2004 IEEE Trans. Pattern Anal. 26 131
Google Scholar
[9] Lin J, Bao W S, Zhang S, Wang X 2019 Phys. Lett. A 383 2862
Google 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 788
Google Scholar
[14] Harrow A, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502
Google Scholar
[15] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503
Google Scholar
[16] Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 108
Google Scholar
[17] Rebentrost P, Steffens A, Marvian I, Lloyd S 2018 Phys. Rev. A 97 012327
Google 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 160501
Google Scholar
[20] Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. A 78 052310
Google Scholar
[21] Li H S, Fan P, Xia H, Peng H, Long G L 2020 Sci. China Phys. Mech. Astron. 63 280311
Google Scholar
[22] Kitaev A Yu 1995 arXiv: 9511026 v1 [quant-ph]
[23] Benioff P 1980 J. Statist. Phys. 22 563
Google Scholar
[24] Long G L 2006 Commun. Theor. Phys 45 825
Google Scholar
[25] Long G L, Liu Y 2008 Commun. Theor. Phys. 50 1303
Google Scholar
[26] Long G L 2011 Int. J. Theor. Phys. 50 1305
Google Scholar
[27] Schuld M, Sinayskiy I, Petruccione F 2016 Phys. Rev. A 94 022342
Google Scholar
[28] Khaneja N, Reiss T, Kehlet C 2005 J. Magn. Reson. 172 296
Google Scholar
[29] Ryan C A, Negrevergne C, Laforest M, Knill E, Laflamme R 2008 Phys. Rev. A 78 012328
Google Scholar
[30] Wang H 2016 Phys. Rev. A 93 052334
Google Scholar
[31] Li Z, Liu X, Wang H, Ashhab S, Cui J, Chen H, Peng X, Du J 2019 Phys. Rev. Lett. 122 090504
Google Scholar
[32] Cory D G, Price M D, Havel T F 1998 Physica D 120 82
Google Scholar
[33] Hou S Y, Sheng Y B, Feng G R 2014 Sci. Rep. 4 6857
Google Scholar
[34] Li H, Gao X, Xin T 2017 Sci. Bull. 62 497
Google Scholar
[35] Xin T, Hao L, Hou S Y, Feng G R, Long G L 2019 Sci. China Phys. Mech. Astron. 62 960312
Google 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 230321
Google Scholar
[37] Lee J S 2002 Phys. Lett. A 305 349
Google Scholar
[38] Feng G, Xu G Long G 2013 Phys. Rev. Lett. 110 190501
Google Scholar
[39] Leskowitz G M, Mueller L J 2004 Phys. Rev. A 69 052302
Google Scholar
[40] Feng G, Long G L, Laflamme R 2013 Phys. Rev. A 88 022305
Google Scholar
[41] Li J, Huang S, Luo Z, Li K, Lu D, Zeng B 2017 Phys. Rev. A 96 032307
Google 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 3274
Google 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 3503
Google Scholar
[3] Viviani R, Gr N G, Spitzer M 2005 Hum. Brain Mapp. 24 109
Google Scholar
[4] Chan T H, Jia K, Gao S, Lu J, Zeng Z, Ma Y 2015 IEEE Trans. Image Process. 24 5017
Google Scholar
[5] Zhang L, Lukac R, Wu X L 2009 IEEE Trans. Image Process. 18 16
Google Scholar
[6] Huang Yan, Liao G, Xiang Y, Zhang L, Li J 2019 IEEE Trans. Image Process. 29 2244
Google Scholar
[7] Donoho D L 2006 IEEE Trans. Inform. Theory. 52 1289
Google Scholar
[8] Yang J, Zhang D, Frangi A F, Yang J Y 2004 IEEE Trans. Pattern Anal. 26 131
Google Scholar
[9] Lin J, Bao W S, Zhang S, Wang X 2019 Phys. Lett. A 383 2862
Google 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 788
Google Scholar
[14] Harrow A, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502
Google Scholar
[15] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503
Google Scholar
[16] Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 108
Google Scholar
[17] Rebentrost P, Steffens A, Marvian I, Lloyd S 2018 Phys. Rev. A 97 012327
Google 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 160501
Google Scholar
[20] Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. A 78 052310
Google Scholar
[21] Li H S, Fan P, Xia H, Peng H, Long G L 2020 Sci. China Phys. Mech. Astron. 63 280311
Google Scholar
[22] Kitaev A Yu 1995 arXiv: 9511026 v1 [quant-ph]
[23] Benioff P 1980 J. Statist. Phys. 22 563
Google Scholar
[24] Long G L 2006 Commun. Theor. Phys 45 825
Google Scholar
[25] Long G L, Liu Y 2008 Commun. Theor. Phys. 50 1303
Google Scholar
[26] Long G L 2011 Int. J. Theor. Phys. 50 1305
Google Scholar
[27] Schuld M, Sinayskiy I, Petruccione F 2016 Phys. Rev. A 94 022342
Google Scholar
[28] Khaneja N, Reiss T, Kehlet C 2005 J. Magn. Reson. 172 296
Google Scholar
[29] Ryan C A, Negrevergne C, Laforest M, Knill E, Laflamme R 2008 Phys. Rev. A 78 012328
Google Scholar
[30] Wang H 2016 Phys. Rev. A 93 052334
Google Scholar
[31] Li Z, Liu X, Wang H, Ashhab S, Cui J, Chen H, Peng X, Du J 2019 Phys. Rev. Lett. 122 090504
Google Scholar
[32] Cory D G, Price M D, Havel T F 1998 Physica D 120 82
Google Scholar
[33] Hou S Y, Sheng Y B, Feng G R 2014 Sci. Rep. 4 6857
Google Scholar
[34] Li H, Gao X, Xin T 2017 Sci. Bull. 62 497
Google Scholar
[35] Xin T, Hao L, Hou S Y, Feng G R, Long G L 2019 Sci. China Phys. Mech. Astron. 62 960312
Google 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 230321
Google Scholar
[37] Lee J S 2002 Phys. Lett. A 305 349
Google Scholar
[38] Feng G, Xu G Long G 2013 Phys. Rev. Lett. 110 190501
Google Scholar
[39] Leskowitz G M, Mueller L J 2004 Phys. Rev. A 69 052302
Google Scholar
[40] Feng G, Long G L, Laflamme R 2013 Phys. Rev. A 88 022305
Google Scholar
[41] Li J, Huang S, Luo Z, Li K, Lu D, Zeng B 2017 Phys. Rev. A 96 032307
Google Scholar
下载:
计量
- 文章访问数: 5317
- PDF下载量: 137
- 被引次数: 0
