中大新聞網(wǎng)訊（通訊員李冠中、吳曉鴻）近日，來(lái)自中山大學(xué)計(jì)算機(jī)學(xué)院量子計(jì)算與軟件研究所的研究成果論文“Recovering the Original Simplicity: Succinct and Deterministic Quantum Algorithm for the Welded Tree Problem（返璞歸真：求解焊接樹(shù)問(wèn)題的簡(jiǎn)潔與確定性量子算法）”被國(guó)際頂級(jí)學(xué)術(shù)會(huì)議SODA錄用。中山大學(xué)計(jì)算機(jī)學(xué)院為該論文的唯一署名單位，論文作者按字母序?yàn)椋篏uanzhong Li(李冠中)、Lvzhou Li(李綠周)、Jingquan Luo(羅鏡泉)，其中李冠中和羅鏡泉分別為李綠周教授團(tuán)隊(duì)的博士研究生和碩士研究生。
該論文重新審視了在量子算法領(lǐng)域備受關(guān)注的焊接樹(shù)問(wèn)題，基于硬幣量子游走模型設(shè)計(jì)了求解該問(wèn)題的具有指數(shù)加速優(yōu)勢(shì)的簡(jiǎn)潔確定性量子算法。這不僅打破了硬幣量子游走只能實(shí)現(xiàn)比經(jīng)典算法平方加速的刻板印象，而且為簡(jiǎn)化現(xiàn)有的基于量子游走的算法提供了新思路。據(jù)統(tǒng)計(jì)，這是SODA歷史上首篇署名單位完全來(lái)自中國(guó)大陸研究機(jī)構(gòu)的專(zhuān)注于量子算法的論文。
焊接樹(shù)問(wèn)題是少數(shù)幾個(gè)基于量子游走展現(xiàn)出量子指數(shù)加速優(yōu)勢(shì)的問(wèn)題。形象地說(shuō)，該問(wèn)題是要從迷宮入口找到出口，每走一步只能探索周邊有路徑相連的位置。這里的“迷宮”是兩棵深度為n的完全二叉樹(shù)，它們水平相對(duì)放置，中間的葉子左右隨機(jī)交替“焊接”起來(lái)形成一個(gè)回路，如下圖中虛線(xiàn)所示。假設(shè)“迷宮”的信息存放在一張鄰接表中。那么，在“迷宮”中每走一步，都需要訪(fǎng)問(wèn)一次鄰接表以獲取當(dāng)前位置的相鄰信息。焊接樹(shù)問(wèn)題即要求盡可能少地訪(fǎng)問(wèn)鄰接表從入口找到出口，其中訪(fǎng)問(wèn)鄰接表的次數(shù)稱(chēng)為查詢(xún)復(fù)雜度。可以證明針對(duì)該問(wèn)題的任何經(jīng)典算法的查詢(xún)復(fù)雜度都是n的指數(shù)量級(jí)，即為 Ω(2n)。
深度n=2的焊接樹(shù)
針對(duì)焊接樹(shù)問(wèn)題，上述論文基于簡(jiǎn)單直觀(guān)的硬幣量子游走模型設(shè)計(jì)了簡(jiǎn)潔而高效的確定性量子算法。該工作價(jià)值體現(xiàn)在以下幾點(diǎn)：(1)與Jeffery 和 Zur（STOC'2023）的算法相比，所得的量子算法相當(dāng)簡(jiǎn)單，這不僅打破了硬幣量子游走只能實(shí)現(xiàn)比經(jīng)典算法二次方加速的刻板印象，而且還展示了最簡(jiǎn)量子游走模型的威力；(2) 所得的量子算法理論上可以百分之成功，而已有量子算法不可避免地具有失敗概率。這也可能改變?nèi)藗冞@樣的看法：由于量子力學(xué)本質(zhì)上是隨機(jī)的，不可能存在具有指數(shù)加速的確定性量子算法求解焊接樹(shù)問(wèn)題；（3）文中展現(xiàn)的簡(jiǎn)潔的算法思路具有很強(qiáng)的啟發(fā)意義。如同一位審稿人所說(shuō)：“這篇論文可能會(huì)開(kāi)創(chuàng)一條新的研究路線(xiàn)，簡(jiǎn)化現(xiàn)有基于量子游走的算法，并提高它們的效率”。
據(jù)悉，SODA（ACM-SIAM Symposium of Discrete Algorithms）是算法領(lǐng)域的國(guó)際頂級(jí)會(huì)議，主要關(guān)注解決離散問(wèn)題的高效算法和相關(guān)數(shù)據(jù)結(jié)構(gòu)的研究，與 STOC、FOCS 一起被公認(rèn)為理論計(jì)算機(jī)科學(xué)的三大頂級(jí)學(xué)術(shù)會(huì)議，在計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望。
文稿終審：計(jì)算機(jī)學(xué)院 馬嘯
