1.School of Mechatronics Engineering, North University of China, Taiyuan 030051, China 2.Department of Physics, Tsinghua University, Beijing 100084, China 3.Department of Applied Physics, Xi’an Jiaotong University, Xi’an 710049, China
Fund Project: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)
Received Date:03 March 2021
Accepted Date:29 March 2021
Available Online:07 June 2021
Published Online:05 August 2021
Abstract: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
本文的量子低秩近似算法, 在实验上实现有以下困难. 首先是制备初始态$ \left|\psi_{{\boldsymbol{A}}}\right\rangle $. 在有QRAM的情况下, 可以高效的制备初始态, 但目前为止还没有真正实现QRAM功能的量子器件, 因此要选择其他方式制备. 其次是相位估计算法需要一个额外的寄存器存放本征值的估计值, 需要大量的量子比特, 这也是所有基于相位估计的算法的共同问题, 使得目前在硬件上实现该类算法非常困难; 除此, 实现密度算符$\rho_{\boldsymbol{AA}^{\dagger}}$和演化算符${\rm{ e}}^{-{\rm{i}} \rho_{\boldsymbol{AA}}^\dagger t_{0}}$也需要大量的辅助比特. 在设计算法时, 通常假设拥有足够多的比特资源, 只考虑时间复杂度的优势, 但目前量子计算机仍在研发当中, 很难提供足够多的比特资源. 针对以上问题, 分别提出了对应的解决方案: 1)利用梯度下降优化脉冲(GRAPE)[28,29], 将量子态从赝纯态演化到初始态$ \left|\psi_{{\boldsymbol{A}}}\right\rangle $, 算法直接从初始态$ \left|\psi_{{\boldsymbol{A}}}\right\rangle $开始, 而制备该初始态的方式不会影响到本文算法的正确性. 2)为了减少量子比特数, 选择量子共振跃迁算法来替代相位估计算法以减少辅助比特的数量, 只用一个辅助比特即可实现这一步骤. 相位估计在该问题中的作用是先区分目标奇异向量(需要保留的)和非目标奇异向量(不需要保留的), 以便之后通过测量进行筛选, 量子共振跃迁算法也可以实现对特定的量子态的选择. 这里, 对量子共振跃迁算法简单介绍(图1). 图 1 共振跃迁. 一个本征值未知的系统与另一个二能级辅助系统存在相互作用. $H_{\rm s}$是左边系统的哈密顿量, 假设$ E_0 = 0 $. 当辅助系统的激发态能级$ \varepsilon $接近任意特征值$ E_i $时, 两个系统之间会发生共振跃迁 Figure1. 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
其中, $ \sigma $是泡利算符, c是两个系统的相互作用强度, $ {\boldsymbol{B}} $是相互算作算符, 需要求解的系统哈密顿量为${\boldsymbol H}_{\rm s}$, 在${{{\boldsymbol H}_{T}}}$中引入参考点, ${{{\boldsymbol H}_{T}}} = \varepsilon_{0}|0\rangle \langle 0 |\otimes $$ | \varPhi\rangle \langle\varPhi|+| 1\rangle\langle 1 | \otimes {{{\boldsymbol H}_{\rm s}}}$, 其中$| \varPhi\rangle$是初始态. 3) 演化一段时间后测量第1个辅助比特, 若发生共振, 则测量结果可能为1或0. 当结果为1时得到目标态. 结果为0时重复上一步, 再测量, 直到测量结果为1. 理论上共振跃迁算法可以替代相位估计算法, 利用较少的辅助比特实现目标. 以图2(a)的校徽为例, 利用共振跃迁算法进行数值模拟, 结果如图2(b)—(d)所示. 图 2 共振跃迁量子算法数值模拟 (a)$ 300\times 300 $的原图像; (b), (c), (d)分别是前10, 30, 50个奇异值恢复的图像. 50个奇异值已经可以很好地恢复图像, 可以辨认校徽的细节、文字 Figure2. 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.
考虑到辅助比特只有1个, 令阈值$\tau = ({\sigma_1 + \sigma_2})/{2}$并对$ {\boldsymbol{M}} $厄米化后得到$ {\boldsymbol{A}} $. 图 3 数字1的灰度图像, 共$ 8\times 8 $个像素 Figure3. A grayscale image of the number 1, with a total of $ 8\times 8 $ pixels
本次实验平台是核磁共振量子计算平台, 实验中使用$^{13}{\rm C }$标记的巴豆酸作为4比特样品, 溶解在d6-丙酮中, 整个过程中$^1 {\rm H}$解耦. 该分子的结构和参数如图4所示. C1—C4表示4个量子位, 选择C1作为辅助量子位. 弱耦合近似下的内部哈密顿量为 图 4$ ^{13} {\rm{C}}$标记巴豆酸的分子结构和参数. C1是辅助量子比特, C2—C4是目标量子比特. 在整个实验中, $ ^1 {\rm{H}}$是解耦的. 对角元素和非对角元素是化学位移和J耦合(单位: Hz). 最下面是相干弛豫时间$ T_2 $(单位: s). Figure4. 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).
其中单位矩阵I不产生有效信号, 极化度$ \epsilon \approx 10^{-5} $. 制备赝纯态后, 利用GRAPE将量子态从$ |0000\rangle $演化到需要的态$ |0\rangle \otimes \left|\psi_{{\boldsymbol{A}}}\right\rangle $, 完成初始态的制备. 第2步 实现共振跃迁算法的哈密顿量$ \mathcal{H} $的时间演化. 利用形状脉冲能够实现时间演化算符${\rm e}^{-{\rm i} \mathcal{H}t_0}$, 其中$ \mathcal{H} $由(17)式给出, 考虑到这里的目标态是初始态的一个很好的近似, 令$c = $$ 0.01$, $ B = I^{\otimes 3} $, $H_{\rm s }= {\boldsymbol{A}}$, $ \varepsilon = 1 $并且$ \varepsilon_{0} = \sigma_1-1 $. 将演化算符多次作用在初始态上, 也就是让$|0\rangle \otimes $$ \left|\psi_{{\boldsymbol{A}}}\right\rangle$在$ \mathcal{H} $下演化一段时间. 最后, 利用量子态层析方法对密度矩阵进行读出[37-41], 需要用到多个读出脉冲分别读出密度矩阵的不同成分, 最后对密度矩阵重构. 本实验的简要流程如图5所示. 图 5 简要量子电路图. 制备好赝纯态后, 将经过GRAPE优化好的形状脉冲作用于第2个寄存器, 完成初始化. 之后将时间演化算符${\rm e}^{-{\rm i} \mathcal H t_{0}}$作用于初始态N次, 再测量第1个比特, 结果为$ |1\rangle $时得到目标态$ \left|\psi_{{\boldsymbol{A}}'}\right\rangle $ Figure5. 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.
23.2.实验结果及分析 -->
3.2.实验结果及分析
对实验读出数据进行处理并重构密度矩阵后得到的结果如图6所示, 另一个奇异向量可以通过完全相同的方法获得, 只需要交换厄米化时矩阵$ {\boldsymbol{M}} $与$ {\boldsymbol{M}}^{\dagger} $的顺序. 通过第1个奇异值对应的奇异向量对图像进行重构, 从图6能看出实验结果和理论值符合得很好. 图 6 (a)通过实验得到的密度矩阵; (b)理论计算的结果; (c)最大的奇异值恢复的矩阵对应图像; 由于辅助比特是$ | 1\rangle $时才给出有意义的结果, 所以这里只考虑其为$ | 1\rangle $的子空间, 忽略其余部分 Figure6. (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.