Matrix Multiplicative Weight（3）

本篇主要介紹最近在看的Matrix Multiplicative Weight Algorithm。承接上篇，本篇將介紹該演算法用quantum的SDP solver。以下是主要參考文獻

Introduction to Semidefinite Programming?

ocw.mit.edu

Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning?

arxiv.org

整個quantum SDP演算法可以視為量子版本MMWA來解決SDP問題，其中quadratic的加速主要源於quantum Gibbs Samplers。本文介紹的是基於zero-sum game framework的MMWA演算法來解決SDP問題。

Semidefinite Programming

Semidefinite Programming是一類優化問題，如：

$[egin{array}{l} min { m{ }}C ullet X\ s.t.{ m{ }}{A_i} ullet X = {b_i}{ m{ }},i = 1,...,m\ Xsucceq0 end{array}\ ag{1}]$

其中為半正定矩陣， $C,Xin R^{n imes n}$ ， $C ullet X=sum_{i,j}^{n}{C_{ij}X_{ij}}=Tr(C^{T}X)in R$ 。

SDP的feasibility problem

給定近似解的誤差，約束條件及Hermitian矩陣 ,令凸集 $S_varepsilon={Xin R^{n imes n}: Xsucceq 0,Tr(X)leq R}$ 其中的使得：
$[egin{array}{c} Trleft( {{A_i}X} ight) le {a_i} + varepsilon \ Xsucceq0\ Trleft( X ight) = 1 end{array}\ ag{2}]$ 如果，則輸出無可行解。如果，則輸出可行解

之所以考慮Approximate Feasibility Problem，基於以下考慮：

1。任何一般的SDP問題，都可以不斷的去試並收縮可行解，最後的得到近似解。
例如： $Tr(C^{T}X)in[-1,1]$ ，要 $[max { m{ }}Tr({C^T}X)]$ ，可將其轉換為求解不等式 $Tr({C^T}X)geq a_0$ ，然後不斷試，然後可通過二分查找（）快速找到 $Tr({C^T}X)geq a_0$ 最大的可行解。2。任何都可以轉化成。例如：

對於所有constraint，都除上常數，則，，然後
$[widetilde X = left[ {egin{array}{*{20}{c}} X&0\ 0&w end{array}} ight]\]$ ，如果令。

解決Approximate Feasibility Problem可通過將其視為zero-sum game，並使用MMWA演算法來解決。

quantum Oracle
輸入密度矩陣（ , ），對於條件約束 ,如果 $Trleft( {{A_i}X} ight) le {a_i} + varepsilon$ 不成立，則輸出。否則均成立則輸出『FEASIBLE』（即為滿足所有條件的一個可行解）。

考慮用2人zero-sum game框架解決該問題：

1。甲的目標是找到一個可行解，乙的目標找出違反的任意一個條件約束。

2。如果原問題可解，則對於甲，一定存在一個可行解使得其滿足所有條件，即乙找不到任何違反的條件約束。此種情況則為zero-sum game的平衡點，並可通過MMWA演算法來近似求得。

MMWA整體框架：

MMWA【1】

Quantum algorithm for SDP

由於量子演算法首先要將經典的數據轉化成量子態再進行處理（Plain model, Quantum input model）

Plain model

1.Oracle 1（Plain Model: ）取出 。令該Oracle為，用於取出矩陣裏的信息，到量子態上。該Oracle僅存第個矩陣的行，第個非零元，則：

$[left| {j,k,l,z} ight angle o left| {j,k,l,z oplus {{left( {{A_j}} ight)}_{k{f^{jk}}left( l ight)}}} ight angle \ ag{3}]$

其中 $[{{f^{jk}}left( l ight)}]$ 為取第個非零元。

2. 估計跡 。在MMWA框架下，除了取出的非零元素外，還需要估計出

估計
假設已知Hermition矩陣以及密度矩陣。並通過sample和Oracle1可分別取得和，並以大於 $frac{2}{3}$ 的幾率以為誤差估計出。

3.製備 $frac{W}{Tr(W)}$ 。整個過程為Gibbs sampling。

假設給定稀疏度為的Hermitian矩陣 $Hin C^{ n imes n}$ ,且。此時可以通過Oracle1以及多個兩比特量子門以 $T_{Gibbs}(s,Gamma,varepsilon)$ 來製備Gibbs $frac{e^{-H}}{Tr(e^{-H})}$ ,誤差為

則以下為Quantum SDP（Plain model）演算法

Quantum Input model

1. Oracle 2.1（Trace model: ）。

令該Oracle為 $O_{Tr}$ ，用於取出 $Tr[A^{+}_j],Tr[A^{-}_j]$ （ $A_j=A^{+}_j-A^{-}_j$ ，因為 $A_j=sum_{i=1}^{n}{lambda_i{f{v}}_i{f{v}}^T_i}$ ， $A^{pm}_j=sum_{i}{left| lambda_i ight|{f{v}}_i{f{v}}^T_i}$ ）

$[{O_{Tr}}left| j ight angle left| 0 ight angle left| 0 ight angle = left| j ight angle left| {Trleft[ {A_j^ + } ight]} ight angle left| {Trleft[ {A_j^ - } ight]} ight angle \ ag{4}]$

Oracle 2.2（preparing model: ）

令該Oracle為，用於製備矩陣 ,該Oracle作用於 $[{{mathbb{C}}^m} otimes left( {{{mathbb{C}}^n} otimes {{mathbb{C}}^n}} ight) otimes left( {{{mathbb{C}}^n} otimes {{mathbb{C}}^n}} ight)]$ ,有

$[Oleft| j ight angle leftlangle j ight| otimes left| 0 ight angle leftlangle 0 ight| otimes left| 0 ight angle leftlangle 0 ight|{O^dag } = left| j ight angle leftlangle j ight| otimes left| {psi _j^ + } ight angle leftlangle {psi _j^ + } ight| otimes left| {psi _j^ - } ight angle leftlangle {psi _j^ - } ight|\ ag{5}]$

其中通過純化 $[left| j ight angle leftlangle j ight| otimes left| {psi _j^ + } ight angle leftlangle {psi _j^ + } ight| otimes left| {psi _j^ - } ight angle leftlangle {psi _j^ - } ight|]$ ，我們可以得到 $frac{A_{j}^{+}}{tr[A_{j}^{+}]}$ 和 $frac{A_{j}^{-}}{tr[A_{j}^{-}]}$

Oracle 2.3（model: ）。

令該Oracle為，用於取條件

$[{O_a}left| j ight angle leftlangle j ight| otimes left| 0 ight angle leftlangle 0 ight|O_a^dag = left| j ight angle leftlangle j ight| otimes left| {{a_j}} ight angle leftlangle {{a_j}} ight|\ ag{6}]$

2. 估計跡。

假設 $[trleft( {A_j^ + } ight) + trleft( {A_j^ - } ight) le B]$ ，令 $S_{tr}(B,varepsilon)$ 和 $T_{tr}(B,varepsilon)$ 分別為使用以上Oracle2.1~2.2製備態的sample complexity和time complexity。則存在一個量子演算法正確地估計或的概率大於。

3.製備 $frac{e^{-K}}{Tr(e^{-K})}$ 。

假設 $K=K^{+}-K^{-},K=sum_{jin S}{c_jA^{pm}_{j}},Ssubseteq[m]$ ，且的秩不大於 $r_{K}$ 。同時假設 $tr[K^{+}]+tr[K^{-}]leq B_{K}$ 。我們可以通過對Oracle2.1~2.2和兩比特門來製備Gibbs態 $ho_{G}=frac{e^{-K}}{Tr(e^{-K})}$ ，其製備的複雜度為 $T_{Gibbs}(r_{K},Phi,B_{K},varepsilon)$