請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/101765完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃鐘揚 | zh_TW |
| dc.contributor.advisor | Chung-Yang Ric Huang | en |
| dc.contributor.author | 楊翔淳 | zh_TW |
| dc.contributor.author | Hsiang-Chun Yang | en |
| dc.date.accessioned | 2026-03-04T16:23:29Z | - |
| dc.date.available | 2026-03-05 | - |
| dc.date.copyright | 2026-03-04 | - |
| dc.date.issued | 2026 | - |
| dc.date.submitted | 2026-02-23 | - |
| dc.identifier.citation | [1] M. Amy, D. Maslov, and M. Mosca. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014.
[2] M. Amy and N. J. Ross. The phase/state duality in reversible circuit design. arXiv preprint arXiv:2105.13410, 2021. [3] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457–3467, 1995. [4] C. H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18(4):766–776, 1989. [5] E. Bernstein and U. Vazirani. Quantum complexity theory. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 11–20. ACM, 1993. [6] R. K. Brayton and A. Mishchenko. ABC: An academic industrial-strength verification tool. In Proceedings of the 22nd International Conference on Computer Aided Verification (CAV), volume 6174 of Lecture Notes in Computer Science, pages 24–40. Springer, 2010. [7] M. J. Bremner, C. M. Dawson, J. L. Dodd, A. Gilchrist, A. W. Harrow, D. Mortimer, M. A. Nielsen, and T. J. Osborne. Practical scheme for quantum computation with any two-qubit entangling gate. Physical Review Letters, 89(24):247902, 2002. [8] D. Canright. A very compact AES S-box. In Cryptographic Hardware and Embedded Systems – CHES 2005, volume 3659 of Lecture Notes in Computer Science, pages 441–455. Springer, 2005. [9] M. DeCross, E. Chertkov, M. Kohagen, and M. Foss-Feig. Qubit-reuse compilation with mid-circuit measurement and reset. Physical Review X, 13(4):041057, 2023. [10] D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A, 439(1907):553–558, 1992. [11] C. Gidney. Halving the cost of quantum addition. Quantum, 2:74, 2018. [12] C. Gidney and M. Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5:433, Apr. 2021. [13] C. Gidney and N. C. Jones. A CCCZ gate performed with 6 T gates. arXiv preprint arXiv:2106.11513, 2021. [14] M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt. Applying grover’s algorithm to AES: Quantum resource estimates. In Post-Quantum Cryptography (PQCrypto 2016), volume 9606 of Lecture Notes in Computer Science, pages 29–43. Springer, Cham, 2016. [15] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 212–219. ACM, 1996. [16] D. Herr, F. Nori, and S. J. Devitt. Optimization of lattice surgery is np-hard. npj Quantum Information, 3:35, 2017. [17] F. Hua, Y. Jin, Y. Chen, S. Vittal, K. Krsulich, L. S. Bishop, J. Lapeyre, A. Javadi-Abhari, and E. Z. Zhang. Caqr: A compiler-assisted approach for qubit reuse through dynamic circuit. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (ASPLOS ’23). ACM, 2023. [18] C. Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Physical Review A, 87(2):022328, 2013. [19] C. Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Physical Review A, 87(2):022328, 2013. [20] K. Keutzer. DAGON: Technology binding and local optimizations by DAG matching. In Proceedings of the Design Automation Conference (DAC), pages 617–623, 1987. [21] R. Královič. Time and space complexity of reversible pebbling. In Mathematical Foundations of Computer Science (MFCS), 2001. [22] N. Li and E. Dubrova. Aig rewriting using 5-input cuts. In 2011 IEEE 29th International Conference on Computer Design (ICCD), pages 429–430, 2011. [23] D. Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3:128, 2019. [24] D. Litinski. Magic State Distillation: Not as Costly as You Think. Quantum, 3:205, Dec. 2019. [25] D. S. Marakkalage, L. Amarú, P.-E. Gaillardon, and G. De Micheli. Three-input gates for logic synthesis. arXiv preprint arXiv:2011.02088, 2020. [26] D. S. Marakkalage, E. Testa, H. Riener, A. Mishchenko, M. Soeken, and G. D. Micheli. Three-input gates for logic synthesis. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 40(10):2184–2188, 2021. [27] D. Maslov. Advantages of using relative-phase Toffoli gates with an application to multiple-control Toffoli optimization. Physical Review A, 93(1):022311, 2016. [28] G. Meuli, M. Soeken, E. T. Campbell, M. Roetteler, and G. De Micheli. The role of multiplicative complexity in compiling low T-count oracle circuits. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1–8, New York, NY, USA, 2019. IEEE. [29] G. Meuli, M. Soeken, and G. De Micheli. Xor-and-inverter graphs for quantum compilation. npj Quantum Information, 8(1):7, 2022. [30] G. Meuli, M. Soeken, M. Roetteler, N. S. Bjørner, and G. De Micheli. Reversible pebbling game for quantum memory management. In Proceedings of the 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 288–291, Piscataway, NJ, USA, 2019. IEEE. [31] G. Meuli, M. Soeken, M. Roetteler, and G. De Micheli. Ros: Resource-constrained oracle synthesis for quantum computers. In Proceedings of the 2019 Quantum Physics and Logic (QPL), volume 318 of EPTCS, pages 119–130, 2020. [32] A. Mishchenko and R. Brayton. Fraigs: A unifying representation for logic synthesis and verification. In Proceedings of the International Workshop on Logic and Synthesis (IWLS), 2005. [33] A. Mishchenko, S. Chatterjee, and R. Brayton. Fast computation of k-feasible cuts. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 198–203. IEEE, 2007. [34] A. Mishchenko, S. Chatterjee, R. Jiang, and R. Brayton. A boolean logic optimization algorithm based on AIGs. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2006. [35] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition edition, 2010. [36] P. Selinger. Quantum circuits of T-depth one. Physical Review A, 87(4):042302, 2013. [37] M. Soeken, H. Riener, G. De Micheli, et al. The EPFL logic synthesis libraries. arXiv preprint arXiv:1805.05121, 2018. [38] E. Testa, M. Soeken, L. Amarù, and G. D. Micheli. Reducing the multiplicative complexity in logic networks for cryptography and security applications. In Proceedings of the 56th Annual Design Automation Conference (DAC ’19), Las Vegas, NV, USA, June 2019. ACM. [39] N. H. E. Weste and D. Harris. CMOS VLSI Design: A Circuits and Systems Perspective. Addison-Wesley, 4 edition, 2011. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/101765 | - |
| dc.description.abstract | 量子預言機在量子演算法與密碼學中扮演重要角色。傳統的合成流程會先將經典電路轉換為 XOR-AND 圖（XAG），再將該 XAG 編譯成量子預言機。然而，現有的 XAG 合成流程往往忽略較高輸入扇入的邏輯元件，導致生成的 XAG 含有過多的與邏輯閘，進而使量子預言機需要更高資源實現。
我們提出一個新的量子預言機合成流程，在技術映射中引入 NPN 類別以降低 XAG 中 AND 閘的數量。此外，我們針對可逆卵石遊戲中的與邏輯閘鏈運算提出一種降低 T-count 為目標的最佳化演算法。最後，我們針對一個新的最佳化目標–時空體積提出一個啟發式演算法。 實驗結果顯示，與典型合成流程相比，時空體積平均降低 45.6%。此外，透過在映射過程中允許更豐富的邏輯元件（例如 AND3 與 AIA 閘），我們在 T-count上平均可達到 1% 的改善。總體而言，我們所提出的流程能以更低的資源成本完成量子預言機合成。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2026-03-04T16:23:29Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2026-03-04T16:23:29Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements ii 摘要 iv Abstract v Contents vii List of Figures xi List of Tables xiii Denotation xiv Chapter 1 Introduction 1 1.1 Applications of Quantum Oracles 1 1.2 Introduction to a Typical Quantum Oracle Synthesis Flow 2 1.3 Resource Optimization for Quantum Oracle Synthesis 3 1.4 Previous Work on Quantum Oracle Synthesis 4 1.5 Contribution of this work 5 1.6 Thesis Structure 6 Chapter 2 Preliminary 7 2.1 Introduction to Quantum Circuit 7 2.1.1 Quantum Bit and Quantum State 8 2.1.2 Quantum Gate 8 2.1.3 Initialization and Measurement 10 2.2 Quantum Oracle 11 2.3 And-Inverter Graph & Xor-And-Inverter Graph 12 2.4 Technology Mapping 14 2.4.1 Cut-Based Technology Mapping 15 2.4.2 Example for Technology Mapping 16 2.5 NPN Classes 17 2.6 Low-T-count Logical Gates Using Ancilla 19 2.6.1 AND Gate Implemented using 4 T-gates 20 2.6.2 6-T CCCX gate and 3-input AND gate 21 2.7 Reversible Pebbling Game 23 2.7.1 Preprocess 23 2.7.2 Scheduling 24 2.7.3 Postprocess 27 2.7.4 Example for Reversible Pebbling Game 28 Chapter 3 And-Reduction-Driven Cell Library for Technology Mapping 31 3.1 Effect of Reducing the Number of AND Gates 31 3.2 Caveats of Mapping Functions to Pure XAG Circuits 32 3.3 Adding 3-, 4-, and 5-Input NPN Classes to the Cell Library 34 3.4 AIG Preprocess & Postprocess 35 Chapter 4 A T-optimized Algorithm for Realizing AND Chains in the Reversible Pebbling Game 37 4.1 Introduction to AND3-like Operations 37 4.2 Example of Choosing an AND3-like Operation over Two AND2 Gate 39 4.3 Cost Function for Trading AND2 with AND3-like Operation 41 4.4 An Algorithm for $T$-optimized Mapping 42 4.5 Example of the T-optimized Algorithm for Realizing AND Chains 44 Chapter 5 A Complete Oracle Synthesis Flow with Improved State-of-the-art Techniques 46 5.1 Ambiguity in Optimization Objectives of the Reversible Pebbling Game 46 5.2 New Objective: Space-Time Volume 48 5.3 A Heuristic Algorithm for Finding a Better Circuit Under the Space-Time Volume Metric 49 Chapter 6 Experimental Results 53 6.1 Experiment Settings 53 6.1.1 Benchmark Selection 54 6.2 Result 1: Reduced #AND2-count for Technology Mapping with NPN Classes as Cell Library 55 6.3 Result 2: The effect of AND-count on Reversible Pebbling Game using Space-Time Volume (w/ AND chain reduction) 55 6.4 Result 3: T-Count Reduction from T-Optimized AND Chains Algorithm 56 Chapter 7 Conclusion and Future Work 60 7.1 Conclusion 60 7.2 Future Work 61 7.2.1 Effect of NPN Classes in Cell Library 61 7.2.2 How XAG Structure Affects Pebbling-Based Synthesis 62 7.2.3 Improving the Space--Time Volume Heuristic 63 References 64 Appendix A - ABC Commands Used for AIG Optimization and Technology Mapping 69 A.1 Overview 69 A.2 Example 69 Appendix B - NPN Classes XAG Generation with Minimum AND2 Implementation 71 B.1 Enumeration of 4-input NPN Classes 71 B.2 Minimum-AND2 Implementations for Selected \ 5-Input NPN Classes 73 Appendix C - And-Inv-And Implementation with 6 T-count 74 | - |
| dc.language.iso | en | - |
| dc.subject | 量子運算 | - |
| dc.subject | 量子預言機合成 | - |
| dc.subject | NPN類別 | - |
| dc.subject | 技術映射 | - |
| dc.subject | 可逆卵石遊戲 | - |
| dc.subject | 時空體積 | - |
| dc.subject | Quantum Computing | - |
| dc.subject | Quantum Oracle Synthesis | - |
| dc.subject | NPN Classes | - |
| dc.subject | Technology Mapping | - |
| dc.subject | Reversible Pebbling Game | - |
| dc.subject | Space-Time Volume | - |
| dc.title | 透過與邏輯閘降減導向技術映射與 T 最佳化可逆卵石遊戲技術改進量子預言機合成 | zh_TW |
| dc.title | Improving Quantum Oracle Synthesis via AND-Reduction-Driven Technology Mapping and T-Optimized Reversible Pebbling Techniques | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 114-1 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 洪士灝;邱大維;李建模 | zh_TW |
| dc.contributor.oralexamcommittee | Shih-Hao Hung;Dah-Wei Chiou;Chien-Mo Li | en |
| dc.subject.keyword | 量子運算,量子預言機合成NPN類別技術映射可逆卵石遊戲時空體積 | zh_TW |
| dc.subject.keyword | Quantum Computing,Quantum Oracle SynthesisNPN ClassesTechnology MappingReversible Pebbling GameSpace-Time Volume | en |
| dc.relation.page | 75 | - |
| dc.identifier.doi | 10.6342/NTU202600718 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2026-02-24 | - |
| dc.contributor.author-college | 重點科技研究學院 | - |
| dc.contributor.author-dept | 積體電路設計與自動化學位學程 | - |
| dc.date.embargo-lift | 2026-03-05 | - |
| 顯示於系所單位： | 積體電路設計與自動化學位學程 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-114-1.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 5.86 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。