2874
0
2026-03-29
2026-03-29
1. 研究了max-cut問(wèn)題的圖結(jié)構(gòu) 對(duì) QAOA參數(shù)空間的能量景觀 的影響。簡(jiǎn)而言之：當(dāng)p=1，每一條邊都會(huì)在能量景觀的\gamma截面中對(duì)應(yīng)一個(gè)簡(jiǎn)諧波，頻率正比于邊的權(quán)重，振幅由局部的圖結(jié)構(gòu)（在公式中表現(xiàn)為鄰邊的余弦乘積）決定。當(dāng)某一條邊權(quán)重過(guò)大，且鄰邊較少時(shí)，會(huì)產(chǎn)生一個(gè)振幅頻率都大的波，將整個(gè)能量景觀切割為很多塊，導(dǎo)致優(yōu)化算法無(wú)法跳出單獨(dú)一塊區(qū)域，搜索到全局的最優(yōu)點(diǎn)。這解釋了我之前的實(shí)驗(yàn)中，某些圖表現(xiàn)很差的原因。
2. 受1啟發(fā)，我隨機(jī)生成了一些圖，構(gòu)建p=1時(shí)的QAOA算子，對(duì)算子做傅里葉分析，篩選出低頻波振幅遠(yuǎn)大于高頻波的圖。我認(rèn)為對(duì)這些圖運(yùn)行QAOA算法時(shí)會(huì)更容易得到較好的結(jié)果。但暫時(shí)無(wú)法驗(yàn)證是否正確。
3. 在之前的周報(bào)中我提到，在QAOA中使用貝葉斯優(yōu)化能相比原始優(yōu)化方法更好，因?yàn)樨惾~斯優(yōu)化能探索多個(gè)初始點(diǎn)，利用更多信息。但是這周我嘗試將 貝葉斯優(yōu)化 替換為 差分進(jìn)化(differential evolution) 算法。實(shí)驗(yàn)結(jié)果，期望割值由15~16提高到17~18，在理想條件（無(wú)噪聲+StateVector精確模擬+更多次迭代）下能達(dá)到21, 更加逼近理論最大割值24. 并且測(cè)得最大割方案的概率由0.07上升至0.14（理想0.33）。差分進(jìn)化效果遠(yuǎn)好于貝葉斯優(yōu)化。隨后我找到Restricted Global Optimization for QAOA這篇文章，這篇文章認(rèn)為qaoa必須采用“全局優(yōu)化”而不是“局部?jī)?yōu)化”，一定程度解釋了 差分進(jìn)化 為什么相比 貝葉斯優(yōu)化 更適合QAOA算法。貝葉斯優(yōu)化雖然能利用全局信息，但是仍然不能跳出局部最小值，但是差分進(jìn)化有跳出機(jī)制。
4. 上一點(diǎn)中 差分進(jìn)化 在理想條件中的效果，已經(jīng)符合預(yù)期。但是在限定40次迭代次數(shù)的條件下還是和理想條件差很多，下一周我會(huì)微調(diào)差分進(jìn)化的超參，希望能加快優(yōu)化速度，使有限迭代次數(shù)的QAOA盡量接近理想條件。我在1中提到能量景觀由頻率為邊權(quán)重的簡(jiǎn)諧波構(gòu)成，那么直觀上，如果我希望優(yōu)化算法從一個(gè)谷底直接跳到另一個(gè)谷底，\gamma參數(shù)的跳躍距離應(yīng)該與簡(jiǎn)諧波的波長(zhǎng)有關(guān)，這是可能的優(yōu)化方向。
* 這次的周報(bào)寫的很長(zhǎng)，因?yàn)槲遗既话l(fā)現(xiàn)deepseek從學(xué)者網(wǎng)上爬到了我之前的周報(bào)，然后又把這個(gè)內(nèi)容當(dāng)作論據(jù)告訴我。我寫的詳細(xì)一點(diǎn)，或許會(huì)有人從中得到幫助。
