請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/93953完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃鐘揚 | zh_TW |
| dc.contributor.advisor | Chung-Yang Huang | en |
| dc.contributor.author | 鄭謹譯 | zh_TW |
| dc.contributor.author | Chin-Yi Cheng | en |
| dc.date.accessioned | 2024-08-09T16:39:29Z | - |
| dc.date.available | 2024-08-10 | - |
| dc.date.copyright | 2024-08-09 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-08-03 | - |
| dc.identifier.citation | [1] Mu-Te Lau, Chin-Yi Cheng, Cheng-Hua Lu, Chia-Hsu Chuang, Yi-Hsiang Kuo, Hsiang-Chun Yang, Chien-Tung Kuo, Hsin-Yu Chen, Chen-Ying Tung, Cheng-En Tsai, et al. Qsyn: A developer-friendly quantum circuit synthesis framework for nisq era and beyond. arXiv preprint arXiv:2405.07197, 2024.
[2] Aleks Kissinger and John van de Wetering. Reducing the number of non-clifford gates in quantum circuits. Physical Review A, 102(2):022406, 2020. [3] John van de Wetering. Zx-calculus for the working quantum computer scientist. arXiv preprint arXiv:2012.13966, 2020. [4] Mu-Te Lau. Private Communication, 2024. [5] Mehdi Mhalla and Simon Perdrix. Finding optimal flows efficiently. In EATCS International Colloquium on Automata, Languages and Programming (ICALP). ICALP 2008, pages 857–868, 2008. [6] John van de Wetering, Richie Yeung, Tuomas Laakkonen, and Aleks Kissinger. Optimal compilation of parametrised quantum circuits. arXiv preprint arXiv:2401.12877, 2024. [7] Korbinian Staudacher, Tobias Guggemos, Sophia Grundner-Culemann, and Wolfgang Gehrke. Reducing 2-qubit gate count for zx-calculus based quantum circuit optimization. arXiv preprint arXiv:2311.08881, 2023. [8] Cheng-Hua Lu. Dynamic quantum circuit optimization by ZX-calculus using Qsyn, July 2023. [9] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. [10] Anna M. Krol, Aritra Sarkar, Imran Ashraf, Zaid Al-Ars, and Koen Bertels. Efficient decomposition of unitary matrices in quantum circuit compilers. Applied Sciences, 12(2):759, January 2022. [11] Mikio Nakahara and Tetsuo Ohmi. Quantum computing: from linear algebra to physical realizations. CRC press, 2008. [12] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock. Minimal universal two- qubit controlled-NOT-based circuits. Physical Review A, 69(6):062321, June 2004. [13] Giulia Meuli, Mathias Soeken, Martin Roetteler, and Giovanni De Micheli. ROS: Resource-constrained oracle synthesis for quantum computers. In Proc. Electronic Proceedings in Theoretical Computer Science (EPTCS), volume 318, pages 119– 130, May 2020. [14] Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bjorner, and Giovanni De Micheli. Reversible pebbling game for quantum memory management. In Proc. Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 288– 291, March 2019. [15] Fang Zhang and Jianxin Chen. Optimizing T gates in Clifford+T circuit as π/4 rotations around Paulis, March 2019. [16] Vivien Vandaele, Simon Martiel, Simon Perdrix, and Christophe Vuillot. Optimal hadamard gate count for Clifford+ T synthesis of Pauli rotations sequences. ACM Transactions on Quantum Computing, 5(1):1–29, March 2024. [17] Luke E Heyfron and Earl T Campbell. An efficient quantum compiler that reduces T count. Quantum Science and Technology, 4(1):015004, September 2018. [18] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and effective techniques for T-count reduction via spider nest identities, April 2020. [19] Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33(10):1476–1489, October 2014. [20] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. Clifford Circuit Optimization with Templates and Symbolic Pauli Gates. Quantum, 5:580, November 2021. [21] Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar, and Zhihao Jia. Quartz: superoptimization of Quantum circuits. In Proc. ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI), pages 625–640, June 2022. [22] Earl T Campbell and Joe O'Gorman. An efficient magic state approach to small angle rotations. Quantum Science and Technology, 1(1):015007, December 2016. [23] Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum,3:205, December 2019. [24] Aleks Kissinger and John Van De Wetering. PyZX: Large scale automated diagrammatic reasoning. In Proc. Electronic Proceedings in Theoretical Computer Science (EPTCS), volume 318, pages 229–241, May 2020. [25] Mikio Nakahara and Tetsuo Ohmi. Quantum computing: from linear algebra to physical realizations. CRC press, 2008. [26] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:23, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [27] Robert Wille and Lukas Burgholzer. MQT QMAP: Efficient quantum circuit mapping. In Proc. International Symposium on Physical Design (ISPD), pages 198–204, March 2023. [28] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum, 4:279, June 2020. [29] Niel de Beaudrap, Aleks Kissinger, and John van de Wetering. Circuit Extraction for ZX-Diagrams Can Be #P-Hard. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 119:1–119:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [30] Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering. There and back again: A circuit extraction tale. Quantum, 5:421, March 2021. [31] Ketan N Patel, Igor L Markov, and John P Hayes. Efficient synthesis of linear reversible circuits. arXiv preprint quant-ph/0302002, 2003. [32] Haowei Deng, Yu Zhang, and Quanxi Li. CODAR: A contextual duration-aware qubit mapping for various NISQ devices. In Proc. ACM/IEEE Design Automation Conference (DAC), pages 1–6, 2020. [33] Robert Wille, Daniel Große, Lisa Teuber, Gerhard W Dueck, and Rolf Drechsler. RevLib: An online resource for reversible functions and reversible circuits. In Proc. International Symposium on Multiple Valued Logic (ISMVL), pages 220–225, 2008. [34] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proc. ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 1001–1014, 2019. [35] Ang Li, Samuel Stein, Sriram Krishnamoorthy, and James Ang. QASMBench: A low-level quantum benchmark suite for NISQ evaluation and simulation. ACM Transactions on Quantum Computing, 4(2):1–26, June 2023. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/93953 | - |
| dc.description.abstract | 在將演算法轉化為實際運行量子電路的過程中量子電路最佳化扮演著不可或缺的角色。在此領域中，透過ZX圖是一種降低小角度旋轉閘的常見方法。我們的研究聚焦在ZX-calculus的萃取，亦即如何將ZX圖轉換回量子電路的過程中降低雙量子邏輯閘的數量。於降低CZ邏輯閘的部分，我們研發出一套預測系統以動態調整萃取流程，同時仰賴配對演算法挑選萃取對象。於降低CX邏輯閘，我們採用了窮舉搜索的方式尋找區域性最佳解。在QASMBench電路中研究成果降低了28%的雙量子邏輯閘數量，同時減少25%的電路深度。同時，我們在Qsyn中使用C++語言實現了所提出的方法，使得Qsyn的萃取時間僅為PyZX的1/10。本研究顯著提高了量子電路最佳化的效率和效果，使未來該領域有更好的發展空間。 | zh_TW |
| dc.description.abstract | Quantum circuit optimization plays an indispensable role in transforming algorithms into functional quantum circuits. Within this field, the ZX-diagram-based method is a prevalent approach for minimizing small-angle rotation gates. Our research reduces double-qubit gate count in the extractor component of ZX-calculus, which involves converting ZX-diagrams back into quantum circuits. For the CZ gates minimization, the research relies on a predictor to dynamically rearrange the steps during extraction and provides a heuristic to select candidates. With respect to CX gates, we adopt the exhaustive search method to solve the local optimal solution. Our proposed method achieves a 28% reduction in double-qubit gate count and a 25% reduction in circuit depth in QASMBench. Furthermore, we implement the proposed method in Qsyn using C++, enabling Qsyn to perform quantum circuit optimization with an extraction time that is only 1/10 that of PyZX. This work significantly advances the efficiency and effectiveness of quantum circuit optimization, paving the way for further innovations in the field. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-08-09T16:39:28Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-08-09T16:39:29Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements i
中文摘要 ii Abstract iii Contents iv List of Figures vii List of Tables ix Denotation x Chapter 1 Introduction 1 1.1 Quantum Circuit Synthesis 2 1.2 ZX-calculus-based Quantum Circuit Optimization 2 1.3 Motivation and Problem Statement 3 1.4 Contributions of the Thesis 4 1.5 Thesis Organization 5 Chapter 2 Background Knowledge for Quantum Circuit Synthesis Flow 6 2.1 Quantum Circuit 6 2.2 Quantum Circuit Synthesis Flow 8 Chapter 3 Introduction to ZX-Calculus-Based Quantum Circuit Optimization Flow 11 3.1 ZX-diagram 11 3.1.1 ZX symbols and definitions 11 3.1.2 ZX-diagram rewriting rules 15 3.2 ZX-calculus-based Quantum Circuit Optimization Flow 19 3.2.1 Converting a quantum circuit to a ZX-diagram 20 3.2.2 Full reduction routine in ZX-diagram 21 3.2.3 Extracting a quantum circuit from a ZX-diagram 22 3.2.4 Post-extraction quantum circuit optimization 22 3.3 Strengths and Limitations of the Existing Flow 24 Chapter 4 Quantum Circuit Extraction from ZX-diagram 26 4.1 General Approach for Converting a ZX-diagram to a Quantum Circuit 26 4.1.1 Generalized flow (Gflow) 27 4.1.2 Preliminaries for extraction 28 4.2 Maximum Delay Gflow Extraction Algorithm 29 4.2.1 Extracting rotations and CZs from Frontier 30 4.2.2 Extracting Hadamard gates 31 4.2.3 Extracting CXs by removing edges between Frontier and Neighbors 32 4.2.4 Managing the gadget connecting to Frontier 33 4.2.5 Extracting the SWAP gates 34 4.3 Case study: Converting a Toffoli-2 ZX-diagram to a Quantum Circuit 35 Chapter 5 Optimizing Double-qubit Gates in Extraction 38 5.1 Optimizing the CZ Gates 38 5.1.1 The existing limitation on extracting CX and CZ gates 38 5.1.2 Applying pivot rules on Frontier with inner edges 39 5.2 Optimizing the CX gates 42 5.2.1 Extracting CX gates by Gaussian Elimination 42 5.2.2 The Gaussian Elimination is far from optimal solution 43 5.2.3 Extracting CX gates by exhaustive search 45 Chapter 6 The Proposed Dynamic Quantum Circuit Extraction Flow 47 6.1 Overview of the Proposed Flow 47 6.2 Edge Selection for Gadget Removal 49 6.3 The Predictive Formula on Whether Removing Gadget Before Extracting CZ gates 51 Chapter 7 Experimental Results 56 7.1 Setup and Benchmarks Used in Experiments 56 7.2 Comparison Baselines: PyZX and Qsyn Extractors 58 7.3 Comparisons on Optimization Levels of CXs 63 7.4 Comparisons on Different Edge Selections for Removing Gadgets 66 7.5 Comparisons on the Coefficient in the Predictive Formula 71 7.6 Experimental Results of the Proposed Method 73 Chapter 8 Conclusion and Future Directions 77 8.1 Strengths of Our Work 77 8.2 Limitations and Future Directions 78 References 80 | - |
| dc.language.iso | en | - |
| dc.subject | 動態萃取 | zh_TW |
| dc.subject | ZX-calculus 萃取器 | zh_TW |
| dc.subject | Gadget 移除 | zh_TW |
| dc.subject | 量子電路最佳化 | zh_TW |
| dc.subject | Quantum Circuit Optimization | en |
| dc.subject | ZX-calculus Extractor | en |
| dc.subject | Dynamic Extraction | en |
| dc.subject | Gadget Removal | en |
| dc.title | 改進基於 ZX 圖之量子電路最佳化流程中之 雙量子位元邏輯閘萃取技術 | zh_TW |
| dc.title | Improving Double-Qubit-Gate Extraction in ZX-Diagram-Based Quantum Circuit Optimization | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 鄭皓中;江介宏 | zh_TW |
| dc.contributor.oralexamcommittee | Hao-Chung Cheng;Jie-Hong Jiang | en |
| dc.subject.keyword | 量子電路最佳化,ZX-calculus 萃取器,動態萃取,Gadget 移除, | zh_TW |
| dc.subject.keyword | Quantum Circuit Optimization,ZX-calculus Extractor,Dynamic Extraction,Gadget Removal, | en |
| dc.relation.page | 84 | - |
| dc.identifier.doi | 10.6342/NTU202402828 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2024-08-06 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電機工程學系 | - |
| dc.date.embargo-lift | 2029-08-03 | - |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf 此日期後於網路公開 2029-08-03 | 11.31 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。