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是一類優化問題，如：

其中為半正定矩陣，，。

SDP的feasibility problem

給定近似解的誤差，約束條件及Hermitian矩陣 ,令凸集其中的使得：
如果，則輸出無可行解。如果，則輸出可行解

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

1。任何一般的SDP問題，都可以不斷的去試並收縮可行解，最後的得到近似解。
例如：，要，可將其轉換為求解不等式，然後不斷試，然後可通過二分查找（）快速找到最大的可行解。2。任何都可以轉化成。例如：

對於所有constraint，都除上常數，則，，然後
，如果令。

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

quantum Oracle
輸入密度矩陣（ , ），對於條件約束 ,如果不成立，則輸出。否則均成立則輸出『FEASIBLE』（即為滿足所有條件的一個可行解）。

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

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

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

MMWA整體框架：

MMWA【1】

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

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

其中為取第個非零元。

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

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

3.製備 。整個過程為Gibbs sampling。

假設給定稀疏度為的Hermitian矩陣 ,且。此時可以通過Oracle1以及多個兩比特量子門以來製備Gibbs ,誤差為

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

1. Oracle 2.1（Trace model: ）。

令該Oracle為，用於取出（，因為，）

Oracle 2.2（preparing model: ）

令該Oracle為，用於製備矩陣 ,該Oracle作用於 ,有

其中通過純化，我們可以得到和

Oracle 2.3（model: ）。

令該Oracle為，用於取條件

2. 估計跡。

假設，令和分別為使用以上Oracle2.1~2.2製備態的sample complexity和time complexity。則存在一個量子演算法正確地估計或的概率大於。

3.製備 。

假設，且的秩不大於。同時假設。我們可以通過對Oracle2.1~2.2和兩比特門來製備Gibbs態，其製備的複雜度為

【1】Satyen Kale. Efficient algorithms using the multiplicative weights update method. Princeton University, 2007.