1.   引　言

量子态层析(quantum state tomography), 也称为量子态估计(quantum state estimation)^[1], 是通过测量数据来推断被测量子态的方法. 对于n量子比特构成的量子系统, 其维数$d = 2^n$, 因而量子态层析任务的时间复杂度随着问题规模的增加成指数增长. 量子态层析分为2个阶段, 即测量阶段和使用测量数据重构量子态阶段. 当面对的量子系统维数较高时, 这2个环节的时间复杂度会很大. 例如文献[2]的研究者面对8离子的量子系统, 耗费10多个小时在测量和数据采集的环节, 而又花费了将近一周时间使用数据进行量子态重构. 因此, 选择合适的测量集及重构方法是解决量子态层析问题的关键. 量子态重构有多种方法, 如线性估计^[3]、线性回归估计^[4,5]、极大似然估计^[6,7]、贝叶斯均值估计^[8,9]等, 这些方法各有优势和不足.

量子算法是应用在量子计算机上的算法. 对于经典算法的难解问题, 有些可以找到量子算法使其在有效时间内解决^[10,11]; 有些在一定条件下可以加速问题的求解, 从而显现出量子算法的优势^[12,13]. 从机器学习的角度, 可以将量子算法整体看作是一个黑盒, 把测量数据及态生成源的数据作为训练集合, 训练得到量子态重构的模型. 这属于使用量子算法解决量子问题的范畴^[14]. 一个自然的问题是: 对于量子态层析的重构过程, 使用量子算法能否使其得到加速,从而使时间复杂度下降? 目前使用量子算法实现量子态重构的相关研究还不多, 并且还未发现从时间复杂度角度来分析量子态重构的量子算法与经典算法相比是否有优势的研究内容.

量子态重构过程的经典算法有多种, 不同算法又分为多个环节, 不同环节中的步骤涉及不同的操作, 这些操作对应的量子算法也有不同的实现方法, 因而并没有一个统一的量子算法来实现重构过程. 本文关注的问题是: 对于使用线性回归模型估计未知状态参数的量子态重构过程, 使用量子算法进行处理是否值得, 在什么条件下使用量子算法会加速任务的完成. 选择使用线性回归算法的估计过程, 原因在于它是几种重构算法中重构速度快于极大似然估计和贝叶斯估计的一种, 并且通过求解受约束的优化问题^[15], 避免了线性估计算法的重构矩阵可能存在负本征值的问题. 通过在重构算法的不同步骤中选择相应的量子算法, 可以形成一个实现量子状态重构的整体量子算法, 然后从时间复杂度的角度将其与经典算法进行对比分析.

当要求的精度和重构过程涉及到的矩阵条件数等指标, 满足使用量子算法进行加速的条件, 且所需制备的量子态数目与系统维数成正比时, 整个量子算法实现过程可以将目前使用线性回归估计实现量子态重构过程的总体时间复杂度, 由$O(d^4)$降低为$O(d {\rm poly}\log (d))$.

本文后续内容安排如下: 第2部分叙述基于线性回归估计的经典重构算法, 第3部分展示使用量子算法处理量子态重构的基本流程, 第4部分对比分析研究了分别使用经典算法和量子算法的时间复杂度, 第5部分是算例, 第6部分是结论.

2.   基于线性回归估计的经典重构算法

在测量存在高斯噪声时, 可以使用基于线性回归估计的重构算法, 来高效地重构量子状态^[4]. 要通过测量数据得到系统密度矩阵$\rho$的重构矩阵$\hat{\rho}$, 可以使用如图1所示的2个环节来进行.

图 1  基于线性回归估计的经典重构算法

Fig. 1.  Classical algorithm of quantum state tomography via linear regression

下载: 全尺寸图片 幻灯片

环节1)　使用测量得到的数据重构伪线性估计矩阵$\hat{\mu}$:

其中$\hat{\mu}$是厄米矩阵, 且满足${\rm tr}\; \hat{\mu} = 1$. $\hat{\mu}$被称为$\rho$的伪线性回归估计, 因为它可能存在负本征值, 但不具有物理意义. 需要使用环节2)通过$\hat{\mu}$重构出目标矩阵$\hat{\rho}$.

环节2)　找到与重构矩阵$\hat{\mu}$最接近的密度矩阵$\hat{\rho}$: 给定一个迹为1的厄米矩阵$\hat{\mu}$, 在2-范数下找到与其最接近的密度矩阵$\hat{\rho}$, 可以表达为

矩阵$\hat{\rho}$即是要重构出的目标矩阵.

下面分别叙述如何得到方程(1)和方程(2), 以及它们的求解过程.

2.1   使用测量数据重构伪线性估计矩阵$\hat{\mu}$ (环节1) )

可以使用线性回归估计^[4], 通过5个步骤得到量子状态中的未知参数, 并使用估计出的参数重构出$\hat{\mu}$. 下面对这5个步骤进行简要叙述.

1) 设量子系统的维数是d. 选取刘维尔空间(Liouville space)中的一组完备正交基, 记为$\left\{{ \varOmega}_i\right\}_{i = 0}^{d^2-1}$.

2) 分别将待重构的量子状态和测量基在刘维尔空间中展开, 得到相应的由展开系数构成的向量.

3) 计算测量算子作用于量子态所得到的测量结果的概率, 可以使用2)中的量子态和测量基在刘维尔空间中的展开系数表示测量结果概率.

4) 结合测量结果概率和实际测量的频率, 得到描述量子状态的未知参数$\varTheta$的线性估计模型:

5) 使用最小二乘法得到方程(3)的解$\hat{\varTheta}$:

这里已取对角权重矩阵${ W} ={ I}$. 方程(4)中, ${ X}\!=\! (\varPsi^{(1)},\cdots, \varPsi^{(M)})^{\rm T}$, ${ X}^{\rm T}{ X} = \sum\limits_{n = 1}^{M}\varPsi^{(n)}\; \varPsi^{(n)^{\rm T}}$. $\left\{|\varPsi\rangle\langle\varPsi| ^{(n)}\right\}_{n = 1}^M$是选取的一组测量基, $\varPsi^{(i)}$是测量基$|\varPsi\rangle\langle\varPsi| ^{(i)}$在刘维尔基下的展开系数. 当选择的这组测量基信息完备或过完备时, 矩阵${ X}^{\rm T}{ X}$是可逆的. ${ Y} =\left(\hat{p}_1- \dfrac{1}{d},...,\hat{p}_M-\dfrac{1}{d}\right)^{\rm T}$, $\hat{p}_j$是得到的测量结果j的频率, d是系统密度矩阵的维数.

至此, 通过量子状态在刘维尔空间一组基下的展开系数$\hat{\varTheta}$, 可以得到中间重构矩阵$\hat{\mu}$:

2.2   求与矩阵$\hat{\mu}$最接近的目标矩阵$\hat{\rho}$ (环节2))

这个问题可以表述为^[15]: 给定一个迹为1的厄米矩阵$\hat{\mu}$, 在2-范数下可以找到与其最接近的密度矩阵$\hat{\rho}$ (迹为1且只含有非负本征值的厄米矩阵)

要求解这个最小二乘的估计问题, 计算量比较大^[15]. 但文献[15]根据表达式的物理意义, 给出了如下的优化解决方法.

2-范数与所使用的基底是相互独立的, 可以选择$\hat{\mu}$的本征基作为基底, 将$\hat{\mu}$和$\hat{\rho}$展开, 则最优的$\hat{\rho}$在这组基矢下是对角阵. 这是因为在方程(2)中, 如果$\hat{\rho}$除对角线外存在非零的矩阵元, 这些矩阵元会贡献正的数值量使该式变大, 从而导致$\hat{\mu}$与$\hat{\rho}$的距离变大, 不符合目标的要求. 因而问题归结为求$\hat{\mu}$的本征值和本征态, 找出$\hat{\rho}$相应的d个非负本征值使方程(2)最小化. 该过程具体算法如下^[15].

1) 计算$\hat{\mu}$的本征值和本征态, 分别记为$\hat{\mu}_i,$ $|\hat{\mu}_i\rangle,\; 1\leqslant i\leqslant d$. 将得到的本征值从大到小按序排列.

2) 令$i = d$, 累加器$a = 0$.

3) 如果$\hat{\mu}_i+a/i < 0$, 令$\lambda_i = 0$, 将$\hat{\mu}_i$加到a上, 然后使i减少1, 重复步骤3). 如果$\hat{\mu}_i+a/i > 0$, 就进行第4)步.

4) 对于所有的$j\leqslant i$, 令$\lambda_j = \hat{\mu}_j+a/i$.

5) 构造出满足条件的$\hat{\rho}$, $\hat{\rho} = \sum\nolimits_i\lambda_i\; | \; \hat{\mu}_i\rangle\langle\hat{\mu}_i\; |$.

至此, 得到系统密度矩阵$\rho$的目标重构矩阵$\hat{\rho}$, 重构过程结束.

3.   量子态重构的量子算法处理过程

整个使用量子算法处理量子态重构的过程如图2所示, 可以分为以下几个环节:

准备环节　根据测量数据及选定刘维尔空间中的基, 制备相应的量子态${ X},\; { X}^{\rm T},\; |{ Y}\rangle,\; \{\varOmega_i\}$;

环节1)　使用测量得到的数据重构伪线性估计矩阵$\hat{\mu}$;

环节2)　找到与矩阵$\hat{\mu}$最接近的密度矩阵$\hat{\rho}$.

图 2  整体量子算法简明过程

Fig. 2.  Concise process of the whole quantum algorithm

下载: 全尺寸图片 幻灯片

对于量子态层析, 对量子态产生源进行测量, 得到的数据是经典数据, 因而需要在环节1)之前引入准备环节, 来制备量子数据${ X},\;{ X}^{\rm T},\; |{ Y}\rangle,\; \{\varOmega_i\}$. 这里对于矩阵的量子数据的符号仍使用原符号, 例如矩阵X和$\varOmega_i$即表示它们各自的量子数据; 对于向量的量子数据, 使用右矢形式, 例如$|{ Y}\rangle$表示向量Y的量子数据. 暂不考虑量子态制备的量子算法实现过程, 而假设能够有效制备量子态. 图2中环节1)和环节2)并行处理多个量子态, 其中每个单独过程与量子态重构的经典算法基本一致, 但注意到在经过本征值和本征态的估计算法之后, 需要引入测量以及量子态制备环节, 以与后面调用量子算法过程相衔接.

图2涉及的量子算法, 可归纳为以下几种: 1) 矩阵乘法的量子算法^[16]; 2) 矩阵求逆使用到的求解线性方程的量子算法^[17]; 3) 求解矩阵本征值和本征态的相位估计算法^[17]; 4) 对$\hat{\mu}$本征值进行排序的排序算法^[18,19]. 使用量子算法的具体过程如图3和图4所示, 下面简要叙述相应的量子算法.

图 3  量子算法过程1: 基于线性回归模型重构算法的量子算法

Fig. 3.  Quantum algorithm process 1: quantum algorithm based on quantum state tomography via linear regression

下载: 全尺寸图片 幻灯片

图 4  量子算法过程2

Fig. 4.  Quantum algorithm process 2

下载: 全尺寸图片 幻灯片

3.1   矩阵乘法的量子算法^[16]

设A是$d\times d$矩阵, 其奇异值分解为${ A} =$$\sum\nolimits_{i}\sigma_i|{ u}_i\rangle\langle { v}_i|$. 则存在量子算法, 可以实现以下输入态到输出态之间的转换:

其中$t = 1/({\rm max}_i\bar{\sigma}_i)$. 通过测量后选择$|0\rangle$得到态

其中$\sigma_i$的估计值$\bar{\sigma}_i$满足$|\bar{\sigma}_i-\sigma_i|\leqslant\varepsilon \|{ A}\|_F$. 设输入态$|{ b}\rangle = \sum\nolimits_ {i}\alpha_i|{{ v}}_i\rangle|0\rangle$, 则输出态即为${ A}|{ b}\rangle$. 包含测量后选择操作在内的整个矩阵乘法的量子算法的时间复杂度是$O(\kappa^3 \sqrt{d}/\varepsilon )$, $\kappa$是矩阵A的条件数, $\varepsilon$是精度. 在计算矩阵间的乘法${ A}\times { B}$时, 可以将B按列展开为$\{{ b}_i\}$, 然后使用量子算法并行处理${ A}|{ b}_i\rangle$.

3.2   矩阵求逆的量子算法^[17]

令A是$d\times d$矩阵, 其奇异值分解为${ A} = \sum\nolimits_{i}\sigma_i|{{u}}_i\rangle\langle {{v}}_i|$. 则存在量子算法可求解线性方程${ A}|{ x}\rangle = |{ b}\rangle$, 实现以下输入态到输出态之间的转换:

其中, $\sum\nolimits_i\alpha_i|{ v} _i\rangle = |{ b}\rangle$, $(-1)^{f_i}$是符号位, 当本征值为负时$f_i = 1$, 否则为0; $\gamma = O(1/\kappa)$, $\kappa$为矩阵A的条件数, $|\bar{\lambda}_i|$为A的本征值的绝对值. 对辅助量子比特进行测量, 当测量结果为$|0\rangle$时, 可以得到

它与方程的解$|{ x}\rangle = { A}^{-1}|{ b}\rangle$成正比. 包括测量后选择操作在内的整个矩阵求逆量子算法的时间复杂度为$O(\kappa^2 {\rm polylog}(n)\|{ A}\|_F/\varepsilon )$.

3.3   求解矩阵$\hat{\mu}$本征值和本征态的相位估计算法^[17]

令A是$d\times d$矩阵, 其奇异值分解为${ A} =$$\sum\nolimits_{i}\sigma_i|{ u}_i\rangle\langle { v}_i|$. 则存在量子算法, 可以实现以下输入态到输出态之间的转换:

其中的$\bar{\lambda}_i$和$|\vec{\mu}_i\rangle$分别是矩阵A的本征值和本征态.

此算法是基于矩阵求逆量子算法的部分过程实现的, 相比于矩阵求逆量子算法, 由于没有引入辅助量子比特并进行测量, 所以该量子算法的时间复杂度为$O(\kappa{\rm polylog}(d)\|{ A}\|_F/\varepsilon )$.

3.4   量子排序算法

以量子比较逻辑门(comparison gate)为基本单元, 可以构造排序算法的黑盒^[18]. 将量子态形式的矩阵$\hat{\mu}$的所有本征值的估计值作为黑盒的输入得到的输出结果是按本征值大小排列的量子态. 文献[19]则指出, 通过使用受控的比较逻辑门可以实现归并排序过程, 同样可以实现$\hat{\mu}$量子态本征值的排序. 在排序之后, 使用与第2.2节中的第1)到5)相对应的量子操作, 即可得到目标密度矩阵$\hat{\rho}$.

4.   经典和量子求解思路的时间复杂度对比

量子算法与经典算法过程的不同环节的时间复杂度如表1所示.

表 1  量子态重构过程不同环节的量子算法与经典算法时间复杂度的对比

Table 1.  Time complexity comparison of each step between quantum algorithm and classical algorithm for reconstructing quantum state

算法过程	时间复杂度
量子态制备过程:	经典	量子
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 

| 显示表格

下面分别具体分析量子态层析任务各个过程的经典算法和量子算法的时间复杂度.

4.1   经典算法各环节的时间复杂度

在第2节描述的使用经典算法进行量子态重构的2个环节, 第1)个环节使用最小二乘法求解模型, 在信息完备的测量集合下, X是$d^2\times(d^2-1)$矩阵, Y是$d^2\times 1$列向量, 因此${ X}^{\rm T}{ X}$以及${ X}^{\rm T}{ Y}$的计算复杂度均是$O(d^4)$; $({ X}^{\rm T}{ X})^{-1}$的时间复杂度一般是$O(d^6)$, 但在选择的测量集合满足一定条件下, $({ X}^{\rm T}{ X})^{-1}$的时间复杂度可以降为$O(d^4)$. 第1)环节最后1步中, 通过估计出的参数, 使用方程(1)重构伪线性估计矩阵$\hat{\mu}$的时间复杂度是$O(d^4)$, 原因是集合$\{\varOmega_i\}$有$d^2$个元素, 而每个元素$\varOmega_i$是$d\times d$矩阵, $\hat{\varTheta}$中的($d^2-1$)个数与$\{\varOmega_i\}(\; i\neq0)$相乘. 但正如文献[15]指出的, 若使用Pauli算子的张量积作为量子系统刘维尔空间中的一组基, 由于每一个$d\times d$的基矩阵都只有d个非0元, 则使用方程(1)的重构过程的时间复杂度可以降低为$O(d^3)$. 第2)个环节计算方程(2), 使用文献[15]的算法, 在寻找与矩阵$\hat{\mu}$最接近的$\hat{\rho}$过程中, 需要求解矩阵$\hat{\mu}$的本征值和本征态, 该步骤的时间复杂度通常是$O(d^3)$. 对得到的$\hat{\mu}$的本征值进行排序, 常用的经典排序算法时间复杂度是$O(d)$. 在排序之后, 使用基本的加法和除法操作, 得到矩阵$\hat{\rho}$的本征值$\{\lambda_i\}$, 该过程时间复杂度是$O(d)$. 最后, 通过$\{\lambda_i\}$和$\hat{\mu}$的本征态重构出目标矩阵$\hat{\rho}$, 此过程的时间复杂度是$O(d^3)$.

总结整个过程, 经典算法的最大时间复杂度出现在对矩阵$({ X}^{\rm T}{ X})^{-1}$求逆的步骤当中, 一般为$O(d^6)$. 选择合适的测量集时, 可以使该步骤复杂度降低为$O(d^4)$.

下面分析量子算法实现过程的时间复杂度.

4.2   量子算法各个环节时间复杂度分析

4.2.1   量子态制备的时间复杂度

在使用量子算法处理量子态重构过程的3个环节中，有2个环节涉及使用测量得到的经典数据制备量子态: i) 准备阶段; ii) 在环节2)中, 测量得到本征值后, 为在后续使用量子算法进行排序, 须制备量子态以存储本征值. 不同制备量子态的量子算法时间复杂度不同. 文献[16]给出了几种不同量子算法的时间复杂度: 1) $O((\log\tilde{\kappa})^ {5/2}(\log\log\tilde{\kappa})^2$$\times\log^c[(\log \tilde{\kappa})^2(\log\log\tilde{\kappa})^2)/\varepsilon ]\cdot(\log d)/\varepsilon )$, 其中$\tilde{\kappa}$是向量${ x}$的最大值与最小值的比率, d是向量维数, $\varepsilon$是要求的精度, c是某个常数; 2) $O(\log(d)/\varepsilon ^2)$; 3) $O(d\log(d)\log(1/\varepsilon ));\; {\rm 4})\; O(\tilde{\kappa}^ {3/2}(\log d)/\varepsilon )$. 可以观察到, 1)是$\tilde{\kappa}$对数的多项式时间复杂度; 1), 2)和4)是d的对数的时间复杂度; 3) 是精度$1/\varepsilon$的对数时间复杂度. 但还没有发现使$\tilde{\kappa},\; d,\; 1/\varepsilon$同时实现对数时间复杂度的量子算法. 当$1/\varepsilon = O({\rm poly}\log d)$时, 1), 2), 4)均可以实现$O({\rm poly}\log d)$的时间复杂度. 但由于1)与4)均与$\tilde{\kappa}$有关, 因此在表1中, 选取了$O(\log(d)/\varepsilon ^2)$作为量子态制备的时间复杂度的代表.

在图2所示的准备环节, 可以使用测量得到的经典数据制备N个量子态, 后续可以使用量子算法过程1以及估计本征值和本征态的量子算法, 对这些量子态并行处理. 但是制备多份量子态会导致在准备环节以及环节2)中的量子态制备过程的时间复杂度增大. 制备N个量子态相应的时间复杂度是$O(N\log(d)/\varepsilon ^2)$. 若制备的量子态个数N的规模是$O(d)$, 则相应的时间复杂度为$O(d\log(d)/\varepsilon ^2)$. 这里假定N的规模是$O(d)$, 是考虑到对d维量子系统来说, 其本征值个数不超过d, 在不同本征值之间大小相差不是特别悬殊时^[11], 测量得到这些本征值所需制备的量子态个数是$O(d)$. 当$1/\varepsilon$是$\log(d)$的多项式规模时, 量子态制备过程的最大时间复杂度是$O(d\; {\rm poly}\log d)$.

4.2.2   矩阵乘法量子算法的时间复杂度

对于信息完备的测量集合, 有${ X} = ( { X}_{ij})_{d^2\times (d^2-1)},$${ Y} = ({ Y}_{k})_{d^2\times 1}$. 集合$\{\varOmega_i\}$中的$d^2-1$个元素均是$d\times d$矩阵. 第1)环节中, 在能够有效制备${ X},\; { X}^{\rm T},\; |{ Y}\rangle,\; \{\varOmega_i\}$的前提下, 均可以使用矩阵乘法的量子算法得到${ X}^{\rm T}{ X},\; |{ X}^{\rm T}{ Y}\rangle$, 及重构中间矩阵$\hat{\mu}$过程中的$\sum\nolimits_i|\varTheta_{i}\rangle\varOmega_i$. 基于奇异值估计矩阵乘法的量子算法, 其时间复杂度是$O(\kappa^3\sqrt{n}/\varepsilon )$^[16], 其中$\kappa$是矩阵条件数, n是2个矩阵相乘时前一矩阵的列数及后一矩阵的行数, $\varepsilon$是要求的精度. 因而, 得到${ X}^{\rm T}{ X}$, $|{ X}^{\rm T}{ Y}\rangle$以及$\sum\nolimits_i|{\varTheta}_ i\rangle\varOmega_i$的时间复杂度均是$O(\kappa^3 d/\varepsilon )$, 而通过$\hat{\rho}$的本征值和本征态得到$\hat{\rho} =$ $\sum\nolimits_i|\lambda_i\rangle|\vec{\mu_i}\rangle\langle\vec{\mu_i}|$的时间复杂度是O$(\kappa^3 \sqrt{d}/\varepsilon )$. 当$\kappa$和$1/\varepsilon$都是$\log d$的多项式规模时, 使用矩阵乘法量子算法的最大时间复杂度是$O(d\; {\rm poly}\log d)$.

4.2.3   矩阵求逆量子算法的时间复杂度

使用基于奇异值估计量子算法的矩阵求逆算法, 文献[17]分析了其时间复杂度, 为$O(\kappa^2{\rm poly}\log (d)$$\|{ A}\|_F/\varepsilon )$. 对于求解量子线性系统的算法^[12], 可以假设$\|{ A}\|_F = O(\sqrt{d})$. 在量子态层析任务中, 如果选择正四面体测量基和正六面体测量基, 可以得到矩阵A是对角矩阵^[4], 同样有$\|{ A}\|_F = O(\sqrt{d})$成立. 因此在量子态重构过程中, 使用基于奇异值估计量子算法解矩阵求逆过程的时间复杂度是$O(\kappa^2\sqrt{d}{\rm poly}\log (d)/\varepsilon )$. 当$\kappa$和$1/\varepsilon$都是$\log(d)$的多项式规模时, 使用矩阵求逆量子算法的最大时间复杂度是$O(\sqrt{d}{\rm poly}\log d)$.

4.2.4   求解矩阵$\hat{\mu}$本征值、本征态量子算法的时间复杂度

使用表2中的量子算法求解中间重构矩阵$\hat{\mu}$的本征值和本征态. 由于此算法的基本过程是基于矩阵求逆量子算法, 文献[17]分析了矩阵求逆量子算法不含有测量后选择操作过程时, 求解过程的时间复杂度是$O(\kappa {\rm poly}\log (d)\|{ A}\|_F/\varepsilon )$. 表2的量子算法最后一步使用酉变换, 且不包含受控旋转门及测量后选择过程, 因而其时间复杂度是$O(\kappa{\rm poly}\log (d)$$\|{ A}\|_F/\varepsilon )$. 使用矩阵的秩r来表示, 则为$O(\kappa\sqrt{r}{\rm poly}$$\log (d)/\varepsilon )$.

下面解释为何要在估计本征值之后引入测量环节以及量子态制备环节. 通过量子算法得到矩阵$\hat{ \mu}$的本征值量子态、本征态, 不同的本征值量子态、本征态之间是纠缠的, 而后续的量子排序算法要求输入全部的本征值量子态. 因而需要引入测量环节得到本征值, 再将其转化为量子态数据. 例如, 通过表2的量子算法后, 若得到的态是$|\varPsi\rangle = \alpha|\bar{\mu}_a\rangle|\hat{\mu}_a\rangle+\beta|\bar{\mu} _b\rangle|\hat{\mu}_b\rangle$, $|\bar{\mu} _a\rangle$和$|\bar{\mu} _b\rangle$是存储了本征值估计值的量子态, $|\hat{\mu}_a\rangle,\; |\hat{\mu}_b\rangle$是相应的本征态. 对处于寄存器中的本征值估计值进行测量, 当测量结果是$\bar{\mu} _a$时, 态$|\varPsi\rangle$塌缩到$|\hat{\mu}_a\rangle$上; 测量结果是$\bar{\mu} _b$时, $|\varPsi\rangle$塌缩到$|\hat{\mu}_b\rangle$上. 因此, 在求解矩阵的本征值和本征态的量子算法之后, 通过引入测量环节提取出本征值信息并且分别进行存储; 为与后续的排序量子算法衔接, 还要将测量得到的本征值信息制备成量子态, 从而贯通整个使用量子算法处理量子态层析的过程.

4.2.5   本征值排序量子算法的时间复杂度

在第2) 环节中, 将所有本征值制备成了N个量子态$\{|\bar{\mu}_i\rangle\}$之后, 可以使用排序量子算法对本征值进行排序. 对于排序过程, 文献[19]指出, 使用归并排序(merge sorting)量子算法的时间复杂度为$O((\log d)^2)$. 在这之后进行基本的量子逻辑操作得到目标密度矩阵$\hat{\rho}$的本征值$\{|\lambda_i\rangle\}$的时间复杂度最多是$O(d)$, 最后使用矩阵乘法的量子算法由$\{|\lambda _i\rangle\}$及$\hat{\mu}$的本征态$\{|\hat{\mu}_i\rangle\}$得到目标矩阵$\hat{\rho}$.

4.2.6   量子态重构过程整体量子算法的时间复杂度

总结上述分析过程, 当不考虑实现的资源代价, 而只追求降低整个过程的时间复杂度时, 若相关矩阵的条件数$\kappa$及要求的精度$1/\varepsilon$都是$\log(d)$的多项式规模时, 准备环节及环节2) 中的量子态制备过程是整体量子算法中时间复杂度最大的过程, 相应的时间复杂度是$O(N{\rm poly}\log d)$. 当制备的量子态的个数N的复杂度是$O(d)$时, 整个量子算法过程的时间复杂度是$O(d{\rm poly}\log d)$. 矩阵乘法的量子算法的时间复杂度也是$O(d{\rm poly}\log d)$.

5.   算　例

本节用一个算例来说明整体量子算法的可行性. 考虑单qubit的量子态层析, 记生成源为$\rho$, 此时系统的维数$d = 2$. 选取刘维尔空间中的一组基$\{\varOmega_l\}$:

其中, $l = 0,\; 1,\; 2,\; 3;\; \sigma_0 = I_{2\times2}\;,\sigma_x,\; \sigma_y,\; \sigma_z$分别为Pauli算子. 选择信息完备的正四面体测量基对$\rho$进行测量, 得到测量基在刘维尔空间展开系数构成的可逆矩阵X以及不同测量结果的频率构成的向量Y:

以下对照图2—图4叙述量子算法过程.

5.1   准备环节

首先制备量子态$\{\varOmega_i\},\; { X}^{\rm T},\; X,\; |{ Y}\rangle$. 根据给定的刘维尔空间中的基以及测量所得数据, 存在数据结构^[20], 可以存储矩阵的行元素以及矩阵每一行的范数, 为后续使用量子算法提供基础. 接下来考虑对制备的多个量子态中单个量子态进行处理的过程.

5.2   调用量子算法过程1求解中间重构矩阵$\hat{\mu}$

1) 使用矩阵乘法量子算法计算$|{ X}^{\rm T}{ Y}\rangle,\; { X}^{\rm T}{ X}$

量子算法过程1如图3所示. 首先调用矩阵乘法量子算法由${ X},\; { X}^{\rm T},\; |{ Y}\rangle$计算出$|{ X}^{\rm T}{ Y}\rangle,\;$X ^TX.

使用矩阵乘法量子算法^[16]计算矩阵与向量的乘积, 输入态由矩阵右奇异向量表示, 输出态由矩阵左奇异向量表示, 即可以得到以下输入态到输出态的变换过程:

其中, $|{ {v}}_i^{{ X}^{\rm T}}\rangle,\; |{ {u}}_i^{{ X}^{\rm T}}\rangle$分别是矩阵${ X}^{\rm T}$奇异值分解后的右奇异向量和左奇异向量; $\bar{\sigma}_i^{{ X}^{\rm T}}$是${ X}^{\rm T}$奇异值$\sigma_i^{{ X}^{\rm T}}$的估计值. 调用量子算法过程中, 会引入因子$t^{{ X}^{\rm T}} = \dfrac{1}{{\rm max}\bar{\sigma}_i^{{ X}^{\rm T}}}$. $|{ Y}\rangle$的展开系数与原始测量数据之间的关系为

由于${ X}^{\rm T}$的奇异值均为$\sigma_i^{{ X}^{\rm T}} = \dfrac{1}{\sqrt{2}}\;(i = 1,\; 2,\; 3)$, 同一量子算法过程的估计精度相同, 因而矩阵${ X}^{\rm T}$奇异值的估计值$\bar{\sigma}_1^{{ X}^{\rm T}} = \bar{\sigma}_2^{{ X}^{\rm T}} = \bar{\sigma}_3^{{ X}^{\rm T}}$相等. 为简明表达计算过程, 假定估计值与待估计值相等, 即$\bar{\sigma}_i^{{ X}^{\rm T}} = \sigma_i^{{ X}^{\rm T}} = \dfrac{1}{\sqrt{2}}\;(i = 1,\; 2,\; 3)$. 最终得到

对于${ X}^{\rm T}{ X}$, 设${ X} = [{ X}_1\; { X}_2\; { X}_3]$, 可使用矩阵乘法量子算法同时求解$|{ X}^T{ X}_1\rangle,\; |{ X}^T{ X}_2\rangle,$ $|{ X}^T{ X}_3\rangle$, 得到

同样设定得到奇异值估计值与待估计值相等, 即$\bar{\sigma}_i^{{ X}^{\rm T}} = \sigma_i^{{ X}^{\rm T}} = \dfrac{1}{\sqrt{2}}$, 从而有

2) 使用矩阵求逆量子算法计算得到$| \varTheta\rangle$

设${ A} = { X}^{\rm T}{ X},\; |{ b}\rangle = |{ X}^{\rm T}{ Y}\rangle,\; { A}| \varTheta\rangle = |{ b}\rangle$, 要得到$|\varTheta\rangle = |{ A}^{-1}{ b}\rangle$. 基于奇异值估计的量子算法的存储结构要求存储的是矩阵列向量元素, 以及矩阵行向量的2-范数^[20]. 由矩阵乘法量子算法计算得到的$|{ X}^{\rm T}{ X}_1\rangle,\; |{ X}^{\rm T}{ X}_2\rangle,\; |{ X}^{\rm T}{ X}_3\rangle$对应矩阵A的列向量. 由于选取的测量基使得A是对角矩阵, 由对角矩阵对称性可知$|{ X}^{\rm T}{ X}_i\rangle$中的元素相当于矩阵A的行向量中的元素, 因而满足使用奇异值估计量子算法的存储结构, 可以使用$|{ X}^{\rm T}{ X}_i\rangle$直接参与后续量子算法运算过程, 而不必经过转置操作. 因而

以方程(10)得到的结果$|{ b}\rangle = |{ X}^{\rm T}{ Y}\rangle =$ $\sum\nolimits_ {i}\dfrac{\alpha_i^{ Y}t^{{ X}^{\rm T}}}{\sqrt{2}}|{{u}}_i^{{ X}^{\rm T}}\rangle$作为输入态, 调用矩阵求逆量子算法, 可以得到以下变换:

其中包含了在调用量子算法时, 输入态$|{ b}\rangle$在基矢$|{{u}}_i^{{ X}^{\rm T}}\rangle$下展开转化为由$|{{v}}_i^{ A}\rangle$表示, 展开系数之间满足关系式:

对方程(13)输出量子态的辅助量子比特位进行测量, 若结果为$|0\rangle$, 则输出态塌缩到所需的矩阵求逆结果:

其中, $\gamma^A = O(1/\kappa)$, $\kappa$是矩阵A的条件数. A是正定厄米矩阵, 对A进行奇异值分解, 可以得到A的奇异值进而得到相应的本征值$\bar{\lambda}_i^{{ A}} = \bar{\sigma}_i^{ A} =$$t^{{ X}^{\rm T}}/2$, 因而

3) 重构中间矩阵$\hat{\mu}$

由方程(1), 矩阵$\hat{\mu} = \dfrac{\varOmega_0}{\sqrt{2}}+\sum\nolimits_{i = 1}^{3}\hat{\varTheta}_{i}\varOmega_i$. 根据$|\varTheta\rangle$以及$\{\varOmega_i\}$, 通过调用矩阵乘法量子算法可以得到$\hat{\mu}$, 具体过程如下.

首先计算$\sum\nolimits_{i = 1}^{3}\hat{\varTheta}_{i}\varOmega_i$, 可以将$\sum\nolimits_{i = 1}^{3}\hat{\varTheta}_{i}\varOmega_i$转化为计算$\hat{\varOmega}|\varTheta\rangle$. 具体操作如下: 将$\{\varOmega_i\}$的元素皆化为列向量,

记

将$\hat{\varOmega}$制备成量子态, 并进行奇异值分解, 可以得到

以方程(16)得到的结果为输入态, 调用矩阵乘法量子算法, 可以得到如下变换:

其中$|{{v}}_i^{\varOmega}\rangle,\; |{{u}}_i^{\varOmega}\rangle$分别是矩阵$\varOmega$奇异值分解后的右奇异向量和左奇异向量. $|\varTheta\rangle$在$|{{v}} _i^{ A}\rangle$和$|{{v}} _i^{\varOmega}\rangle$下的展开系数之间的关系为

从而得到$\hat{\varOmega}| \varTheta\rangle$的具体表达式为

可以观察到, 在调用量子算法过程中, 引入了因子$\dfrac{\gamma^{ A} t^{\varOmega}}{t^{{ X}^{\rm T}}}$. 因而在后续运算过程中, 需要乘以该因子的倒数以抵消其对运算结果的影响. 从而

(23)式得到的量子态$|\hat{\mu}\rangle$是相应于矩阵$\hat{\mu}$按列展开的向量, 因而对应的经典矩阵$\hat{\mu}$为

可以验证, 以上步骤得到的矩阵$\hat{\mu}$与使用经典算法时得到的矩阵$\hat{\mu}$是一致的.

5.3   计算目标重构矩阵$\hat{\rho}$

1) 估计$\hat{\mu}$的本征值本征态, 测量本征值并制备成量子态

设方程(24)中

对矩阵$\hat{\mu}$进行奇异值分解,

可以得到$|{{u}}_i^{\mu}\rangle = |{{v}}_i^{\mu}\rangle$. 设

可以计算得到

设输入态$|{ b}^{\mu}\rangle = \beta_1|{ {v}}^{\mu}_1\rangle|+\beta_2|{ {v}}^{\mu}_2\rangle$, 使用量子算法估计$\hat{\mu}$的本征值和本征态, 有以下输入态到输出态的变换:

其中, $|\vec{\mu}_1\rangle = [u_1\; u_2]^{\rm T},\; |\vec{\mu}_2\rangle = [v_1\; v_2]^{\rm T},\; |\bar{\mu}_i| = \sigma_i^{\mu}$.

对存储本征值叠加态的寄存器$||\bar{\mu}_i|\rangle$进行测量, 可以得到$\hat{\mu}$本征值的经典数据$\bar{\mu}_i$及相应的本征态量子态$|\vec{\mu}_i\rangle$. 在准备环节制备N个量子态的前提下, 对N个量子态进行测量得到$\hat{\mu}$所有的本征值$\bar{\mu} _1,\; \bar{\mu} _2$. 将这些本征值重新制备成量子态$|\bar{\mu} _1\rangle,\; |\bar{\mu}_2\rangle$, 继而调用量子算法过程2进行后续过程.

2) 进行量子算法过程2得到重构矩阵$\hat{\rho}$

首先使用排序算法对$|\bar{\mu}_1\rangle,\; |\bar{\mu}_2\rangle$进行排序, 然后通过一般操作得到目标重构矩阵$\hat{\rho}$的本征值.

对于中间重构矩阵$\hat{\mu}$, 注意到有$\bar{\mu}_1+\bar{\mu}_2 = 1$, 再观察方程(28)中的$\sigma_1^{\mu},\; \sigma_2^{\mu}$的表达式, 可知必有$\bar{\mu}_2\geqslant\bar{\mu}_1$成立, 因而$\hat{\mu}$的本征值之间的大小关系有2种情况: 1) $\bar{\mu}_2\geqslant\bar{\mu}_1 > 0$; 2) $\bar{\mu}_2 > 0 > \bar{\mu}_1$. 这里不妨设$\bar{\mu}_2 > 0 > \bar{\mu}_1$. 调用量子排序算法后, 得到由大到小排序的本征值量子态$|\bar{\mu}^{(1)}_ {2}\rangle,\; |\bar{\mu}^{(2)}_{1}\rangle$, 其中下标为原始本征值序号, 上标为排序后本征值序号. 通过与2.2节经典操作相应的一般量子操作, 使$|\bar{\mu}^{(2)}_{1}\rangle\rightarrow|\lambda_2\rangle = |0\rangle,\; |\bar{\mu}^{(1)}_ {2}\rangle\rightarrow|\lambda_1\rangle = |1\rangle$. 因而待重构矩阵$\hat{\rho}$为

下面使用矩阵乘法量子算法计算$|\vec{\mu} _2\rangle\langle\vec{\mu}_2|$. 与计算${ X}^{\rm T}{ X}$而将X表示成${ X} = [{ X}_1\; { X}_2\; { X}_3]$的过程类似, 这里将$\langle\vec{\mu}_2|$表示为$\langle\vec{\mu}_2| = [\bar{v}_1\; \bar{v}_2]$, 与$\langle\vec{\mu} _2|$本身的表达式相同, 然后使用矩阵乘法量子算法分别计算$\bar{v}_1|\vec{\mu} _2\rangle$以及$\bar{v}_2|\vec{\mu} _2\rangle$.

对$|\vec{\mu} _2\rangle$进行奇异值分解, 得到

对输入态$|{ b}^ {\vec{\mu}_2}\rangle = \alpha_1^{\vec{\mu}_2}|{{v}}_1^{\vec{\mu}_2}\rangle$调用矩阵乘法量子算法, 可以得到以下输入态到输出态的变换:

其中$\alpha_1^{\vec{\mu}_2} = \bar{v}_1,\; |{\bf{v}}_1^{\vec{\mu}_2}\rangle = 1,\; \bar{\sigma}^{\vec{\mu}_2} = \sigma^{\vec{\mu}_2} = 1$, 量子算法计算过程中引入了因子$t^{\vec{\mu}_2}$. 同理可以得到

其中$\alpha_2^ {\vec{\mu}_2} = \bar{v}_2$. 从而得到重构矩阵$\hat{\rho}$为

将方程(9), (14), (25)及(28)的表示代入到方程(34), 并去掉因子$t^{\vec{\mu}_2}$, 即得到最终的使用输入数据${ Y} = [y_1\; y_2\; y_3\; y_4]^{\rm T}$表示的重构矩阵:

其中

6.   结　论

本文深入探讨了处理量子态重构的整体量子算法. 通过在重构过程的不同步骤使用相应的量子算法, 得到了实现量子态重构的整体量子算法新方案. 对比分析表明: 对于d维密度矩阵, 经典算法的最大时间复杂度出现在矩阵乘法过程中, 为$O(d^4)$; 而对于量子算法, 在精度$\varepsilon$和矩阵的条件数$\kappa$等指标满足使用量子算法进行加速的条件下, 即$1/\varepsilon ,\; \kappa$的复杂度均为$O({\rm poly}\log d)$时, 量子算法的最大时间复杂度出现在量子态制备过程中, 为$O(N{\rm poly}\log d)$, 其中N为制备量子态的数目. 当制备的量子态数N的规模是$O(d)$, 即可得到中间重构矩阵$\hat{\mu}$所有的本征值时, 量子算法的时间复杂度为$O(d{\rm poly}\log d)$.

通俗地说, 本文主要试图回答如下问题: 如果量子计算机可物理实现且量子算法可以在量子计算机上物理实现, 那么量子算法在多大程度上可以降低量子态层析的时间复杂度? 研究表明, 如果量子态可以高效制备, 那么采用量子算法可将量子态层析整体算法的时间复杂度从$O(d^4)$降为$O(d {\rm poly}\log d)$; 如果量子态无法高效制备, 量子态层析整体算法的时间复杂度从$O(d^4)$降为$O(d^3)$. 因为对于量子态制备问题，制备维数为d²、规模为 O(d)的量子态，时间复杂度是 O(d³). 因此本研究从一个侧面证明了量子态能否高效制备已成为量子算法降低时间复杂度的瓶颈。

最后简要探讨本文所提方案的物理实现可行性. 文献[20]的作者讨论了奇异值估计量子算法能够实现的前提是构造出一种合适的存储经典数据的数据结构, 并在文章最后给出了具体的构造形式, 因而是能够物理实现的. 由于方案涉及的矩阵乘法、矩阵求逆以及本征值和本征态估计的量子算法均是基于奇异值估计的量子算法, 因而理论上是可以物理实现的. 方案涉及到的其他过程, 即量子态制备、测量以及量子排序, 是理论上能够实现或已经实现的^[14,19,21]. 因此总体来说, 本文所提方案具有物理实现的可行性.

附录　求解矩阵$\hat{\mu}$本征值和本征态的相位估计算法

求解矩阵$\hat{\mu}$本征值和本征态的相位估计量子算法如表A1所示. 这里使用的量子算法是在[17]基础上, 通过简单变换得到的.

若A为正定厄米方阵, 矩阵的奇异值分解也就是矩阵的本征分解, 矩阵A的奇异向量$|{{v}}_i\rangle$与其本征向量$|{\bf{\mu}}_i\rangle$相等. 若A为非正定厄米方阵, 将矩阵A分别用本征分解和奇异值分解来表示, 有

对于$\bar{\lambda}_i > 0,\; \vec{{ \mu}}_i = \vec{{{u}}}_i = \vec{{{v}}}_i$, 而当$\bar{\lambda}_i < 0$时, 可取$\vec{\mu_i} = -\vec{{{u}}} _i = \vec{{{v}}}_i$. 因此最终量子态的表示与一般的量子相位估计算法^[11]得到的形式类似, 但存储的是本征值的绝对值, 有一个受控相位门表示其本征值的符号位.

表 A1  求解厄米矩阵本征值和本征态的量子算法^[17]

Table A1.  Quantum algorithm for calculating the eigenvalues and eigenstates of Hermite matrix^[17]

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 

| 显示表格