Variational algorithms for linear algebra

线性代数的量子变分算法

Quantum algorithms have been developed for efficiently solving linear algebra tasks.However,they generally require deep circuits and hence universal fault-tolerant quantum computers.In this work,we propose variational algorithms for linear algebra tasks that are compatible with noisy intermediate-scale quantum devices.We show that the solutions of linear systems of equations and matrix–vector multiplications can be translated as the ground states of the constructed Hamiltonians.Based on the variational quantum algorithms,we introduce Hamiltonian morphing together with an adaptive ans?tz for efficiently finding the ground state,and show the solution verification.Our algorithms are especially suitable for linear algebra problems with sparse matrices,and have wide applications in machine learning and optimisation problems.The algorithm for matrix multiplications can be also used for Hamiltonian simulation and open system simulation.We evaluate the cost and effectiveness of our algorithm through numerical simulations for solving linear systems of equations.We implement the algorithm on the IBM quantum cloud device with a high solution fidelity of 99.95%.

量子算法可用于高效解决线性代数问题.然而,对于一般的线性代数问题,通常需要深层量子线路和容错量子计算机,这就超出了现有的技术水平.本文提出变分量子算法来解决线性代数问题,可兼容中等规模含噪声量子器件.解线性方程组和矩阵乘法问题可以被转换为解有效哈密顿量的基态问题.基于变分算法,结合绝热演化的思想,作者采用自适应线路拟设来求解基态问题,并给出了求解的验证判据.另外,通过数值方法可对该算法的实用性和资源估计进行分析和验证.本文算法在IBM量子云平台机器进行了实验验证,求解达到了99.95%的保真度.研究表明本文提出的量子算法适用于稀疏矩阵的求解问题,可用于机器学习和优化等问题.其中矩阵乘法问题可用于量子演化和开放系统演化等量子模拟问题.