《武汉工程大学学报》 2015年02期
72-76
出版日期：2015-02-28
ISSN:1674-2869
CN:42-1779/TQ
基于矩阵填充技术重构低秩密度矩阵
０ 引 言随着信息技术的飞速发展，重构量子态以及某些物理过程，在物理学、尤其量子信息科学领域的重要性日益增加［１］. 而描述一个量子系统，最为普遍的方法是求解密度矩阵，它提供了一个量子态最完整的描述和解决方案［２］. 因此，如何从可测量量中准确地重构密度矩阵，在科学研究上具有非常重要的意义. 重构泡利测量下密度矩阵的问题被普遍应用于量子态层析中，这是由于大多数物理过程关注的量子态都可用低秩密度矩阵准确描述，而且泡利基下的张量积结构容易在实验中测得. 本文利用矩阵填充技术在泡利测量基础上能够有效地降低密度矩阵测量过程的复杂性，在一个矩阵可压缩或可稀疏表示时，通过观测矩阵的某种线性或非线性运算后的元素，来有效地重构出该矩阵. １ 相关技术１．１ 矩阵填充原理矩阵填充原理是在压缩感知理论的基础上衍生发展的，于２００６年兴起的压缩感知［３］理论，其核心思想是通过采集部分信息恢复傅里叶基下完整的稀疏信号. 而现实研究中的信号通常可以用矩阵形式表示，若目标矩阵的特征值具有稀疏性（即低秩性）则可通过采集部分矩阵元恢复出完整的目标矩阵［４］，这就是衍生出的矩阵填充原理［５］. 矩阵填充主要研究的问题是：通过凸优化算法，仅采集部分数据和信息，有效地将目标矩阵准确重构出来. 其具体的数学形式为： minimize rank(X) subject to PΩ(X)=ＰΩ(M)（１）其中X表示重构矩阵，M表示原始目标矩阵，ＰΩ代表矩阵M的投影集合. 然而，根据（１）式，在秩最小化的条件下实现矩阵填充是一个ＮＰ－ｈａｒｄ问题，则可把该问题转化为解决核范数最小化来重构未知矩阵： ｍｉｎｉｍｉｚｅ ||Ｘ||* ｓｕｂｊｅｃｔ ｔｏ ＰΩ（Ｘ）＝ＰΩ（Ｍ） （２）式（2）中||Ｘ||*为核范数，即奇异值之和，数学表达式为 ||Ｘ||*=■?滓i(Ｘ)任何理论都需要满足一定的条件才能实现，矩阵填充也不例外，从上述可知，要想利用矩阵填充原理重构目标矩阵，除了要满足矩阵的低秩性以外，在采样方式和数目上也有限制. 一般地，矩阵填充原理采取均匀等分方式采样；维数为ｄ×ｄ，秩为ｒ的矩阵Ｍ，进行奇异值分解［６］（ＳＶＤ），得矩阵Ｍ独立元的个数为ｒ（２ｄ－ｒ）. 如果采样数目m少于ｒ（２ｄ－ｒ），那么无论采取何种采样方式都无法实现矩阵填充，也就是说，采样数目必须满足ｍ≥ｒ（２ｄ－ｒ）. １．２ 奇异值阈值（ＳＶＴ）算法在解决矩阵填充问题上， ＳＶＴ算法是一种简单、易于实现的迭代算法，其核心是解决目标矩阵的凸优化问题，即核范数最小化问题. 通过对矩阵的奇异值进行软阈值分解，选取合适的步长和阈值极限，ＳＶＴ就能无限收敛接近于目标矩阵，该算法占用存储空间小、计算成本低，是重构低秩矩阵行之有效的方法［７］.１．２．１ 奇异值阈值（ｓｈｒｉｎｋ）算子 根据式（２）中，定义优化变量Ｘ∈Ｒｄ×ｄ，取τ＞０，步长集合为｛δｋ｝ｋ≥１，以Ｙ０＝０∈Ｒｄ×ｄ为起始，算法定义为：Ｘｋ＝ｓｈｒｉｎｋ（Ｙｋ－１， τ）Ｙｋ＝Ｙｋ－１＋δｋＰΩ（Ｍ－Ｘｋ） （３）ｓｈｒｉｎｋ（Ｙｋ－１， τ）是一种非线性函数，称为奇异值阈值算子，它是与核范数相关的近似操作，主要思想是将软阈值法则用到输入矩阵的奇异值上. 考虑秩为ｒ的矩阵Ｘ∈Ｒｄ×ｄ，奇异值分解式为Ｘ＝Ｕ∑Ｖ*，∑＝ｄｉａｇ（｛σ｝１≤ｉ≤ｒ），对于τ≥０，设软阈值算子Ｄτ作如下定义Ｄτ（Ｘ）：＝ＵＤτ（∑）Ｖ*，Ｄτ（∑）＝ｄｉａｇ（{（σｉ－τ）＋}）其中ｔ＋表示ｔ的正数部分，即ｔ＋＝ｍａｘ（０，ｔ）. 也就是说，这个操作是将软阈值法则用到矩阵Ｘ的奇异值上，从而有效地向零向量收缩.１．２．２ 阈值迭代 下面介绍ＳＶＴ算法，对于τ＞０数列｛δｋ｝为正的迭代步长，以Ｙ０开始，ｋ取值为ｋ＝１，２，３…,式（３）变为 Ｘｋ＝Ｄτ（Ｙｋ－１）Ｙｋ＝Ｙｋ－１＋δｋＰΩ（Ｍ－Ｘｋ） 这个阈值迭代是比较容易实现. 在每一步骤中，仅需计算奇异值（ＳＶＤ）和执行初等矩阵运算即可. 在标准的数值线性代数包的基础上，此算法用计算机编码就可实现. 定义非负整数ｌ≤ｄ，对于每组奇异向量有， ［Ｕｋ，∑ｋ，Ｖｋ］ｌ ｋ＝１，２，３其中Ｕｋ＝［Ｕ■■，…，Ｕ■■］，Ｖｋ＝［Ｖ■■，…，Ｖ■■］，∑ｋ是一个对角矩阵，奇异值σ■■，…，σ■■ 在其对角线上. 运行算法，直到达到截止标准停止. ＳＶＴ算法的程序运行步骤如表１所示. 表１ ＳＶＴ算法具体步骤Ｔａｂｌｅ １ Ｔｈｅ ｓｐｅｃｉｆｉｃ ｓｔｅｐｓ ｏｆ ＳＶＴ ａｌｇｏｒｉｔｈｍ１．３ 泡利测量下的密度矩阵若一未知量子态是纯态或者近似纯态，则密度矩阵ρ∈Ｒｄ×ｄ，秩为ｒ，迹为１，其中希尔伯特空间维数ｄ＝２ｎ. 设ｗ１，ｗ２，…，ｗ■为Ｒｄ×ｄ中的标准正交基，对应于希尔伯特－施密特［８］（Ｈｉｌｂｅｒｔ－Ｓｃｈｍｉｄｔ）内积 （Ａ，Ｂ）＝ｔｒ（Ａ*Ｂ），从｛ｗ１，ｗ２，…，ｗ■｝中随机均分采样出ｍ个元素Ｐ１，Ｐ２，…，Ｐｍ，得观测系数（Ｐｉ，ρ），则可利用算法从这些数据中重构ρ. 以泡利测量为例，考虑自旋为■，ｎ量子比特的体系，下面利用泡利矩阵描述这一系列测量值，形式记为：ｗ＝?茚■■■■■ｗｉ，其中?茚表示张量积，ｗｉ∈｛１，σｘ，σｙ，σｚ｝，其中 1=1 00 1，σｘ=0 11 0，σｙ=0 -ii 0，σｚ=1 00 -1由直积法则可知，ｗ共有ｄ２个矩阵元，记为ｗ（ａ），ａ∈［１，ｄ２］. 从ｗ（ａ）中随机采集ｍ个元素Ｓ１，Ｓ２，…，Ｓｍ∈［１，ｄ２］，从期望值ｔｒρｗ（Ｓｉ）中重构密度矩阵. 为实现重构密度矩阵，要在矩阵空间上解决如下凸优化问题：ｍｉｎ ||?姿||*Ｓｕｂｊｃｅｔ ｔｏ tr?姿=1, trｗ(Ｓｉ)?姿=trｗ(Ｓｉ)ρ其中||?姿||*是核范数，即奇异值之和. ?姿为通过凸优化重构的矩阵，与目标矩阵ρ相对应. 显然地，如果ρ在｛ｗ（Ｓｉ）｝基下几乎没有非零系数，那么ＳＶＴ算法很难实现重构密度矩阵. 为避免这种情况，必须保证运算过程中采集到ρ足够的重要信息，这就是很多文献中所提出的“不相关”概念. 一般地，在某些特定的基（泡利基）下，任何低秩矩阵都是不相关的. ２ 基于矩阵填充重构密度矩阵本文利用矩阵填充优化算法，能够有效、快速地重构泡利测量下的密度矩阵. 在核范数最小化的矩阵填充问题上， ＳＶＴ算法主要是通过选择恰当的迭代步长使收敛集合无限接近于目标矩阵来实现重构. ＳＶＴ算法的主要参数为步长、截止标准、最大迭代次数、采样率. ２．１ 迭代步长如何选取合适的迭代步长是优化算法的关键问题. 若步长选择过大，算法会发散，相反，步长过小，算法的收敛速率会很慢. 要保证ＳＶＴ算法的收敛性，迭代步长δ需满足０＜δ<２，在研究中，一般使用１．２倍的采样率的倒数来表示步长. 即δ＝１．２■. 实验结果显示，步长对改变矩阵维数、秩、采样率都有重要的作用. ２．２ 截止标准ＳＶＴ算法的截止标准为 ■≤?着实验中，选取截止标准ε为１×１０－４. ２．３ 最大迭代次数最大迭代次数表示为ρａｘｉｔｅｒ＝５００.２．４ 采样率维数为ｄ×ｄ，采样数目为ｍ，采样率定义为：p=■.３ 数值结果泡利测量下的密度矩阵可通过ｃｖｘ程序包编程进行数值模拟. ｃｖｘ是用于解决非约束和带约束条件的凸优化问题，它是一种基于Ｍａｔｌａｂ语言的建模系统. 由于所研究的密度矩阵可用张量积直乘的形式表示，则用计算机代码容易实现. 本文的实验数据是在ＣＰＵ：２ ＧＨｚ；内存：２ ＧＢ的普通计算机上，使用Ｍａｔｌａｂ软件程序模拟得到. 利用ＳＶＴ算法，通过在矩阵空间Ω上随机等分采样，得到如图１到图３的数值结果. 图1 不同采样率下的相对误差曲线图Fig.1 The relative error with sampling density in 6qubits and 7qubits首先，分析自旋为■，６量子比特、７量子比特的态，泡利测量下的密度矩阵重构效果见图１. 重构效果用恢复矩阵与原始矩阵的相对误差值表征，随着采样率逐渐增加，相对误差逐渐减小，一般地，当相对误差小于１０－４时，便认为是非常准确的重构结果. 对于６量子比特［图１（ａ）］，６４×６４维的量子态，采样率约为４０％时，密度矩阵基本实现重构，对于７量子比特［图１（ｂ）］，１２８×１２８维的量子态，采样率约为２５％时，密度矩阵基本实现重构.其次，分析在实现密度矩阵重构的情况下，最小采样率、所用时间分别与维数大小的关系（见图２、３）. 对于自旋为■，量子比特分别为６、７、８、９的体系，从图２中可知，随着维数增大，最小采样率逐渐减小，即仅需采集非常少量的数据便可准确的重构密度矩阵；所用时间（图３）虽然随着维数的增加而增长，但最长时间（维数为５１２×５１２时对应的时间）仅约有４０ s，运行速度非常快，这就是利用矩阵填充技术重构低秩矩阵的优越性.图2 不同维数下最小采样率变化图 Fig.2 The relation of minimum sampling图3 不同维数下所用时间图 Fig.3 The time required for SVT with the size ddensity with the size d通过对某一量子态下的密度矩阵相对误差的数值模拟和分析，得出重构效果良好的结论，在此基础上建模，能够很好地应用于量子态层析实验上，根据所建模型，在已知少量（不到一半）数据的情况下即可得到完整密度矩阵信息，且准确度较高.为保证所建模型的可行性，本文除了评估重构矩阵的准确度外，还从最小采样率、所用时间方面进行讨论. 最小采样率代表密度矩阵恰好实现重构时对应的采样数目与维数之比. 一般认为，对于维数越大的矩阵，越需要从原始矩阵中采集较多的数据才能进行重构，但是由于密度矩阵的低秩性（即特征值的稀疏性），目标矩阵可通过特别少量的数据成功重构，且维数越大，需要的数据反而越少，这说明基于矩阵填充技术能够解决低秩大矩阵问题.另外，原则上，维数越大的矩阵，模拟实验过程越耗时，但是随着采样率的降低，大大缩短了运行时间，这为研究更大量子比特下的密度矩阵问题提供参考基础. ４ 结 语将近年来新兴的矩阵填充理论应用于重构泡利测量下未知密度矩阵中，用Ｍａｔｌａｂ软件程序进行数值模拟，并且获得显著的重构效果，这为量子态层析提供了研究基础，对研究纯态或者近似纯态的量子体系具有一定意义. 致 谢本论文的研究是在硕士生课题方向的基础上开展的，感谢赵清教授、冯中营老师、康睿丹老师、王卫星老师对我的论文撰写和研究过程给予的帮助和指导. 论文引用了数位学者的研究文献，在此一并表示感谢！