容錯量子電路中基於矩陣之小角度旋轉閘最佳化流程的輔助量子位元最小化

Abstract

在容錯量子計算中，T-count 最小化是降低 Clifford+T 電路資源成本的核心目標，因為 T 閘通常需要仰賴 magic-state distillation 等昂貴的容錯實作。先進的 T-count 最佳化流程（如 FastTODD）常透過 Hadamard gadgetization，將內部 H 閘換成輔助量子位元與對應的 post-measurement control（PMC），使非 Clifford 旋轉得以合併為統一的對角 Pauli-rotation（PR）tableau，從而取得更強的 T-count 縮減。以統一對角旋轉流程為例，平均可再降低約 22% 的 T-count，但每減少一個 T 閘約需付出 1.26 個額外輔助量子位元（A/T）。既有 degadgetization 與 ZX 相關方法雖能降低部分輔助量子位元開銷，僅追求最小 T-count 仍無法保證最終電路具有較低的輔助量子位元寬度。 本論文關注積極進行 T-count 最佳化後仍殘留的輔助量子位元開銷，並指出兩個關鍵困難。第一，即使不同的 T 最佳化 PR 表示具有相同的最小 T-count，它們在欄位重排、排程與 degadgetization 之後，仍可能對應截然不同的峰值輔助量子位元寬度；因此 T-count 最佳化結果並非唯一，電路結構差異會直接影響輔助量子位元的可回收性與同時使用量。第二，先前輔助量子位元減量方法常將 PMC 視為一般量子閘處理，但 PMC 由量測結果的古典狀態所控制；在 commutation 過程中，單量子位元 X 修正可能被改寫為具有嚴格拓樸依賴的多量子位元古典修正。若忽略這些古典狀態限制，某些看似可行的 degadgetization 便可能無法保持原本的計算語意。 為解決上述問題，本論文提出一個結構感知的 T–輔助量子位元共最佳化框架。首先形式化 PMC 的量測順序、經對角 PR 欄位的 commutation，以及還原為單一 X 修正以進行 degadgetization 的條件，確保後續輔助量子位元減量保持計算正確性。接著，在固定的最小 T-count 表示下，擷取 gadget 與 PR 欄位的阻擋限制，並以 SMT/SAT 搜尋能最小化峰值同時作用輔助量子位元數量的欄位排程（sat_reorder）。再者，以 FastTODD 的 tie-search 在前處理組態與同分合併路徑所產生的等價 T 最佳 PR 結構間搜尋，並以 SMT 寬度評估各候選，於維持最小 T-count 的前提下尋找更低的輔助量子位元開銷（必要時亦可進一步改善 T-count）。實驗顯示，相對於統一 T 最佳化基準（平均 A/T 約 1.26），SMT 重排可將平均 A/T 降至約 0.97，再經 tie-search 可進一步降至約 0.48。上述流程已實作於 Qsyn 量子電路編譯器，可作為端對端編譯階段使用。

In fault-tolerant quantum computing, T-count minimization is a central objective for reducing the resource cost of Clifford+T circuits, because T gates typically require expensive fault-tolerant implementations such as magic-state distillation. State-of-the-art T-count optimization flows, including FastTODD, often apply Hadamard gadgetization: each internal H is replaced by an ancilla and a post-measurement control (PMC), so that non-Clifford rotations can be collected into a unified diagonal Pauli-rotation (PR) tableau and optimized more aggressively. In the unified diagonal-rotation flow, this yields about a 22% further T-count reduction on average, but at an A/T cost of roughly 1.26 added ancilla qubits per reduced T gate. Although prior degadgetization and ZX-based methods can reduce some of this overhead, minimizing T-count alone does not guarantee a low-ancilla circuit. This thesis studies the ancilla overhead that remains after aggressive T-count optimization and identifies two obstacles. First, equivalent T-optimal PR representations with the same minimized T-count can induce substantially different peak ancilla widths after column reordering, scheduling, and degadgetization; T-optimization is therefore not unique, and structural differences directly affect ancilla reclaimability and simultaneous usage. Second, previous ancilla-reduction methods often treat PMCs as ordinary gates, even though PMCs are controlled by classical measurement outcomes. During commutation, an initial single-qubit X correction can be rewritten into a multi-qubit classical correction with strict topological dependencies. Ignoring these classical-state constraints can make a degadgetization step appear valid even when it does not preserve the intended computation. To address these issues, this thesis proposes a structure-aware T–Ancilla co-optimization framework. We first formalize PMC measurement order, commutation through diagonal PR columns, and restoration to a single-X correction as the precondition for degadgetization, so that subsequent ancilla reduction remains classically correct. Given a fixed minimized-T representation, we then extract gadget–column blocking constraints and encode them in an SMT/SAT formulation (sat_reorder) that minimizes the peak number of simultaneously active ancillae. Finally, FastTODD tie-search explores equivalent T-optimal PR structures from preprocessing configurations and tied merge paths, scoring each candidate by T-count and SMT width to seek lower ancilla overhead under a minimized T-count (and occasionally a still smaller T-count). Experiments show that, relative to the unified T-optimization baseline (average A/T about 1.26), SMT reordering reduces the average A/T to about 0.97, and tie-search further lowers it to about 0.48. The full pipeline is implemented in the Qsyn quantum circuit compiler as an end-to-end compilation stage.