Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
复制标题
DOI：
10.22331/q-2020-11-11-361
复制
发表时间：
2019-10
期刊：
影响因子：
6.4
通讯作者：
Lin Lin-Lin;Yu Tong
中科院分区：
文献类型：
--
作者：
Lin Lin-Lin;Yu Tong
提出了一种基于量子信号处理和极小极大多项式的量子本征态滤波算法。该算法允许我们有效地准备给定哈密顿量的目标本征态，如果我们可以获得与目标本征态有非平凡重叠的初始态，并且具有合理的谱间隙下界。将该算法应用于量子线性系统问题(QLSP)，分别提出了基于量子绝热计算(AQC)和基于量子Zeno效应的两种算法。这两种算法都将最终解准备成一个纯状态，并在ad-稀疏矩阵上获得了接近最优的O~(dκ)(1/ϵ)查询复杂度，其中κ是条件数，ϵ是期望精度。这两种算法都不使用相位估计或幅度放大。
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimalO~(dκlog(1/ϵ))query complexity for ad-sparse matrix, whereκis the condition number, andϵis the desired precision. Neither algorithm uses phase estimation or amplitude amplification.