考量閘門重排與提早量測之量子位元最佳重複使用演算法

Abstract

量子位元（qubit）資源限制是當前量子電腦的一項常見瓶頸，不僅限制了執行複雜演算法的能力，也減緩了量子應用的發展。透過在量測後重設量子位元，並將其重新用於後續閘門操作，可以有效降低整體所需的量子位元數量。我們提出一套基於可滿足模理論（SMT）與整數線性規劃（ILP）的最佳化演算法，在最大化量子位元重複使用的同時，也能選擇性地限制電路深度於一個指定上限內。 本方法考慮所有可行的電路重排（circuit rearrangement）以提升最佳性，涵蓋閘門重新排序（gate reordering）與提前量測（eager measurement）等技術。為了解決大型電路的可擴展性問題，我們進一步提出一套子電路提取演算法（subcircuit-extraction-based approach），藉由放寬最佳性保證來進行求解。 實驗結果顯示，相較於現有技術，我們的演算法能顯著減少量子位元使用數與電路深度，而子電路提取演算法的架構則在保有解品質的同時，有效處理了可擴展性的挑戰。

Qubit capacity is a common bottleneck in quantum computers, limiting the ability to run complex algorithms and slowing the advancements in quantum computing applications. Reusing qubits by resetting them after measuring and repurposing them for subsequent gate operations offers an effective strategy to reduce the overall qubit requirements. Based on Satisfiability Modulo Theories (SMT) and Integer Linear Programming (ILP), we present an optimal algorithm that maximizes qubit reuse while optionally constraining the circuit depth to a specified upper bound. Our approach considers all feasible circuit rearrangements to enhance optimality, including gate reordering and eager measurement. We further propose a subcircuit-extraction-based approach to scale for large circuits by relaxing the optimality guarantee. Experimental results show that our exact method substantially decreases both the qubit count and the circuit depth compared to the current state of the art, while the subcircuit-extraction-based approach effectively addresses scalability issues with maintained solution quality.