透過與邏輯閘降減導向技術映射與 T 最佳化可逆卵石遊戲技術改進量子預言機合成

Abstract

量子預言機在量子演算法與密碼學中扮演重要角色。傳統的合成流程會先將經典電路轉換為 XOR-AND 圖（XAG），再將該 XAG 編譯成量子預言機。然而，現有的 XAG 合成流程往往忽略較高輸入扇入的邏輯元件，導致生成的 XAG 含有過多的與邏輯閘，進而使量子預言機需要更高資源實現。 我們提出一個新的量子預言機合成流程，在技術映射中引入 NPN 類別以降低 XAG 中 AND 閘的數量。此外，我們針對可逆卵石遊戲中的與邏輯閘鏈運算提出一種降低 T-count 為目標的最佳化演算法。最後，我們針對一個新的最佳化目標–時空體積提出一個啟發式演算法。 實驗結果顯示，與典型合成流程相比，時空體積平均降低 45.6%。此外，透過在映射過程中允許更豐富的邏輯元件（例如 AND3 與 AIA 閘），我們在 T-count上平均可達到 1% 的改善。總體而言，我們所提出的流程能以更低的資源成本完成量子預言機合成。

Quantum oracles play an important role in quantum algorithms and cryptography. Traditional synthesis pipelines first transform a classical circuit into an Xor-And graph (XAG) and then compile the XAG into a quantum oracle. However, existing XAG-based synthesis flows often overlook higher-fanin logic components, which can lead to XAGs with excessive AND gates and, consequently, quantum oracles with higher resource requirements. We propose a quantum oracle synthesis flow that incorporates NPN classes into technology mapping to reduce the number of AND gates in the mapped XAG. We also introduce a T-optimized algorithm that reduces the cost of AND-chain recomputation within reversible pebbling game. In addition, we propose a heuristic method for optimizing a resource metric called space--time volume. Experimental results show an average 45.6% reduction in space-time volume compared with the typical oracle synthesis flow. Moreover, by enabling richer logic components, such as AND3 and AIA gates, during mapping, the proposed flow achieves an average 1.5% reduction in T-count. Overall, the proposed flow enables quantum oracle synthesis with lower resource costs.