基于量子算法的量子态层析新方案

摘要

在经典信息可有效制备为量子态和量子算法可物理实现的条件下,深入研究了量子算法如何有效改善基于线性回归估计的量子态层析算法的时间复杂度问题.在已有的量子算法基础上,形成了量子态层析的新方案.与现有的经典算法相比,本文所提方案需要引入量子态制备和额外的测量环节,但能显著降低量子态层析的时间复杂度.对于维数为d的待重构密度矩阵,当所用的量子算法涉及的矩阵的条件数κ和估计精度ε的倒数的复杂度均为O(poly log d),且所需同时制备的量子态数目规模是O(d)时,本方案可将量子态层析整体算法的时间复杂度从O(d4)降为O(dpoly log d).