近日(rì)，四川省計算機研究院研究科(kē)學家李乾共同撰寫的論文《Quantum Lovasz Local Lemma: Shearer’s Bound is Tight》被計(jì)算機(jī)領域最頂級國(guó)際會議(yì)之一：第51屆ACM計(jì)算理(lǐ)論年(nián)會（STOC 2019，51th Annual Symposium on the Theory of Computing）錄用。STOC被公認是計(jì)算機(jī)科(kē)學領域難度最高的國(guó)際會議(yì)之一，在整個計(jì)算機(jī)科(kē)學領域享有崇高的聲望。據不完全統計(jì)，這是華南(nán)地區單位第一次被該會議(yì)錄用論文。

量子洛瓦茲局部引理(lǐ)是研究量子計(jì)算複雜性領域中的核心問(wèn)題：量子可(kě)滿足性問(wèn)題的重要工(gōng)具。本論文給了該引理(lǐ)适用範圍的一個充分(fēn)必要的數學刻畫(huà)，從(cóng)而證實了Sattath等人(rén)在美國(guó)科(kē)學院院刊（PNAS）上提出的猜想，這也意味着經典統計(jì)物理(lǐ)中的晶格氣模型配分(fēn)函數完整刻畫(huà)了量子物理(lǐ)中幾乎所有作(zuò)用在足夠大(dà)的qudits上的哈密頓量的可(kě)滿足性。此外，本論文還(hái)證明了在一般情況下，對易洛瓦茲局部引理(lǐ)并不等價于量子洛瓦茲局部引理(lǐ)，并給出了定量分(fēn)析。這些結果有助于深入理(lǐ)解量子可(kě)滿足性問(wèn)題以及非對易性在量子現象中所起的作(zuò)用。

四川省計算機研究院是深圳大(dà)學獨資舉辦的“其他(tā)組織利用國(guó)有資産舉辦的事(shì)業單位”，由英國(guó)皇家學會院士擔任首席科(kē)學家，中國(guó)科(kē)學院陳國(guó)良院士任名譽院長，深圳大(dà)學毛睿教授任執行院長。