中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit

文献类型：期刊论文

作者Yang, Shuai1,2; Zi, Wei1,2; Wu, Bujiao3; Guo, Cheng1,2; Zhang, Jialin1,2; Sun, Xiaoming1,2
刊名IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
出版日期2024-03-01
卷号43期号:3页码:868-877
关键词Qubit Logic gates Boolean functions Quantum circuit Quantum algorithm Circuit synthesis Sun limited ancillary qubit satisfiability (SAT) problem SAT-oracle space-depth tradeoff
ISSN号0278-0070
DOI10.1109/TCAD.2023.3325974
英文摘要One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an m -clause SAT-oracle necessitates 2m-1 ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to O(log m) using m ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover's algorithm.
资助项目National Natural Science Foundation of China
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:001170495100013
出版者IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
源URL[http://119.78.100.204/handle/2XEOYT63/39645]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Sun, Xiaoming
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China
3.Peking Univ, Ctr Frontiers Comp Studies, Beijing 100871, Peoples R China
推荐引用方式
GB/T 7714		 Yang, Shuai,Zi, Wei,Wu, Bujiao,et al. Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit[J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,2024,43(3):868-877.
APA Yang, Shuai,Zi, Wei,Wu, Bujiao,Guo, Cheng,Zhang, Jialin,&Sun, Xiaoming.(2024).Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit.IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,43(3),868-877.
MLA Yang, Shuai,et al."Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit".IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 43.3(2024):868-877.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。