Quantum Circuit Design for Integer Multiplication Based on Schonhage-Strassen Algorithm
文献类型：期刊论文
| 作者 | Nie, Junhong2,3; Zhu, Qinlin2,3; Li, Meng2,3; Sun, Xiaoming1,2,3 |
| 刊名 | IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
 |
| 出版日期 | 2023-12-01 |
| 卷号 | 42期号:12页码:4791-4802 |
| 关键词 | Quantum circuit Qubit Arithmetic Logic gates Convolutional neural networks Time complexity Standards Integer programming Integer multiplication quantum circuit Sch\"onhage--Strassen algorithm |
| ISSN号 | 0278-0070 |
| DOI | 10.1109/TCAD.2023.3279300 |
| 英文摘要 | Quantum arithmetic circuits have attracted extensive attention recently since it plays fundamental roles in many applications of quantum computing. Specifically, quantum circuits for integer multiplication are of great significance to various quantum algorithms, including Shor's integer factorization and discrete logarithm algorithm. In this article, we design a family of quantum circuits for integer multiplication based on the famous classical integer multiplication algorithm, Schonhage-Strassen algorithm. We have made slight modifications to the algorithm to simplify its quantum circuit implementation. As a result, the quantum circuit we designed has gate depth O(log(2)n) . To the best of our knowledge, this is the first poly-logarithmic depth quantum circuit for integer multiplication which keeps the circuit size and the number of ancillary qubits subquadratic. Our design has size O(nlog nlog logn) counted by elementary quantum gates which is the same as the time complexity of the Schonhage-Strassen algorithm, and it consumes O(nlog nlog logn) clean ancillary qubits. In addition, we also utilize a weaker version of Schonhage-Strassen algorithm to give a family of circuits which has depth at the same order O(log(2)n) but with significantly smaller constants, while still keeping the size and number of ancillary qubits subquadratic. |
| 资助项目 | National Natural Science Foundation of China |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:001123254100036 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/38850]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Sun, Xiaoming |
| 作者单位 | 1.Shanghai Innovat Ctr Processor Technol, Shanghai 200234, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Nie, Junhong,Zhu, Qinlin,Li, Meng,et al. Quantum Circuit Design for Integer Multiplication Based on Schonhage-Strassen Algorithm[J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,2023,42(12):4791-4802. |
| APA | Nie, Junhong,Zhu, Qinlin,Li, Meng,&Sun, Xiaoming.(2023).Quantum Circuit Design for Integer Multiplication Based on Schonhage-Strassen Algorithm.IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,42(12),4791-4802. |
| MLA | Nie, Junhong,et al."Quantum Circuit Design for Integer Multiplication Based on Schonhage-Strassen Algorithm".IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 42.12(2023):4791-4802. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。