-
在经典信息可有效制备为量子态和量子算法可物理实现的条件下, 深入研究了量子算法如何有效改善基于线性回归估计的量子态层析算法的时间复杂度问题. 在已有的量子算法基础上, 形成了量子态层析的新方案. 与现有的经典算法相比, 本文所提方案需要引入量子态制备和额外的测量环节, 但能显著降低量子态层析的时间复杂度. 对于维数为 d的待重构密度矩阵, 当所用的量子算法涉及的矩阵的条件数
$ \kappa $ 和估计精度$ \varepsilon $ 的倒数的复杂度均为$ O(\mathrm{poly}\log d) $ , 且所需同时制备的量子态数目规模是$ O(d) $ 时, 本方案可将量子态层析整体算法的时间复杂度从$ O(d^4) $ 降为$ O(d \mathrm{poly}\log d) $ .Recently, we try to answer the following question: what will happen to our life if quantum computers can be physically realized. In this research, we explore the impact of quantum algorithms on the time complexity of quantum state tomography based on the linear regression algorithm if quantum states can be efficiently prepared by classical information and quantum algorithms can be implemented on quantum computers. By studying current quantum algorithms based on quantum singular value decomposition (SVE) of calculating matrix multiplication, solving linear equations and eigenvalue and eigenstate estimation and so on, we propose a novel scheme to complete the mission of quantum state tomography. We show the calculation based on our algorithm as an example at last. Although quantum state preparations and extra measurements are indispensable in our quantum algorithm scheme compared with the existing classical algorithm, the time complexity of quantum state tomography can be remarkably declined. For a quantum system with dimension d, the entire quantum scheme can reduce the time complexity of quantum state tomography from$ O(d^{4}) $ to$ O(d\mathrm{poly}\log d) $ when both the condition number$ \kappa $ of related matrices and the reciprocal of precision$ \varepsilon $ are$ O(\mathrm{poly}\log d) $ , and quantum states of the same order$ O(d) $ can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to$O(d^3) $ when quantum states can not be efficiently prepared. In other words, the preparing of quantum states efficiently has become a bottleneck constraining the quantum acceleration.-
Keywords:
- quantum algorithm/
- quantum state tomography/
- time complexity
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] -
算法过程 时间复杂度 量子态制备过程: 经典 量子 1) ${ X}\rightarrow|{ X}\rangle$ — $O(d\log (d)/\varepsilon ^2)$ 2) ${ Y}\rightarrow|{ Y}\rangle$ — $O(d\log (d)/\varepsilon ^2)$ 3) $\{\varOmega_i\}\rightarrow\{|\varOmega_i\rangle\}$ — $O(d\log (d)/\varepsilon ^2)$ 最小二乘求解过程: 经典 量子 1) ${ X}^{\rm T}{ X}$ $O(d^4)$ $O(\kappa^3 d/\varepsilon )$ 2) $({ X}^{\rm T}{ X})^{-1}$ $O(d^4)$ $O(\kappa^2\sqrt{d}\mathrm{poly}\log(d)/\varepsilon )$ 3) ${ X}^{\rm T}{ Y}$ $O(d^4)$ $O(\kappa^3 d/\varepsilon )$ 使用估计出的参数重构密度矩阵$\hat{\mu}$: 经典 量子 1) ${ I}/d+\sum_{i=1}^{d}\hat{\varTheta}_i\varOmega_i$ $O(d^4)$ $O(\kappa^3 d/\varepsilon )$ 寻找与矩阵$\hat{\mu}$最接近的目标密度矩阵$\hat{\rho}$: 经典 量子 1) 求解矩阵$\hat{\mu}$的本征值和本征态$\{|\bar{\mu}_i\rangle|\hat{\mu}_i\rangle\}$ $O(d^3)$ $O(\kappa\sqrt{r}\mathrm{poly}\log d/\varepsilon )$ 2) 测量得到$\hat{\mu}$本征值数值$\{\bar{\mu} _i\}$ — $O(d)$ 3) 将$\hat{\mu}$的本征值数据制备成量子态 $\{\bar{\mu} _i\}\rightarrow\{|\bar{\mu} _i\rangle\}$ — $O(d\log(d)/\varepsilon ^2)$ 4) 对矩阵$\hat{\mu}$的本征值进行排序 $O(d)$ $O((\log d)^2)$ 5) 一般运算得到矩阵$\hat{\rho}$的本征值$\{\lambda_i\}$或$\{|\lambda_i\rangle\}$ $O(d)$ $O(d)$ 6) 由$\hat{\rho}$的本征值及$\{|\hat{\mu}_i\rangle\}$得到$\hat{\rho}=\sum_i\lambda_i|\hat{\mu}_i\rangle\langle\hat{\mu}_i|$ $O(d^3)$ $O(\kappa^3 \sqrt{d}/\varepsilon )$ 
下载:
导出CSV
1) 制备输入态$|{{b}}\rangle=\sum_i\beta_i|{{v}}_i\rangle$, 其中${{v}}_i$是矩阵A的奇异向量 2) 分别对矩阵A及${ A}+\eta { I}$使用奇异值估计算法, 精度$\delta<1/2\kappa$并且$\eta=1/\kappa$, 得到$\sum_i\beta_i|{{v}}_i\rangle_{ A}||\bar{\lambda}_i|\rangle_B||\bar{\lambda}_i+\eta|\rangle_C\rangle$ 3) 增加一辅助寄存器D, 当寄存器B的值大于C时, 将D置为1, 然后应用一受控于此辅助位的条件相位门: $\qquad\sum_i(-1)^{f_i}\beta_i|{{v}}_i\rangle_{ A}||\bar{\lambda}_i|\rangle_B||\bar{\lambda}_i+\eta|\rangle_C\rangle|f_i\rangle_D$ 4) 对寄存器C进行量子算法的逆运算, 得到态 $\qquad\sum_i(-1)^{f_i}\beta_i|{{v}}_i\rangle_{ A}||\bar{\lambda}_i|\rangle_B|f_i\rangle_D$ 5) 将奇异向量$|{{v}}_i\rangle_{ A}$转化到矩阵的本征态$|{{\mu}}_i\rangle_{ A}$上: 相应于正本征值的奇异向量不变, 相应于负本征值的奇异向量乘以–1 , 得到 $\qquad\sum_i(-1)^{f_i}\beta_i|{{\mu}}_i\rangle_{ A}||\bar{\lambda}_i|\rangle_B$ 下载:
导出CSV
-
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]
下载:
计量
- 文章访问数:10827
- PDF下载量:247
- 被引次数:0