韋仙

太原工業(yè)學(xué)院理學(xué)系，山西 太原 030008

基于矩陣填充技術(shù)重構(gòu)低秩密度矩陣

韋仙

太原工業(yè)學(xué)院理學(xué)系，山西 太原 030008

從有限的信息中重構(gòu)低秩或者近似低秩矩陣的問(wèn)題日益受到人們的關(guān)注，解決這個(gè)問(wèn)題的技術(shù)稱為矩陣填充.對(duì)于一個(gè)希爾伯特空間下純態(tài)或者近似純態(tài)的量子體系（也就是低熵狀態(tài)），其密度矩陣是低秩的，且跡為1.將矩陣填充理論應(yīng)用于重構(gòu)泡利測(cè)量下未知密度矩陣中，用Matlab軟件程序進(jìn)行數(shù)值模擬，采用奇異值閾值算法，將軟閾值法則用在未知態(tài)密度矩陣的奇異值上，通過(guò)計(jì)算機(jī)編程，進(jìn)行閾值迭代，直至達(dá)到截止標(biāo)準(zhǔn)，能夠大大提高運(yùn)行速率.由于以泡利矩陣為基的張量積結(jié)構(gòu)便于在實(shí)驗(yàn)中獲得，以重構(gòu)泡利測(cè)量下的未知密度矩陣為例，采集了部分?jǐn)?shù)據(jù)，分析了矩陣的重構(gòu)結(jié)果.通過(guò)對(duì)重構(gòu)誤差、運(yùn)行時(shí)間、采樣率方面的研究，得出密度矩陣能夠通過(guò)矩陣填充技術(shù)完整重構(gòu)的結(jié)論.

矩陣填充；密度矩陣；低秩；量子態(tài)層析

0 引言

隨著信息技術(shù)的飛速發(fā)展，重構(gòu)量子態(tài)以及某些物理過(guò)程，在物理學(xué)、尤其量子信息科學(xué)領(lǐng)域的重要性日益增加［1］.而描述一個(gè)量子系統(tǒng)，最為普遍的方法是求解密度矩陣，它提供了一個(gè)量子態(tài)最完整的描述和解決方案［2］.因此，如何從可測(cè)量量中準(zhǔn)確地重構(gòu)密度矩陣，在科學(xué)研究上具有非常重要的意義.

重構(gòu)泡利測(cè)量下密度矩陣的問(wèn)題被普遍應(yīng)用于量子態(tài)層析中，這是由于大多數(shù)物理過(guò)程關(guān)注的量子態(tài)都可用低秩密度矩陣準(zhǔn)確描述，而且泡利基下的張量積結(jié)構(gòu)容易在實(shí)驗(yàn)中測(cè)得.本文利用矩陣填充技術(shù)在泡利測(cè)量基礎(chǔ)上能夠有效地降低密度矩陣測(cè)量過(guò)程的復(fù)雜性，在一個(gè)矩陣可壓縮或可稀疏表示時(shí)，通過(guò)觀測(cè)矩陣的某種線性或非線性運(yùn)算后的元素，來(lái)有效地重構(gòu)出該矩陣.

1 相關(guān)技術(shù)

1.1 矩陣填充原理

矩陣填充原理是在壓縮感知理論的基礎(chǔ)上衍生發(fā)展的，于2006年興起的壓縮感知［3］理論，其核心思想是通過(guò)采集部分信息恢復(fù)傅里葉基下完整的稀疏信號(hào).而現(xiàn)實(shí)研究中的信號(hào)通常可以用矩陣形式表示，若目標(biāo)矩陣的特征值具有稀疏性（即低秩性）則可通過(guò)采集部分矩陣元恢復(fù)出完整的目標(biāo)矩陣［4］，這就是衍生出的矩陣填充原理［5］.

矩陣填充主要研究的問(wèn)題是：通過(guò)凸優(yōu)化算法，僅采集部分?jǐn)?shù)據(jù)和信息，有效地將目標(biāo)矩陣準(zhǔn)確重構(gòu)出來(lái).其具體的數(shù)學(xué)形式為：

其中X表示重構(gòu)矩陣，M表示原始目標(biāo)矩陣，PΩ代表矩陣M的投影集合.

然而，根據(jù)（1）式，在秩最小化的條件下實(shí)現(xiàn)矩陣填充是一個(gè)NP－h(huán)ard問(wèn)題，則可把該問(wèn)題轉(zhuǎn)化為解決核范數(shù)最小化來(lái)重構(gòu)未知矩陣：

式（2）中||X||*為核范數(shù)，即奇異值之和，數(shù)學(xué)表達(dá)式為

任何理論都需要滿足一定的條件才能實(shí)現(xiàn)，矩陣填充也不例外，從上述可知，要想利用矩陣填充原理重構(gòu)目標(biāo)矩陣，除了要滿足矩陣的低秩性以外，在采樣方式和數(shù)目上也有限制.

一般地，矩陣填充原理采取均勻等分方式采樣；維數(shù)為d×d，秩為r的矩陣M，進(jìn)行奇異值分解［6］（SVD），得矩陣M獨(dú)立元的個(gè)數(shù)為r（2d－r）.如果采樣數(shù)目m少于r（2d－r），那么無(wú)論采取何種采樣方式都無(wú)法實(shí)現(xiàn)矩陣填充，也就是說(shuō)，采樣數(shù)目必須滿足m≥r（2d－r）.

1.2 奇異值閾值（SVT）算法

在解決矩陣填充問(wèn)題上，SVT算法是一種簡(jiǎn)單、易于實(shí)現(xiàn)的迭代算法，其核心是解決目標(biāo)矩陣的凸優(yōu)化問(wèn)題，即核范數(shù)最小化問(wèn)題.通過(guò)對(duì)矩陣的奇異值進(jìn)行軟閾值分解，選取合適的步長(zhǎng)和閾值極限，SVT就能無(wú)限收斂接近于目標(biāo)矩陣，該算法占用存儲(chǔ)空間小、計(jì)算成本低，是重構(gòu)低秩矩陣行之有效的方法［7］.

1.2.1 奇異值閾值（shrink）算子根據(jù)式（2）中，定義優(yōu)化變量X∈Rd×d，取τ＞0，步長(zhǎng)集合為｛δk｝k≥1，以Y0＝0∈Rd×d為起始，算法定義為：

shrink（Yk－1，τ）是一種非線性函數(shù)，稱為奇異值閾值算子，它是與核范數(shù)相關(guān)的近似操作，主要思想是將軟閾值法則用到輸入矩陣的奇異值上.

考慮秩為r的矩陣X∈Rd×d，奇異值分解式為

對(duì)于τ≥0，設(shè)軟閾值算子Dτ作如下定義

其中t＋表示t的正數(shù)部分，即t＋＝max（0，t）.也就是說(shuō)，這個(gè)操作是將軟閾值法則用到矩陣X的奇異值上，從而有效地向零向量收縮.

1.2.2 閾值迭代下面介紹SVT算法，對(duì)于τ＞0數(shù)列｛δk｝為正的迭代步長(zhǎng)，以Y0開始，k取值為k＝1，2，3…,式（3）變?yōu)?/p>

這個(gè)閾值迭代是比較容易實(shí)現(xiàn).在每一步驟中，僅需計(jì)算奇異值（SVD）和執(zhí)行初等矩陣運(yùn)算即可.在標(biāo)準(zhǔn)的數(shù)值線性代數(shù)包的基礎(chǔ)上，此算法用計(jì)算機(jī)編碼就可實(shí)現(xiàn).

定義非負(fù)整數(shù)l≤d，對(duì)于每組奇異向量有，

1.3 泡利測(cè)量下的密度矩陣

若一未知量子態(tài)是純態(tài)或者近似純態(tài)，則密度矩陣ρ∈Rd×d，秩為r，跡為1，其中希爾伯特空間維數(shù)d＝2n.設(shè)w1，w2，…，wd2為Rd×d中的標(biāo)準(zhǔn)正交基，對(duì)應(yīng)于希爾伯特－施密特［8］（Hilbert－Schmidt）內(nèi)積（A，B）＝tr（A*B），從｛w1，w2，…，wd2｝中隨機(jī)均分采樣出m個(gè)元素P1，P2，…，Pm，得觀測(cè)系數(shù)（Pi，ρ），則可利用算法從這些數(shù)據(jù)中重構(gòu)ρ.

表1 SVT算法具體步驟Table 1 The specific steps of SVT algorithm

由直積法則可知，w共有d2個(gè)矩陣元，記為w（a），a∈［1，d2］.從w（a）中隨機(jī)采集m個(gè)元素S1，S2，…，Sm∈［1，d2］，從期望值trρw（Si）中重構(gòu)密度矩陣.

為實(shí)現(xiàn)重構(gòu)密度矩陣，要在矩陣空間上解決如下凸優(yōu)化問(wèn)題：

其中||λ||*是核范數(shù)，即奇異值之和.λ為通過(guò)凸優(yōu)化重構(gòu)的矩陣，與目標(biāo)矩陣ρ相對(duì)應(yīng).

顯然地，如果ρ在｛w（Si）｝基下幾乎沒(méi)有非零系數(shù)，那么SVT算法很難實(shí)現(xiàn)重構(gòu)密度矩陣.為避免這種情況，必須保證運(yùn)算過(guò)程中采集到ρ足夠的重要信息，這就是很多文獻(xiàn)中所提出的“不相關(guān)”概念.一般地，在某些特定的基（泡利基）下，任何低秩矩陣都是不相關(guān)的.

2 基于矩陣填充重構(gòu)密度矩陣

本文利用矩陣填充優(yōu)化算法，能夠有效、快速地重構(gòu)泡利測(cè)量下的密度矩陣.在核范數(shù)最小化的矩陣填充問(wèn)題上，SVT算法主要是通過(guò)選擇恰當(dāng)?shù)牡介L(zhǎng)使收斂集合無(wú)限接近于目標(biāo)矩陣來(lái)實(shí)現(xiàn)重構(gòu).SVT算法的主要參數(shù)為步長(zhǎng)、截止標(biāo)準(zhǔn)、最大迭代次數(shù)、采樣率.

2.1 迭代步長(zhǎng)

2.2 截止標(biāo)準(zhǔn)

SVT算法的截止標(biāo)準(zhǔn)為

實(shí)驗(yàn)中，選取截止標(biāo)準(zhǔn)ε為1×10－4.

2.3 最大迭代次數(shù)

最大迭代次數(shù)表示為ρa(bǔ)xiter=500.

2.4 采樣率

維數(shù)為d×d，采樣數(shù)目為m，采樣率定義為：

3 數(shù)值結(jié)果

泡利測(cè)量下的密度矩陣可通過(guò)cvx程序包編程進(jìn)行數(shù)值模擬.cvx是用于解決非約束和帶約束條件的凸優(yōu)化問(wèn)題，它是一種基于Matlab語(yǔ)言的建模系統(tǒng).由于所研究的密度矩陣可用張量積直乘的形式表示，則用計(jì)算機(jī)代碼容易實(shí)現(xiàn).

本文的實(shí)驗(yàn)數(shù)據(jù)是在CPU：2 GHz；內(nèi)存：2 GB的普通計(jì)算機(jī)上，使用Matlab軟件程序模擬得到.利用SVT算法，通過(guò)在矩陣空間Ω上隨機(jī)等分采樣，得到如圖1到圖3的數(shù)值結(jié)果.

圖1 不同采樣率下的相對(duì)誤差曲線圖Fig.1 The relative error with sampling density in 6 qubits and 7qubits

通過(guò)對(duì)某一量子態(tài)下的密度矩陣相對(duì)誤差的數(shù)值模擬和分析，得出重構(gòu)效果良好的結(jié)論，在此基礎(chǔ)上建模，能夠很好地應(yīng)用于量子態(tài)層析實(shí)驗(yàn)上，根據(jù)所建模型，在已知少量（不到一半）數(shù)據(jù)的情況下即可得到完整密度矩陣信息，且準(zhǔn)確度較高.

圖2 不同維數(shù)下最小采樣率變化圖Fig.2 The relation of minimum sampling density with the size d

圖3 不同維數(shù)下所用時(shí)間圖Fig.3 The time required for SVT with the size d

為保證所建模型的可行性，本文除了評(píng)估重構(gòu)矩陣的準(zhǔn)確度外，還從最小采樣率、所用時(shí)間方面進(jìn)行討論.最小采樣率代表密度矩陣恰好實(shí)現(xiàn)重構(gòu)時(shí)對(duì)應(yīng)的采樣數(shù)目與維數(shù)之比.一般認(rèn)為，對(duì)于維數(shù)越大的矩陣，越需要從原始矩陣中采集較多的數(shù)據(jù)才能進(jìn)行重構(gòu)，但是由于密度矩陣的低秩性（即特征值的稀疏性），目標(biāo)矩陣可通過(guò)特別少量的數(shù)據(jù)成功重構(gòu)，且維數(shù)越大，需要的數(shù)據(jù)反而越少，這說(shuō)明基于矩陣填充技術(shù)能夠解決低秩大矩陣問(wèn)題.

另外，原則上，維數(shù)越大的矩陣，模擬實(shí)驗(yàn)過(guò)程越耗時(shí)，但是隨著采樣率的降低，大大縮短了運(yùn)行時(shí)間，這為研究更大量子比特下的密度矩陣問(wèn)題提供參考基礎(chǔ).

4 結(jié)語(yǔ)

將近年來(lái)新興的矩陣填充理論應(yīng)用于重構(gòu)泡利測(cè)量下未知密度矩陣中，用Matlab軟件程序進(jìn)行數(shù)值模擬，并且獲得顯著的重構(gòu)效果，這為量子態(tài)層析提供了研究基礎(chǔ)，對(duì)研究純態(tài)或者近似純態(tài)的量子體系具有一定意義.

致謝

本論文的研究是在碩士生課題方向的基礎(chǔ)上開展的，感謝趙清教授、馮中營(yíng)老師、康睿丹老師、王衛(wèi)星老師對(duì)我的論文撰寫和研究過(guò)程給予的幫助和指導(dǎo).論文引用了數(shù)位學(xué)者的研究文獻(xiàn)，在此一并表示感謝！

［1］MATTEO Paris，JAROSLAV Rehacek．Quantum state estimation［M］．Berlin:Springer Science＆Business Media，2004：1－8．

［2］戴宏毅．約化密度矩陣及其在量子信息處理中的應(yīng)用［J］．大學(xué)物理，2010，29（2）：31－33．

DAI Hong－yi．Reduced density matrix and its application in quantum information processing［J］．College Physics，2010，29（2）：31－33．（in Chinese）

［3］DONOHO D L．Compressed sensing［J］．IEEE Transactions on Information Theory，2006，52（4）：1289－1306．

［4］胡端平，唐超．一致矩陣的特征性質(zhì)［J］．武漢工程大學(xué)學(xué)報(bào)，2009，31（5）：93－94．

HU Duan－ping，TANG Chao．The character of consistent matrix［J］．Journal of Wuhan Institute of Technology，2009，31（5）：93－94．（in Chinese）

［5］楊建華，孫霞林．協(xié)方差矩陣在非負(fù)二次型估計(jì)中的可容許性［J］．武漢工程大學(xué)學(xué)報(bào)，2007，29（1）：75－77．

YANG Jian－h(huán)ua，SUN Xia－lin．Compatibility of nonnegative quadractic estimation［J］．Journal of Wuhan Institute of Technology，2007，29（1）：75－77．（in Chinese）

［6］EMMANUEL J Candès，TERENCE Tao．The power of convex relaxation：Near－optimal matrix completion［J］．IEEE Transactions on Information Theory，2010，56（5）：2053－2080．

［7］CAI Jian－feng，EMMANUEL J Candes，SHEN Zuowei．A sngular value thresholding algorithm for matrix completion［J］．Siam Journal of Optimization，2010，20（4）：1956－1982．

［8］DAVE Gross．Recovering low－rank matrices from few coefficients in any basis［J］．IEEE Transactions on Information Theory，2011，57（3）：1548－1566．

Reconstructing low－rank density matrix via matrix completion

WEI Xian
Faculty of Science，Taiyuan Institute of Technology，Shanxi 030008，China

The problem of reconstructing low－rank or approximately low－rank matrix from the limited information is getting people＇s attention and solving this problem is well known as matrix completion．For the pure or nearly pure quantum state（ie．low entropy state）in a Hilbert space，the density matrix is low－rank and has trace 1．This paper is concerned with applying matrix completion theory to the unknown density matrix recovery which is from Pauli measurements．The singular value thresholding（SVT）algorithm was utilized to numerical simulation by Matlab software programs．And its soft－thresholding rule was used to singular values of the unknown state density matrix．The threshold iteration was conducted by SVT algorithm through computer programming until a stopping criteria was reached，which could greatly improve the run rate．We took the density matrix from Pauli measurements for example because of the convenience on getting the tensor product structure based on Pauli matrices in experiment．The effect of matrix reconstruction was studied in the case of sampling a small number of entries from the matrix．We conclude that the density matrix can be reconstructed successfully by studying the aspects of reconstruction error，run－time and sampling rate．

matrix completion；density matrix；low－rank；quantum state tomography

O413.1

A

10.3969/j.issn.1674-2869.2015.02.016

1674-2869（2015）02-0072-05

本文編輯：龔曉寧

2014－11－24

太原工業(yè)學(xué)院院級(jí)青年科學(xué)基金（2014LQ05）

韋仙（1988－），女，山西晉城人，助理實(shí)驗(yàn)師，碩士.研究方向：理論物理.