針對拓樸量子電路之橋技術壓縮演算法

A Bridge-based Compression Algorithm for Topological Quantum Circuits

徐晨皓(Chen-Hao Hsu)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202100494

摘要

拓樸量子誤差校正（topological quantum error correction）架構是現今實現大規模可靠量子計算最具展望性的技術。拓樸量子誤差校正電路可以通過三維立體圖建模，而其實現所需之資源可抽象為其時空體積（space-time volume）。要以合理的實體量子位元（qubit）數量及合理的計算時間，來計算大規模的實際問題，是極具挑戰性的。因此，最小化拓樸量子誤差校正電路之時空體積成為關鍵的問題。在文獻上，人工應用橋壓縮（bridge compression）於拓樸量子誤差校正電路可以極大程度的壓縮體積。我們期望開發用於拓樸量子誤差校正電路之自動壓縮技術，以實現低成本的大規模量子計算。
在本篇論文中，我們提出第一個能在拓樸量子誤差校正電路自動進行橋壓縮的方法。我們提出的演算法主要包括四個階段：預處理階段、迭代橋接階段、模塊擺置階段、副缺陷（dual-defect）信號連線階段。在預處理階段，藉由斷開副缺陷環，輸入的量子電路會被分解為模塊。而在迭代橋接階段，會盡可能多的在副缺陷環間加橋。接下來，在滿足量測時間順序的限制下，將所有模塊被放置進二點五維（2.5-dimensional）的結構中。最後，副缺陷信號通過應用A星搜索演算法進行連接以重建環。實驗結果顯示，與最先進的方法相比，我們提出的演算法可以平均將時空體積減少83%。

關鍵字

量子計算 ； 拓樸量子誤差校正 ； 辮結量子電路 ； 橋壓縮 ； 時空體積最小化

並列摘要

The topological quantum error correction (TQEC) scheme is promising
for scalable and reliable quantum computing. A TQEC circuit can be modeled by a three-dimensional diagram, and the implementation resource of a TQEC circuit is abstracted to its space-time volume. Implementing a quantum algorithm with a reasonable physical qubit number and reasonable computation time is challenging for large-scale practical problems. Therefore, minimizing the space-time volume of a TQEC circuit becomes a crucial issue. Previous work shows that bridge compression can greatly compress TQEC circuits, but it was performed only manually. It is desirable to develop automated compression techniques for TQEC circuits to achieve low-overhead, large-scale quantum computations.
In this thesis, we present the first work that can automatically perform bridge compression on TQEC circuits. Our proposed algorithm mainly consists of four stages:
the preprocessing stage, the iterative bridging stage, the module placement stage, and the dual-defect net routing stage. In the preprocessing stage, the input quantum circuit is decomposed into a set of modules. Then, the iterative bridging is performed to bridge dual-defect loops as much as possible. Next, all modules are placed in the 2.5-dimensional (2.5D) structure while considering time-ordered measurement constraints. Finally, all dual-defect nets are routed by applying the A* search algorithm with the negotiation-based rip-up and reroute technique. Compared with the state-of-the-art method, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 83%.

並列關鍵字

Quantum Computing ； Topological Quantum Error Correction ； Braided Quantum Circuit ； Bridge Compression ； Space-time Volume Minimization

參考文獻

[1] The Boost C++ libraries. [Online]. Available: https://www.boost.org/users/history/version_1_72_0

[2] The LEMON graph library. [Online]. Available: https://lemon.cs.elte.hu/trac/lemon

[3] N. A. B. Adnan and S. Yamashita, “Logical qubit layout problem for ICM representation,” Journal of Information Processing, vol. 26, pp. 20–28, January 2018.

[4] M. AlFailakawi, I. Ahmad, L. AlTerkawi, and S. Hamdan, “Depth optimization for topological quantum circuits,” Quantum Information Processing, vol. 14, no. 2, pp. 447–463, February 2015.

[5] K. Asai and S. Yamashita, “Compaction of topological quantum circuits by modularization,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 102, no. 4, pp. 624–632, April 2019.