【量子計算】Qubit Mapping and Routing:近5年學術研究的總覽

量子計算是具有巨大潛力的快速發展領域,它能夠解決傳統計算機無法應對的問題。然而,實現量子計算的全部潛力需要克服多項技術挑戰,其中之一是Qubit Mapping和Routing (QMR)的問題。Qubit Mapping和Routing是指將量子演算法從Logical Qubits對應到實體量子電腦上的Physical Qubits的方法,並找到一種可行的2-Qubit Gate Sequence。在這個過程中,常常需要添加Swap Gate來連接原本不相鄰的Qubits以執行2-Qubit Gate。Qubits非常敏感且容易出錯,因此在Mapping和Routing的過程中,需要盡量減少所需添加的Swap Gate的數量。QMR問題是實際量子計算中的關鍵挑戰,解決這個問題將對推動量子計算技術的發展產生重大影響。

Qubit Mapping and Routing (QMR)

簡短描述一下QMR這個問題

  • 在量子計算中,2-Qubit Gate只能在相鄰的Physical Qubits上被執行。
  • 如果在程式中的2-Qubit Gate的兩個Qubits不相鄰,Swap Gates會被添加進入此量子程式中始得這兩Qubit相鄰後執行2-Qubit Gate。
  • 解決QMR問題的目標是要加入Swap Gate讓所有2-Qubit Gate都可被執行且希望加入最少的Swap Gate數量以降低量子系統的Noise。

QMR 的研究趨勢

QMR近期的研究趨勢

我們從近期發表的學術論文中可以看到整體趨勢由一開始只能解決5-10 Qubits數量較小的量子程式後來加入了考慮每個Qubit本身錯誤率的QMR方法。然後開始有根據不同量子硬體而有不同的解決方法,逐步到達考慮大型量子程式以及針對特殊程式而有的優化方式。這是大致近幾年針對此問題研究方向的變化。以下將針對這些研究主題進行逐一簡短的討論。

Exact Algorithm & Heuristic Algorithm(https://arxiv.org/abs/1907.02686

在2018年,由IBM Research Tokoy提出使用Dynamic Programming (DP)找出最佳的Qubit Mapping以及Routing Path。這個方法雖然能找到最佳解,但由於時間複雜度過高,以致於無法擴張至大型的量子程式使用。在這方法中僅討論到約6 Qubits。而在這篇論文中也有提到使用Heuristic的方式搭配Look-Ahead Window來找一個好的QMR Solution。使用Shortest Path作為Cost Function。編譯一個16 Qubits的程式大約需要800秒。很明顯比DP的方式快很多。

SABRE (https://arxiv.org/abs/1809.02573

這個方法在2019年的ASPLOS會議上發表。同樣使用Heuristic algorithm 和 Look-Ahead Window,但在Cost Function上只需要能把Qubits往目標Qubits移動到更近的地方即可。並且提出使用Reverse Circuit來返回得到初始Qubit Mapping的方式。此方式可編譯20 Qubit的程式僅需1秒鐘。

考量Noise的Qubit Mapping (https://arxiv.org/abs/1901.11054

這個方法一樣是在2019 ASPLOS會議上發表。考慮每個Qubit和Quantum Gates在每天Error Rate都不同的情況下,挑選當下Error Rate最低的Qubit以及Gates來做Mapping & Routing。使用SMT Solver來解這個最佳化的問題。由於是使用SMT Solver,因此這個方法的擴展性不佳。編譯一個32 Qubits的程式會需要幾天的時間。

Variation-Aware Qubit Movement(https://arxiv.org/abs/1805.10224

同樣是在2019 ASPLOS會議上發表。根據每一個2-Qubit Gate不同的成功率可以畫出一個Weighted Connectivity Graph,然後使用Dijkstra’s Greedy Algorithm來找出最低Error Rate的Path來進行Swap Gate的添加以降低整個程式的錯誤率。

Frequency-Aware Compilation (https://arxiv.org/abs/2008.09503

此方法是在2020年MICRO會議上發表。此方法是Technology-Aware的類別針對Superconducting transmon tunable qubits來降低Cross Talk(互相干擾)以提升整個量子程式的成功率。Cross Talk通常指的是在電子、通訊或量子系統中,不同元件之間的相互干擾。當不同元件之間的訊號在共享線路或空間中傳輸時,它們可能會互相影響,從而導致干擾。在量子系統中,Cross Talk通常是指不同量子位元之間的相互作用,導致干擾或錯誤。Cross Talk是一個重要的問題,因為它可能會對系統的準確性和穩定性產生負面影響,並且需要在系統的設計和操作中加以考慮和管理。這個方法使用Graph Coloring的方式來產生Cross Talk Graph並降低Cross Talk Error。

針對Trapped-Ion QCCD架構的QMR (https://arxiv.org/abs/2004.04706

此方法於2020年的ISCA會議上提出。針對Trapped-ion quantum charge-coupled device (QCCD)的架構提出的方式。在此論文中開始討論針對78 Qubits的量子程式進行編譯。

QMR for Trapped-Ion Linear Shuttling (https://arxiv.org/abs/2010.15876

此方法是我在2021年的HPCA會議上提出。提出Trapped-Ion Linear Shuttling的架構並且考慮在此架構下,如何最佳化QMR。利用Linear Shuttling的特性產生Opposing Swaps以減少所需添加的Swap Gate。此流程中應用了SABRE以及Heuristic和Greedy的方法混合來得到較好的結果。可在50秒左右完成78 Qubits程式的Compilation。

Hierarchical Synthesis for Large-Scale Circuits (https://ieeexplore.ieee.org/document/9743148)

此方法是我2021年在ICRC會議上所發表。使用Quantum Synthesis來最佳化一個量子程式。Quantum Synthesis指的是透過分解相對應的Matrix來產生一組新的Quantum Circuit但使其對應到的Matrix與原本相同。而新產生的Quantum Circuit所需要的2-Qubit Gates比原本的程式所需還要少,藉此降低整體程式的Noise以提升成功率。為了讓此方法可實際應用在較大的量子程式上,這個方法使用了Circuit Partition的技巧將壹個大電路分成很多小的Block,分別對每個小的Block進行最佳化的Synthesis後,再將結果合併成為最終的量子程式。此方法不僅是進行QMR,並進一步最佳化。

針對10000+ Qubit進行QMR(https://arxiv.org/abs/2210.01306

在2022年有些文章開始討論針對更大的量子程式進行編譯的方式。使用Dual-Source Dijkstra來最佳化QMR問題。編譯10000 Qubit的QFT程式約需要五個小時。

針對QAOA的QMR(https://ieeexplore.ieee.org/document/9251960

這個方法在2020年的MICRO會議上發表。針對QAOA的問題,由於程式中的2-Qubit Gates彼此具有可交換性(Commutative)。因此,可以善用此特性更進一步的最佳化QMR。

針對2-Local Qubit Hamiltonian Simulation (https://arxiv.org/abs/2108.02099

在2022年的ISCA上,這篇文章再次擴張此方法到2-Local Qubit Hamiltonian Simulation上。主要是使用Heuristic的方式來解此問題。

總結

這篇文章概述了近年來針對QMR問題的學術研究,並簡述了現有解決方案的特點(如下圖所示)。與此同時,我們正在見證Reinforcement Learning和NN-Assisted等技術的出現在解決QMR問題上。在當前AI/ML蓬勃發展的時代,我們有理由相信,很快就會有更多使用Pre-Trained Model來最佳化QMR的方法出現,為我們帶來更高效、更穩定的量子計算體驗。

X. Ryan
X. Ryan

Hello!我是一個在矽谷工作,有軟體工程背景的量子計算科學家。這裡分享的內容主要是把平常研究開發時所用的小工具以及看過的東西記錄下來,同時也分享一些日常生活瑣事。

文章: 49