Inverting well conditioned matrices in quantum logspace
Inverting well conditioned matrices in quantum logspace
复制标题
量子对数空间中的良条件矩阵的逆
DOI：
10.1145/2488608.2488720
复制
发表时间：
2013
影响因子：
5.2
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
A. Ta
我们表明，量子计算机改善了最知名的经典算法矩阵求逆（和奇异值分解），就空间而言。这增加了（仍然很短的）量子计算机可以帮助解决的重要问题。具体来说，我们证明了一个良好的条件矩阵的逆可以近似在量子对数空间与中间测量。这应该是比较与最著名的经典算法的问题，需要Ω（log2 n）空间。我们还展示了如何近似一个正常的矩阵的谱，或一个任意矩阵的奇异值，具有ε加性精度，以及如何近似奇异值分解（SVD）的矩阵的奇异值是很好的分离。
该技术建立在以前几项工作的基础上，包括在小量子空间中模拟哈密顿[2][10]，将厄米矩阵视为哈密尔顿算子，并在其上运行量子相位估计过程（建立在[5]）和使小空间概率（和量子）计算通过使用离线随机性和移位和截断方法（建立在[8]上）保持一致。
We show that quantum computers improve on the best known classical algorithms for matrix inversion (and singular value decomposition) as far as space is concerned. This adds to the (still short) list of important problems where quantum computers are of help. Specifically, we show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires Ω(log2 n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with ε additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated.
The technique builds on ideas from several previous works, including simulating Hamiltonians in small quantum space (building on [2] and [10]), treating a Hermitian matrix as a Hamiltonian and running the quantum phase estimation procedure on it (building on [5]) and making small space probabilistic (and quantum) computation consistent through the use of offline randomness and the shift and truncate method (building on [8]).