ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (9): 1856-1874.doi: 10.7544/issn1000-1239.2021.20210314

所属专题: 2021量子计算专题

• 基础理论 • 上一篇    下一篇

面向超导量子计算机的程序映射技术研究

窦星磊,刘磊,陈岳涛   

  1. (计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190) (中国科学院计算技术研究所 北京 100190) (liulei2010@ict.ac.cn)
  • 出版日期: 2021-09-01
  • 基金资助: 
    国家自然科学基金项目(62072432,61502452)

An Investigation into Quantum Program Mapping on Superconducting Quantum Computers

Dou Xinglei, Liu Lei, Chen Yuetao   

  1. (State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190) (Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)
  • Online: 2021-09-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (62072432, 61502452).

摘要: 量子程序在量子计算机上执行时可能由于噪声产生错误.先前的量子程序映射策略将量子程序映射至量子计算机中的最健壮的区域上,以获得更高的保真度.在量子计算机上同时映射多个量子程序可以提升量子计算机的通量和资源利用率.但由于健壮资源稀缺、资源分配冲突,并发量子程序映射会导致整体可靠性下降.介绍了量子程序映射,对相关研究进行分类,并深入分析了其特点与区别.此外,针对并发量子程序映射问题提出了一种新的映射策略,包括3个关键设计:1)提出了社区发现辅助量子位划分算法.结合拓扑结构和错误率数据为并发量子程序进行物理量子位划分,提升初始映射可靠性,避免健壮资源的浪费.2)引入了跨程序SWAP操作,降低了并发量子程序的映射开销.3)提出了一种量子程序映射任务的调度框架,用于动态选取并发量子程序,在保证量子计算机保真度的前提下,提升了通量.所提策略较先前工作在程序执行保真度上提升了8.6%,节省了11.6%的映射开销.所设计的系统是一个面向量子计算机的操作系统原型——QuOS.

关键词: 量子计算, 并发程序, 映射, 保真度, 任务调度

Abstract: Errors occur due to noise when quantum programs are running on a quantum computer. Previous quantum program mapping solutions map a specific quantum program onto the most reliable region on a quantum computer for higher fidelity. Mapping multiple quantum programs onto a specific quantum computer simultaneously improves the throughput and resource utilization of the quantum computer. However, due to the scarcity of robust resources and resource allocation conflict, multi-programming on quantum computers leads to a decline in overall fidelity. We introduce quantum program mapping, classify the related studies, and analyze their characteristics and differences. Furthermore, we propose a new mapping solution for mapping concurrent quantum programs, including three key designs. 1) We propose a community detection assisted qubit partition (CDAQP) algorithm, which partitions physical qubits for concurrent quantum programs according to both physical topology and the error rates, improving the reliability of initial mapping and avoiding the waste of robust resources. 2) We introduce inter-program SWAPs, reducing the mapping overheads of concurrent quantum programs. 3) A framework for scheduling quantum program mapping tasks is proposed, which dynamically selects concurrent quantum programs to be executed, improving the throughput while ensuring the fidelity of the quantum computers. Our approach improves the fidelity by 8.6% compared with the previous solution while reducing the mapping overheads by 11.6%. Our system is a prototype of the OS for quantum computers—QuOS.

Key words: quantum computing, multi-programming, mapping, fidelity, task scheduling

中图分类号: