论文标题
使用Richardson推断来增强量子线性系统算法
Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
论文作者
论文摘要
我们提出了一种量子算法，以求解表单$ a \ mathbf {x} = \ mathbf {b} $的线性方程式的系统，其中$ a $是tridiagonal toeplitz matrix和$ \ \ \ mathbf {b} $ coutivaltic confcection/$ poction/$ pogrigity（ \ log（n））$，其中$ n $表示方程数，$ε$是准确性，而$κ$是条件编号。必须运行\ emph {repot-until-success}算法$ \ MATHCAL {o} \ left（κ/（1-ε）\右）$ times才能成功，利用幅度扩增，并采样$ \ natercal {o}（o}（o}（o}（1/amis^2）$ times $ times。因此，该算法在$ n $方面取得了指数的改进。特别是，我们提出了有效的甲壳，用于状态制备，哈密顿模拟和一组可观察到的牙齿，以及相应的误差和复杂性分析。作为这项工作的主要结果，我们展示了如何使用Richardson外推来增强哈密顿模拟，从而在该算法中以$ 1/\sqrtε$电路复杂性而不是$ 1/ε$进行量子相估计（QPE）实施，并且可以并行化。此外，我们分析了与经典方法相比，总体算法的必要条件以实现指数加速。我们的方法不仅限于考虑的设置，并且可以应用于通过产品公式近似哈密顿模拟的更一般的问题，尽管我们的理论结果需要相应地扩展。所有提出的过程均以Qiskit实施，并使用经典模拟对小型系统进行了测试，并使用IBM量子体验可用的真实量子设备进行了测试。
We present a quantum algorithm to solve systems of linear equations of the form $A\mathbf{x}=\mathbf{b}$, where $A$ is a tridiagonal Toeplitz matrix and $\mathbf{b}$ results from discretizing an analytic function, with a circuit complexity of $poly(\log(κ), 1/\sqrtε, \log(N))$, where $N$ denotes the number of equations, $ε$ is the accuracy, and $κ$ the condition number. The \emph{repeat-until-success} algorithm has to be run $\mathcal{O}\left(κ/(1-ε)\right)$ times to succeed, leveraging amplitude amplification, and sampled $\mathcal{O}(1/ε^2)$ times. Thus, the algorithm achieves an exponential improvement with respect to $N$ over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation and a set of observables together with the corresponding error and complexity analyses. As the main result of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with $1/\sqrtε$ circuit complexity instead of $1/ε$ and which can be parallelized. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although, our theoretical results would need to be extended accordingly. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.
