论文标题
量子计算机上的精确有效的兰有方法
Exact and efficient Lanczos method on a quantum computer
论文作者
论文摘要
我们提出了一种使用量子计算机上编码的块来精确构建Krylov空间的算法，该算法可以用作兰西斯方法的基础，以估计哈密顿量的极端特征值。虽然经典的兰开斯方法在系统大小中具有指数成本以代表量子系统的Krylov状态，但我们的有效量子算法在多项式时间和内存中实现了这一点。所产生的Krylov空间与Lanczos方法相同的意义上是确切的，因此相对于确切方法的唯一近似值是由于有限的样品噪声所致。这是可能的，因为与以前的量子Krylov方法不同，我们的算法不需要模拟真实时间或假想时间的演变。在存在噪声的情况下，我们为最终的基态能量估计提供了明确的误差。为了使我们的方法有效地成功，输入问题的唯一要求是，初始状态与真正的基态的重叠必须为$ω（1/\ text {poly}（n））$ n $ qubits。
We present an algorithm that uses block encoding on a quantum computer to exactly construct a Krylov space, which can be used as the basis for the Lanczos method to estimate extremal eigenvalues of Hamiltonians. While the classical Lanczos method has exponential cost in the system size to represent the Krylov states for quantum systems, our efficient quantum algorithm achieves this in polynomial time and memory. The construction presented is exact in the sense that the resulting Krylov space is identical to that of the Lanczos method, so the only approximation with respect to the exact method is due to finite sample noise. This is possible because, unlike previous quantum Krylov methods, our algorithm does not require simulating real or imaginary time evolution. We provide an explicit error bound for the resulting ground state energy estimate in the presence of noise. For our method to be successful efficiently, the only requirement on the input problem is that the overlap of the initial state with the true ground state must be $Ω(1/\text{poly}(n))$ for $n$ qubits.
