首頁>科技>產業動態
量子計算機能更好解決組合優化問題
旅行推銷員問題是指旅行者要通過最短的路線拜訪多個城市，然后返回起點。圖片來源：HZB
旅行推銷員問題是一個經典的數學問題，也是一個組合優化問題。德國柏林弗雷大學和亥姆霍茲柏林能源與材料研究中心（HZB）科學家開展的一項新研究證明，量子計算機在解決旅行推銷員問題上，相較于傳統方法，展現出了更高的效率和更快的速度。研究論文發表于最新一期《科學進展》雜志。
旅行推銷員問題是要尋找一條能讓旅行者拜訪多個城市并返回出發點的最短路徑。雖然問題聽起來簡單，但隨著城市數量的增加，以及由此導致的計算時間的激增，其變得越來越復雜。旅行推銷員問題代表了一類具有巨大經濟意義的優化問題，涉及鐵路網、物流、資源優化等多個領域。
在最新研究中，HZB理論物理學家延斯·艾澤特教授領導的團隊，使用純分析方法來評估量子計算機如何解決旅行推銷員等組合優化問題。他們發現，可使用密碼學領域的秀爾算法來解決這些優化問題。這意味著，計算時間不再隨著城市數量的增加而呈指數級“爆炸”，而只是以多項式的形式增加。結果顯示，以這種方式獲得的解在質量上比使用傳統算法的近似解好得多。
編輯：馬嘉悅
