Solving linear systems of equations is an essential component in science and technology, including in many machine learning algorithms. Existing quantum algorithms have demonstrated large speedup in solving linear systems, but the required quantum resources are not available on near-term quantum devices. In this work, we study potential near-term quantum algorithms for linear systems of equations. We investigate the use of variational algorithms for solving $Ax = b$ and analyze the optimization landscape for variational algorithms. We found that a wide range of variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, still suffer from a fundamentally different plateau problem. To circumvent this issue, we design a potentially near-term adaptive alternating algorithm based on a core idea: the classical combination of variational quantum states. We have conducted numerical experiments solving linear systems as large as $2^{300} \times 2^{300}$ by considering special systems that can be simulated efficiently on a classical computer. These experiments demonstrate the algorithm's ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.
翻译:解决线性方程系统是科学技术的重要组成部分,包括许多机器学习算法。现有的量子算法在解决线性系统方面表现出了巨大的速度,但短期量子装置没有提供所需的量子资源。在这项工作中,我们研究了线性方程系统的潜在近期量子算法。我们研究了使用变式算法解决$Ax=b$和分析变式算法的最佳景观。我们发现,为避免荒凉高原而设计的多种变式算法,如适当初始化的想象时间演进和非巴氏激发的优化,仍然受到一个根本不同的高原问题的影响。为绕过这一问题,我们设计了一个基于核心想法的近期适应性交替算法:变式量状态的经典组合。我们通过考虑在古典计算机上能够有效模拟的特殊系统,进行了相当于2 ⁇ 300美元(times 2 ⁇ 300)美元(times 300)$的线性系统。我们进行了数字实验。这些实验表明,算算算算算算算法能够将近100美元300美元300美元至300美元(qubb)的近距离的量子装置缩成系统大小。