本文将目前量子计算机技术的发展概况及主要问题梳理总结为3个方面。

1）量子芯片等计算基础架构。量子计算机通常采用超导（如IBMQ、谷歌悬铃木）、离子阱（UMD）、光量子（“九章”）等实现方式^[1,10-11]。但出于对芯片工艺、集成、维护等诸多因素的考量，采用超导器件是较为理想的选择。目前主流的超导量子芯片均是2D的Mesh结构（如图1）^[12]。从图1可以看出，每个超导量子位可与其附近的量子位产生连接，意味着这两个量子位之间可以进行CNOT等操作（量子纠缠）。在2D结构的量子芯片中，并非所有的量子位之间均有连接，也并非每个量子位向外连接其它量子位的数量都是一定的。并且，每个物理量子位的状态均不一样，导致每个量子位状态的保持时间、运算准确度均不相同，在有些情况下甚至差异很大^[13]。此外，量子位之间的连接器也会存在不稳定的现象进而影响计算的准确度。在计算过程中，如果两个逻辑量子位需要纠缠但它们之间的物理位置在芯片上却并不相邻，那么则需要SWAP交换操作将这两个逻辑量子位移动到有连接且紧邻的位置。SWAP操作依赖于量子位之间的连接器，如果连接器不稳定，每次SWAP操作均会削弱量子位的一致态，致使最终的计算结果不准确。由于这些问题，量子线路/算法在芯片上运行时会产生不稳定的运算结果，亦即运算的准确率（Fidelity）时常产生波动。

图  1  IBMQ_melbourne和IBMQ_yorktown的2D的Mesh结构

以ibm_washington^[14]量子芯片为例，其拥有127个物理量子位，是目前IBM可提供的具有最多量子位的量子芯片。在该芯片中，量子位一致状态保持时间平均为101.6 us，而执行单个量子门操作所需的平均时间为550.41 ns。因此，可在该量子芯片上执行的量子线路（程序）的深度将会受限，即理论上量子程序深度超过约180后，便难以保证量子位的一致状态（计算结果无效）。此外，量子芯片中不同量子位、连接器执行操作的错误率也不同，时刻影响着计算效果。例如，在ibm_washington中CNOT门操作错误率最低可达0.59%，最高可达17.3%，平均为1.92%；量子位读出错误率最低可达0.30%，最高可达35.60%，平均为3.13%。综上所述，量子计算基础架构处在不断进步发展的阶段，如何提高量子计算芯片等基础计算架构的可用性、可靠度、准确率是需要解决的问题。

2）量子操作系统及软件栈。操作系统（OS）及软件栈是计算机系统的“魂”，可用性强的计算机系统不可能脱离系统软件体系的支撑而独立存在，量子计算机也如是。

目前，量子计算机的存在形式多种多样，有包括量子设备型与量子芯片型等。典型的量子设备型计算机类似于“九章”量子计算设备^[1]，是一套能够产生特定的光量子反应的设备，用以完成某种特定的计算任务，整个设备可被视为一台用以完成某项任务的专用计算机系统。典型的基于量子芯片的量子计算机（如IBMQ、谷歌悬铃木等）通常具备一定的可编程性，量子位（采用固态超导材质较多）的排布呈现2D的Mesh结构，目前可集成100个量子位左右（如IBMQ最新的量子芯片ibm_washington可集成127个物理量子位^[14]，谷歌的Bristlecone量子芯片集成了72个物理量子位^[15]）。量子操作系统及系统软件栈向用户隐藏了量子计算机底层的具体物理实施细节，为上层量子算法、量子程序的执行提供接口。当执行一个量子程序时，用户将高级语言（如QASM^[16]，Scaffold^[17]）表示的量子算法作为输入，经过系统软件栈（OS）的转换、优化、调度和映射，最终生成能够在特定量子计算机硬件上执行的机器指令序列。

“量子程序/线路的映射”是量子软件栈及OS的关键挑战之一。量子程序/线路需要被映射到量子位上才能运行。映射机制关系到量子程序能否运行在有较高稳定性、较高准确性的物理量子位上；也关系到昂贵的量子芯片的利用率、可用度和运行准确率。随着量子芯片的发展，量子程序映射机制也进行着深刻的变化。如先前的映射机制仅将量子芯片抽象为1D或2D简化模型^[18-19]，后续引入了针对实际芯片拓扑结构的考量^[20-21]。对量子门操作错误率的优化^[13]、对串扰错误的考虑^[22-23]也逐步被加入到量子程序映射机制中。近期，随着量子计算云服务的发展，提升量子计算机的通量和资源利用率成为了一项重要需求；文献[24-26]提出了同时映射多个并发量子程序的解决方案。此外，并发调度多个量子程序也能够帮助加速量子机器学习领域中的变分量子算法（VQA）^[27]。

并发量子程序映射问题又对现有的量子程序映射机制提出挑战。现有的映射策略主要支持单程序，难以在两个量子程序间进行公平的资源分配，难以保证每个量子程序的执行保真度。当前的研究者普遍认为，随着量子计算机架构的快速发展，量子程序映射策略将不断更迭，以充分挖掘量子计算机硬件的能力，保证计算的可靠度、准确度。

3）量子算法/线路的优化。量子算法的实现媒介是量子线路；量子线路通过各种量子门操作多个物理量子位实现量子算法进而达到计算目的。图2展示了Grover算法^[6]对应的量子线路图，其功能是在N个无序数据中搜索一个特定数据。量子线路是量子算法的显化，决定着在量子芯片上如何进行计算，因此，优化量子线路就是优化量子计算的过程。

图  2  Grover算法对应的量子线路图（搜索“01”）

从物理机的角度来讲，目前能够集成的量子位数量还比较有限。IBM目前已制造出的量子计算机中最多包含1121个物理量子位。然而由于量子位数目和错误率的限制，目前的量子计算机仍不能运行大规模的量子程序（如破解RSA-2048预计需要4000个以上量子位）。因此，如何优化量子算法，优化（缩减）量子线路规模，使其可在现有的量子计算机上成功运行并准确输出结果，就成为至关重要的研究内容。被优化的量子线路需要具有和被优化之前同样的准确度（Fidelity），否则，优化就失去了意义。酉矩阵的分解^[28-29]是量子算法优化关注的一个重点问题。每个量子算法可由一个酉矩阵表示。要在具体量子计算机上执行该量子算法，需进行酉矩阵的分解，即把酉矩阵分解为特定量子计算机支持的基础门操作的组合。其优化目标是缩减酉矩阵分解后所占用的量子位数目和量子线路深度。另一个问题是量子线路的转化^[30-32]，其关注如何对已有的量子程序进行等价转换，消除量子线路中的冗余操作，优化量子线路的规模和深度。

由于目前的量子计算机尚不普及，采用超级计算机集群模拟大规模量子线路的运行是一种普遍的方式^[33-34]，也是国内外研究的热点。从这个角度来看，对量子算法、线路的优化也能够降低超算模拟的复杂度和运算成本。

此外，业界也对经典计算机与量子计算机的协作方式进行了积极的讨论。首先，量子计算机可作为经典计算机的协处理器。当前计算机除了CPU之外，通常会包括GPU、FPGA等异构加速器或协处理器，协助加速处理特殊类型的计算任务。文献[35]讨论了可将量子芯片作为经典计算机的qFPGA协处理器，协助处理适合量子计算机处理的计算任务。其次，可结合量子计算机与经典计算机的计算能力，协同完成量子计算任务。大型量子线路可被拆分为多个小规模的部分^[36-40]，分别在多个量子计算机或经典计算机上执行，最终进行结果合并。该方法允

许协同量子计算机和经典计算机，执行更大规模的量子程序。然而，此类方法仍存在诸多局限性，例如灵活性低，量子线路拆分带来的计算开销较高等，仍存在较大的优化空间。

笔者认为以上这三层次之间存在深刻的关联，相互依存影响，均系量子计算机系统实用化的关键层次。量子计算机系统不仅包括底层计算架构，也应包括相应的软件系统栈及优化机制（专用的计算设备除外）。目前，国内外相关科研机构均在积极部署相关的科研与技术攻关。然而，量子计算系统尚处在蓬勃发展阶段。在量子芯片方面，虽然IBM、谷歌等公司在努力增大单个量子芯片上的量子位数，但从目前数据来看，超导量子芯片上能够集成的量子位的数量依然在100左右^[14-15]，还不能满足很多有实用价值的量子算法的需求。在量子计算软件栈方面，目前国内外的相关技术均在积极发展阶段，正是百家争鸣、百花齐放的时刻，这中间存在这很多机遇和挑战，软件栈的创新和优化还有较大的空间（如并行量子任务调度、量子算法纠错、量子芯片上的任务映射等）。在量子算法/线路优化方面，目前诸多工作在探索使用量子算法解决现实和经典问题^[4-7]，也有工作尝试将AI与量子计算相结合^[2-3]。

为推进量子计算的实用化，国内外学术界、工业界从量子芯片架构及工艺^{[10～11,41～51]}、量子操作系统及软件栈^{[13,18～27,35,47,52～72]}、量子算法优化^[28～32]方面开展了积极的探索。这些工作探索了如何通过改进硬件工艺、优化系统软件栈的方式保证量子程序的保真度或更高效、可靠地运行更大规模的量子程序。

一系列工作针对量子芯片架构及工艺优化作出了积极的探索，内容涉及量子位及连接器制造工艺^{[10-11,41～45]}、量子内存的实施^[46-47]、量子芯片集成和封装^[48-49]等关键技术。有研究者提出了针对特定量子线路的量子芯片设计流程^[50-51]，根据该类量子线路的特点，确定物理量子位的放置位置、连接和频率，设计专用量子芯片。这些技术提升了量子芯片的可靠性，但要使量子芯片进一步向实用化迈进，需量子操作系统和系统软件栈的跨层次协同设计。

为优化量子程序执行保真度，充分利用量子计算机中有限的资源，研究者针对量子系统软件栈中的各个层次进行了改进和优化。其中包括量子程序映射、错误抑制、并发程序调度、调试与断言、量子纠错编码等。量子程序映射问题已被证明是NP-完全问题^[20,52]，求解该问题的技术可分为两类。一类方法^{[20,22,52,55-59]}将量子程序映射问题转换为等价的有约束条件的优化问题，并采用求解器^[53-54]求解。此类方法可获得小型量子程序映射问题的最优解或近似最优解，但算法时间复杂度高，难以支持求解具有数十个以上量子位的量子程序映射问题。第二类方法^{[13,18-21,57,60-64]}采用启发式信息辅助搜索，具有更优的可扩展性，不受限于量子芯片和量子程序的规模，具有处理更大规模量子程序映射问题的能力，但无法保证所求解结果为最优解。其中一部分工作^{[18-19,60-61]}对量子芯片结构进行了简化，针对1D线性模型或2D网格模型设计启发式算法。另外的工作^{[13,20,21,57,62-64]}则基于具体的芯片拓扑结构。此外，一些工作为提升量子程序的执行保真度，设法对量子芯片上易发生的错误进行抑制，具体包括串扰错误抑制^[22-23,65]、测量错误抑制^[66]，以及通过采用多种初始映射对局部不可靠资源错误的抑制^[67]等。研究工作^[13,25-27]对并发量子程序映射问题进行了探索，支持在同一量子芯片上同时映射和执行多个量子程序。文献[25-26]提出了并发量子程序调度机制，允许依据用户需求，自动判断是否采用并发机制，并能够选择最优的并发量子程序共同执行。这些工作帮助了量子计算机在量子计算云服务逐渐兴起的背景下提升资源利用率和通量，也能帮助加速变分量子算法（VQA）的执行。[68-69]设计和改进了量子程序中的断言机制，通过在量子线路中设置断言，检测量子位是否满足预期状态，协助完成量子程序调试。量子纠错编码（QEC）能检测并纠正量子程序执行期间发生的错误，是未来实现容错量子计算的重要保证。一些工作^[47,70～72]对量子纠错编码的实现和优化进行了探究，对构造一个纠错码所需的物理量子位数目、量子纠错码的执行效率进行了优化和改进。这一系列对量子操作系统及系统软件栈的优化与改进也将为本文提供参考。

量子程序/线路的优化可帮助消除量子线路中的冗余操作，在保证功能、运算结果不变的情况下简化量子线路。相关工作^[30,73]是研究量子程序优化较有代表性的工作，核心是通过冗余量子位缩减量子线路深度，从而缩短量子程序执行时间，避免由于执行时间过长导致不能保持一致状态。

目前用于求解大规模的科学计算的量子计算机还处在发展阶段，因此使用经典计算机搭建量子计算模拟系统，仍是目前研究量子算法和验证量子计算有效性的必要方式。国内外许多公司机构设计并开发了量子计算模拟器。例如，阿里巴巴发布的“太章”模拟器^[74]、英特尔的量子模拟器“Qhipster”^[75]、牛津大学的通用量子模拟器“QuEST”^[76]等。这些模拟器各有其应用领域，在模拟效率、规模、扩展性等方面也各有优势。使用经典计算机模拟量子计算的难点在于随着模拟的量子位数的增长，模拟的时间和空间开销呈指数级增长^[74]，单机已无法满足对于大规模量子计算的模拟。一些工作^[74,77～80]基于大规模集群模拟量子计算，通常采用任务拆分^{[36～40,74,77,78]}、节点数据传输优化^[79,80]的方式优化超算集群的并行处理能力。然而目前模拟器能模拟的量子位数、量子应用仍然有限，且消耗的资源较大，模拟效率也不高。量子模拟器的整体效能有待进一步优化。此外，采用混合计算架构（使经典计算机与量子计算机协同工作），是运行更大规模量子程序的另外一种可行方法。有研究者^[36～40]提出可将较大规模的量子线路拆成多个小规模的线路，使之在多台小型量子计算机上分别执行或在经典计算机上模拟执行，最终再将运算结果汇总，以达到处理较大规模量子线路的目的。

综上所述，国内外在本文涉及的领域内已有一定的探索经验，同时也留下了更为广阔的继续探索空间。我们将以这些工作为基础，以推动国内量子计算实用化为目标，结果国内实际情况，进一步探索新型的量子计算系统栈的关键技术。

本文将着重介绍量子操作系统（QuOS）的设计思想及初步的实现。本文的目的是为正蓬勃发展的量子计算探索出一套实用性较高的、高效能系统栈技术方案，进而充分发挥量子计算架构在计算效率、效能上的优势，在推进领域内学术进步的同时，也有望为社区作出创新性贡献。申请人期望本文能够为国家的量子计算架构及OS软件栈关键技术带来突破和新的思路。

对于超导量子计算机来说，量子位（Qubit）的资源分配就是QuOS的关键行为。在单个量子计算节点上，QuOS为量子程序分配量子位，也可以为并发的量子程序分配量子位。具体来说包括以下内容。

1）对于单个量子程序，QuOS将依据量子芯片的实时状态综合度量，选择稳定性高、错误率低的量子位及连接进行分配，进而确保量子程序的准确度（Fidelity），以及量子计算机的可靠度。

2）QuOS应能调度并发多量子程序。综合量子芯片的实时情况，及待调度量子程序的需求，选择调度可并发的量子程序的最优组合，在尽可能的最大化并发多量子程序的准确度的同时，也提高了昂贵的量子计算机的利用率，为提供高可靠的“量子云”服务提供支持。

3）在多量子程序并发的情况下，通过程序隔离的方式，降低串扰（Crosstalk）等物理因素带来的影响；隔离运行异常的程序。

4）对于单量子程序，支持高效、最短路径的量子位SWAP操作，减少准确度的损失。在多程序并发的情况下，支持程序间量子位SWAP操作。

5）QuOS支持单量子任务、多量子任务调度。 定义两种任务 --（1）完全可在量子计算机上执行的任务；（2）混合计算任务，一部分在量子计算机上运行，一部分在经典超算上运行。

QuOS对上层用户隐藏硬件体系结构层次的细节。目前看来，量子计算的计算架构会有如下3种计算形态：1）经典计算机上的任务划分出一部分运行在量子计算机上加速，进而使得整个任务更高效的执行；2）将量子计算的任务拆分出一部分用经典超算来模拟，解决目前由于量子位数量不足而导致的无法计算；3）将量子计算的任务拆分成若干个子任务，分散在不同的量子计算机上执行，形成“任务 -- 计算资源”的最佳匹配，更有效的利用量子计算机。

QuOS为达到为用户隐藏了这些底层混合异构计算架构的细节的目的，QuOS将包含面向异构量子计算的调度机制，将不同的任务映射到相应的量子计算机上，并支持根据用户标注的任务特性调度任务，支持对目前量子硬件信息的实时掌控来调度任务。经过混合计算架构中不同的处理部件分别处理的结果将会融合在一起，进而汇总成一个统一的运算结果。量子不能长时间保持稳定态；但是，分批执行的中间结果又必须被存储下来，并维持一段时间，等待其它程序片段的运行结果以进行合并。这是一对必须要被解决好的、天然存在的矛盾。为解决此问题，QuOS将支持一种基于“谐振腔”的量子数据存储架构及量子态存储/读取操作方法，将量子线路的中间处理结果保存在腔体中（按目前的技术指标，至少能提高两个数量级的状态保持时间），操作时再从腔体中读出并开展后继操作，并保证在量子状态不发生变化的硬实时性。

QuOS对用户提供统一的服务接口。具体行为包含以下3点。

1）QuOS提供统一的API，为程序员提供便利的编程抽象，支持程序员显式的在编写程序时标注语义，例如，程序中的哪些部分将被量子计算机执行，异构计算部件之间如何协同等关键问题。QuOS在运行时将根据这些信息在不同设备之间调度任务。

2）鉴于目前量子计算机“专用性”的存在形态，可预先在系统中固化一部分能够解决经典问题的量子线路模型（oracle算子），以简化提供统一服务的开销。在计算过程中，只要待解决的问题确定了，就可以在量子计算机上启动这些量子线路。此时，基于对问题的抽象，经典计算机将输入信号传递给量子计算机，通知量子计算机开始工作；量子计算机处理完成之后，经典计算机将会获得处理结果。目前，一些检索类的问题，一些在大范围空间中寻找最优解的问题，将有可能利用这种计算模型；同理，有了量子器件的辅助和加速，架构师/程序员在设计系统或编码的时候也可以更为大胆的设计一些之前仅用传统计算机不能、不敢涉及解决的问题。

3）QuOS需要协同多种量子计算设备工作，并在他们之间保持通信。在上层用户看来，他们不应该了解底层计算设备的太多细节，QuOS应该屏蔽大部分量子计算机运算的细节。信息的传递在QuOS层由管道（QuPipe）或软总线来完成。

QuOS需支持量子程序线路的调试、断言式、纠错等机制。量子线路必须在极短的时间内执行完毕（通常不超过数百微秒），并且需要多次重复执行并观测结果出现的概率。量子状态保持时间极短且不可复制，这就给量子程序的调试、纠错等带来挑战。QuOS需要支持针对量子线路特点的调试机制、断言式、纠错算法、结果验证等机制；支持量子线路稳定运行、输出结果可推演，争取在微秒级修复损坏的量子线路等。

基于上述设计原则，本文尝试实现了一种QuOS的原型系统（基于超导量子计算机），其中包括如下几种核心机制。更详细内容请参见文献[25-26]。量子操作系统是量子计算机系统资源的管理者，既负责映射、调度量子程序/任务，又负责分配、管理量子计算机硬件资源。本文介绍一个面向超导量子位NISQ量子计算机（如IBMQ）的操作系统原型（QuOS），包以下内容。

1、QuOS的设计 -- 量子程序映射机制及优化

量子程序/线路需要被映射到物理量子计算机上才能被执行，管理量子程序映射是QuOS的核心职责。量子位的映射结果直接决定这量子程序的运行效果和结果。针对最新的NISQ量子计算机的特性，QuOS包括量子程序映射框架，提升量子程序的Fidelity（准确度），提升量子计算机的可靠性和效率。具体包括以下四项关键技术：

a） 高内聚的量子位映射。结合物理量子位的实时状况，采用“社区发现”等算法对健壮量子位资源进行社区划分，将物理连接紧密且可靠的健壮量子位划分至同一社区中，搜索最优量子位区域进行分配，提升分配资源可靠度且避免可靠量子位资源的浪费。其总体思路是：根据量子芯片中量子位的物理拓扑，以及门操作、读出和串扰错误率，构建一棵层次树，对量子芯片中的健壮资源分布进行建模，帮助定位量子芯片上连接紧密且可靠的健壮资源，为量子程序提供更优的初始映射。层次树构建时以量子位的物理拓扑和错误率为依据，能够保证层次树中每个节点内量子位的可靠性和内聚性。具体包括以下内容。

首先是层次树的构建方法。QuOS基于“社区发现”过程，构造一棵层次树（二叉树）。层次树中每个节点代表一个社区，同时也是一个候选的待分配量子位区域。起始时，每个物理量子位对应层次树中的一个叶结点。本文在每次迭代中选取2个能使收益最大化的层次树节点进行合并，并将这2个节点作为合并后新节点的左右子节点，直到最终只剩下一个包含所有物理量子位的节点（层次树的根节点）为止。如图3展示了对于IBMQ London量子芯片构建的层次树。其中图3a为IBMQ量子芯片，每个节点对应的数值代表该物理量子位的读出操作错误率，连接上的数值代表两个物理量子位间的CNOT操作错误率。图3b则为依据“社区发现”方法为IBMQ构建的层次树^[25,26]。

图  3  IBMQ London量子芯片层次树

其次是层次树节点合并时收益的判断标准，主要包括两项。第一项涉及社区中量子位连接的紧密程度，具体采用两个社区合并前后，两种社区划分方案模块度的差值进行度量。模块度用于衡量一种社区划分方案的合理程度。差值越高，说明合并两个社区后，每个社区内部量子位连接更紧密。第二项涉及社区内量子位和连接器的可靠度。具体采用量子芯片中的门操作错误、串扰（crosstalk）错误和读出错误进行衡量。QuOS倾向于优先合并具有低读出、操作、串扰错误率且连接更紧密的量子位。因此，量子位集合越健壮，越容易被优先合并，其在层次树中的深度就越深。并且一个社区中的物理量子位健壮且具有紧密的相互连接，能够帮助缩减量子程序映射成本。

b） 并发多量子程序的映射。为提高量子计算机通量和资源利用率，QuOS支持并发量子程序任务映射机制，即在一个量子芯片上映射多道量子程序。

QuOS基于前文所述的层次树，为每个并发量子程序分配其初始映射区域，以支持并发量子程序映射。对于每个量子程序，自底向上搜索层次树，可搜索到多个可供分配的量子位集合。最终依据以下几项原则，选取最优的量子位集合进行分配。

首先，候选量子位集合中的量子位连接越紧密，越有助于降低量子位调度（SWAP）成本。对于一个量子位集合，其量子位连接的紧密程度可由其中每对量子位的SWAP路径长度（即最短路径-1）的平均值进行衡量。优先选取平均SWAP路径长度更小的量子位集合，以降低后续量子位调度的SWAP开销。

其次，候选量子位集合中门操作、读出错误率越低，越有助于提升量子程序的执行可靠度。在超导量子芯片中，CNOT操作错误率和读出错误率是导致错误的主要因素。因此选取具有更低平均CNOT操作错误率和读出操作错误率的量子位集合，以获得更高的程序执行保真度。

再之，应尽量避免将易发生串扰（crosstalk）问题的两个社区分配给并发量子程序，以缓解串扰错误。由于设备制造缺陷、控制错误等原因，在邻近的一对量子位连接上同时执行的CNOT操作可能发生串扰，导致两个CNOT操作的错误率均发生提升。在社区分配的过程中，为了避免串扰错误，考虑易发生串扰的CNOT对的数量多少比考虑串扰错误的高低更为重要。其原因在于：即使一对CNOT操作的串扰错误较高，也可通过指令调度等技术避免串扰的发生。但易发生串扰错误的CNOT对数过多，会导致需要大量的指令调度操作来避免串扰，导致被延迟执行的CNOT操作增多，量子程序执行时间延长，带来与量子位状态保持时间相关的错误。因此本文优先选取与已分配的社区具有较少易串扰CNOT对的量子位区域进行分配。

c） 跨程序的量子位交换（SWAP）调度。QuOS对并发量子程序映射特点，引入跨程序SWAP操作，即逻辑量子位的交换可以在程序之间进行，克服了仅在单个程序内部SWAP的局限，进而缩减SWAP成本，提升程序可靠度。

本文的前期实践证明，在以下两种情况下执行跨程序SWAP操作，能够比仅允许执行单个程序内部SWAP操作的情况带来更低的量子位调度开销。

第一种情况如图4所示。先前策略单独对每个程序进行量子位调度，不允许跨程序SWAP操作。而QuOS允许同时对多个量子程序进行量子位调度，允许引入跨程序SWAP操作，使得1个跨程序SWAP操作可替代2个程序内SWAP操作^[25-26,81]。

图  4  跨程序SWAP操作可替换2个程序内SWAP操作

第二种情况如图5所示。先前策略的最短SWAP路径被已映射的量子程序遮挡，需3步SWAP操作才能使量子位q1，q5相邻。而QuOS采用跨程序SWAP操作，可采取捷径，仅需1步SWAP即可达到相同目的^[25,26,81]。

图  5  跨程序SWAP可取捷径

QuOS包含一种新的量子位调度机制，对多个并发量子程序同时进行调度，并充分利用跨程序SWAP操作，降低量子位调度的开销，具体包括以下几项内容：

首先是启发式搜索空间设计。本文以首层CNOT门操作是否存在紧邻的后继CNOT为判断依据，筛选首层CNOT门操作中的关键门操作。优先处理关键门操作可帮助快速更新首层CNOT门操作，缩小映射后的量子线路深度。因此限定启发式搜索空间为：仅与关键门操作涉及到的物理量子位相关的SWAP操作。

其次是启发式函数设计。最近邻成本函数（NNC）通常可作为启发式函数的一部分，它代表门操作集合中所有CNOT操作的平均SWAP路径长度，可帮助采用最少的SWAP操作完成量子位调度。除此之外，QuOS把允许和不允许跨程序SWAP两种情况下的最短SWAP路径长度差值加入启发式函数，鼓励执行能够采取捷径的跨程序SWAP操作。

最后QuOS加入对串扰错误的考虑。本文分析了引发串扰错误的主要原因在于同时执行的CNOT门操作，以及量子位调度过程中引入的SWAP操作。为了缓解串扰错误，QuOS改进量子位调度的启发式搜索过程，每次迭代不再只选取具有最低（最优）启发式函数值的SWAP，而是依据启发式函数值由低到高选出一部分较优的SWAP，再从中选择串扰错误最低的SWAP操作。

d） 针对新3D架构量子芯片的映射。对于新型3D量子芯片，可充分利用量子位的三维排布和更多的量子位间相互连接，优化初始分配和SWAP策略，缩短SWAP路径，提升程序执行保真度。本文拟利用具有高度数的物理量子位，对3D量子芯片上量子程序的初始分配进行优化。对于量子程序中的一个逻辑量子位，如果与之交互的逻辑量子位数目较多，那么将其分配至一个具有较高度数的物理量子位上是降低SWAP成本的有效方法。这样做会使更多的CNOT操作涉及到的逻辑量子位的映射位置直接相邻，无需在执行前插入SWAP，从而降低量子位调度过程中的SWAP成本。

2、QuOS的设计 -- 多量子程序并行的调度

面对不同的量子芯片特性及多样化的量子程序，QuOS具备自适应的量子任务调度机制，自动控制任务单独执行或并发执行多任务。该机制筛选可并发执行的最优量子程序组合，在提升量子计算机的通量和昂贵的量子位的资源利用率的同时，避免量子程序执行准确度（Fidelity）的大幅下降。

QuOS将采用自适应的、按需调度的量子程序调度机制，支持根据系统或用户需求，按需选择最优量子程序组合执行。技术方案具体涉及以下两项内容。

首先是调度器的优化目标选择。QuOS根据用户的输入，或自动检测系统当前的任务，将提升通量或提升量子程序执行保真度作为目标。如VQA量子算法包括数百个串行的、重复的、独立的执行和测量过程，每个独立的执行和测量过程可被当做一个单独的量子程序进行调度。此时设置调度器以提升通量为优化目标可对VQA算法进行加速。而如果需要保证一个量子程序的保真度，调度器可以单独映射该量子程序，避免并发量子程序对其造成干扰。

其次是调度器的调度逻辑。调度器首先选取调度队列中的首个量子程序作为待执行任务。接着按照与首个量子程序的匹配度顺序，检查调度队列中是否存在其他量子程序能够与该量子程序并发执行，且造成的成功率的损失低于阈值。若存在此类程序，则将它们与该量子程序同时映射到量子计算机上执行；否则，单独映射并执行该量子程序。其中，与该量子程序深度相近，且量子位数较少的程序，具有较高的匹配度。

本文首先总结了量子计算系统的发展。随后，提出了一种量子操作系统软件栈的设计方案（QuOS）。随着量子计算机逐步进入人们的视野，笔者认为现在已经到了需要认真研究量子操作系统及相关软件的时刻。虽然量子计算机和经典的冯诺依曼计算机架构有着本质的区别，但是业界关于经典计算机操作系统的研究已经有了丰富的经验和丰厚的积淀，“他山之石，可以攻玉”。本文认为人们对经典操作系统的设计经验有些同样也适用于对量子操作系统的设计，并做出了尝试和改进。希望未来有更多的科研工作者投入到相关的研究中来。