旅行推銷員問題是指旅行者要通過最短的路線拜訪多個城市，然后返回起點(diǎn)。圖片來源：HZB

旅行推銷員問題是一個經(jīng)典的數(shù)學(xué)問題，也是一個組合優(yōu)化問題。德國柏林弗雷大學(xué)和亥姆霍茲柏林能源與材料研究中心（HZB）科學(xué)家開展的一項新研究證明，量子計算機(jī)在解決旅行推銷員問題上，相較于傳統(tǒng)方法，展現(xiàn)出了更高的效率和更快的速度。研究論文發(fā)表于最新一期《科學(xué)進(jìn)展》雜志。

旅行推銷員問題是要尋找一條能讓旅行者拜訪多個城市并返回出發(fā)點(diǎn)的最短路徑。雖然問題聽起來簡單，但隨著城市數(shù)量的增加，以及由此導(dǎo)致的計算時間的激增，其變得越來越復(fù)雜。旅行推銷員問題代表了一類具有巨大經(jīng)濟(jì)意義的優(yōu)化問題，涉及鐵路網(wǎng)、物流、資源優(yōu)化等多個領(lǐng)域。

在最新研究中，HZB理論物理學(xué)家延斯·艾澤特教授領(lǐng)導(dǎo)的團(tuán)隊，使用純分析方法來評估量子計算機(jī)如何解決旅行推銷員等組合優(yōu)化問題。他們發(fā)現(xiàn)，可使用密碼學(xué)領(lǐng)域的秀爾算法來解決這些優(yōu)化問題。這意味著，計算時間不再隨著城市數(shù)量的增加而呈指數(shù)級“爆炸”，而只是以多項式的形式增加。結(jié)果顯示，以這種方式獲得的解在質(zhì)量上比使用傳統(tǒng)算法的近似解好得多。