前提知识

希尔伯特空间(Hilbert Space)

希尔伯特空间是复向量内积空间。

内积空间是两个向量上的函数并返回一个标量的二元运算，它的结果是欧几里得空间的标准内积。

一个量子系统的态空间一般用有限维度的Hilbert空间来表述，即可以用来表述量子系统的各种可能的量子态。

量子两个基本状态

叠加态

量子叠加态就是一个量子能在同一时间处于两种不同属性0和1的状态，而对于经典物理中，一个粒子只能处于一种状态，如要么左旋，要么右旋。

纠缠态

量子纠缠态，就是满足一定条件的情况下一个量子的行为将会影响到另一个量子的状态。即其中一个量子被操作改变而发生状态变化时，比如进行量子观测时，一个量子被观测为左旋。则另一个量子其状态立即发生相应的状态变化。而两个量子之间不存在一定相同或者相反的绝对规则。因此两个被纠缠的粒子可以是状态相同，也可以是状态相反。

Bloch 球面

百度百科

从任意纯态出发，有： $$ |\psi\rangle=\alpha|0\rangle+\beta|1\rangle, \alpha, \beta \in \mathbb{C}, \quad|\alpha|^{2}+|\beta|^{2}=1 $$ 可设： $$ \alpha=\cos \theta e^{i \delta} $$

$$ \beta=\sin \theta e^{i(\delta+\phi)} $$

有： $$ |\psi\rangle=\cos \theta e^{i \delta}|0\rangle+\sin \theta e^{i(\delta+\phi)}|1\rangle= e^{i \delta}\left(\cos \theta|0\rangle+\sin \theta e^{i \phi}|1\rangle\right) $$ $e^{i \delta}$称共同相位，可以省略。$e^{i \phi}$称相对相位。有： $$ |\psi\rangle=\cos \theta|0\rangle+\sin \theta e^{i \phi}|1\rangle $$ 因$cos\theta$和$sin\theta$为长度，所以都为非负实数，可以确定： $$ 0 \leq \theta \leq \frac{\pi}{2} \Rightarrow 0 \leq 2 \theta \leq \pi, \quad 0 \leq \phi<2 \pi $$ $x=\sin 2 \theta \times \cos \phi$的所有分布在三维空间中画出来，即布洛赫球面。 $$ \begin{array}{rlrl}{x} & {=} & {\sin 2 \theta \times \cos \phi} \ {y} & {=} & {\sin 2 \theta \times \sin \phi} \ {z} & {=} & {\cos 2 \theta}\end{array} $$

欧拉公式

$e^{ix}=cosx+isinx$

得到一个模为1的复向量,$x$是向量的角

k-core

一个图G的 KCore 是G的子图
这个子图的每个顶点的度≥K

计算方法

每个顶点记录is_delete，current_degree
如果一个顶点的度数小于k，则从图中删除该顶点，给邻居发消息
顶点收到消息之后，更新自己的度。

论文阅读

待了解

希尔伯特空间
Bloch球面
k-core算法

问题

noisy是什么意思？
SWAP操作如何理解？和量子纠缠的关系是什么？
baseline mapping policy中
普通方法与本论文的本质区别在哪里？普通方法也知道有错误率，但是认为普通方法的错误率是全局一致的。
Algorithm2 中的量子位活动是什么？
error-configs？
量子程序中的Cx代表什么意思?
Fig15中的执行过程是怎么回事？其中的SWAP操作为什么是3次方的失败概率？

概念

NISQ： Noisy Intermediate Scale Quantum computers，噪声中尺度量子计算机，具有10至1000量子位。容错率低，但能为量子应用提供一些优势。
Qubit-Allocation：处理程序量子位到物理量子位的映射问题。
Qubit-Movement：选择将一个量子位状态移动到另一个量子位状态的路径的问题
量子纠缠：两个暂时耦合的粒子，不再耦合之后彼此之间仍旧维持的关联。通过“2量子位操作完成”。如果两量子位不存在connection，可以通过swap操作，使得两量子位挨在一起，之后通过2量子位操作完成量子纠缠。
VQM：Variation-Aware Qubit Movement，可变感知量子位移动
VQA：Variation-Aware Qubit Allocation，可变感知量子位分配
qubit device：量子位设备
QEC：Quantum error correction codes，量子位防止错误的方法：量子误差校正码
SWAP操作：量子计算机中，用来交换两个量子状态的操作，即量子纠缠
data qubit：量子位数据
phycal qubit：物理量子位
PST：Probability of Successful Trial，成功试验概率，表示程序在没有任何错误的情况下成功完成的概率，用于度量量子计算机性能
量子门 (Quantum gate，或量子逻辑门)是一个基本的，操作一个小数量量子位的量子线路，使用酉矩阵表示。
Coherence Time：相干时间，一个物理量子位保持一个数据所能持续的时间
Operational errorrate：操作错误率定义为在执行操作时引入错误的概率
ANS,aggregate node strength，$A N S=\sum_{i}^{k} d_{i}$ where $d_{i}=\sum_{j}^{N} w_{i j}$
activity，(total number of CNOT operations)
benchmark：标准检查程序
STPT，Successful Trials per Unit Time，单位时间成功尝试次数

摘要

现有量子计算机的不足：容错性不好。造成容错性不好的原因是：

量子位数太少
系统噪声大，工作不稳定

NISQ应运而生（量子位相对较多），本paper研究量子位分配和量子位移动。

不同的量子位和不同的量子位间的连接（link）拥有不同的错误率，这可能会影响量子位元移动和量子位元分配的**决策**。因此作者分析了IBM-Q20的公开可用的特性数据，确实发现了上述差异，确定了设备的变异性对整个系统的可靠性有重要的影响。

为了利用**错误率**的可变性，作者提出了

可变感知量子位移动(VQM)
可变感知量子位分配(VQA)

这些策略可避免较弱的量子位和链接，鼓励更多的操作向较强的量子位和链接发展。

基于IBM-Q20仿真模型，变量感知策略可以将系统可靠性提高1.7倍。基于IBM-Q5，可靠性可高达1.9倍。

介绍

量子计算机：

能够加速求解普通困难问题的求解，如：

素因子分解
模拟物质和化学反应

通过创建纠缠集合状态实现运算，创建纠缠集合所用到的操作是：“两量子位操作”，这个操作只能对有**联系**的量子位元进行。

量子算法

利用叠加和纠缠的性质，依靠量子运算来改变量子位元的状态。

历史

过去20年：从理论模型到被实践
过去2年：各公司设计出了量子计算机蓝图
过去10年：一致性时间（coherence times）从1纳秒上升到了100微秒

量子位

具有易变的特性，因为：退相干和操作错误
具有避免错误的方法，即：QEC，但QEC有不足：需要10-100个物理量子位元来编码一个容错量子位元。当前有数十或数百量子位的计算机因量子位限制，不能使用QEC。

VOM and VOA

VOM

以前的做法是让SWAP次数更少的路径
选择成功率最高的纠缠路径

VOA

以前的做法是选择让SWAP次数更少的的放置位置，这些研究假设了swap代价均等
将数据量子位放置在成功率更高的的物理量子位上

需要考虑量子位设备的多样性，认为SWAP操作代价不等

文章工作

给出了所有20个量子位的相干时间统计量，执行单量子位运算时的误码率，以及在不同量子位上执行双量子位运算的误码率。
证明确实不同的量子位和连接是存在差异的。
提出Variation-Aware Qubit Movement：如果想对两个数据量子位进行纠缠，VQM方法会找出是成功率最高的path，而不是SWAP最小的path
提出Variation-Aware Qubit Allocation：在将数据量子位映射到物理量子位上时，选择最强的链接，提升系统整体的可靠性。

背景和动机

量子计算背景

传统计算机的一个位可看做球体上的南北两极，而一个量子位代表的数据可看做在一个球面**（布洛赫球面）**上的任意一点
量子操作：将一个量子位从球面上的一点移动到另一点
存储和操作量子位是量子算法的关键
量子纠缠是创建有联系的量子位之间的集合状态的操作
量子纠缠通过“二量子位操作”完成，例如控制非门
IBM量子机中，两量子位比特操作通过他们之间的连接环（coupling-link）完成。
超导量子计算机通常不会采用全互联量子位，而是采用一种受限制的网络，如mesh，只在相邻的量子位之间连接。
SWAP操作可以交换邻接的量子位位，能使任意两个量子进行纠缠，SWAP可以通过三个控制非门完成

量子计算机中的错误

很有可能因为量子设备的环境发生变化而产生错误
分类：连贯性错误和操作错误
连贯性错误：量子位只能在有限时间内保持数据，高能状态$(|1\rangle)$总会向低能状态$(|0\rangle)$衰变。与这种衰变相关的时间常量被称为T1相干时间（T1 Coherence Time）。T1表示一个量子位自然放松的时间。T2表示被环境影响的量子位放松时间。
操作错误：量子操作不精确，不完美，可能导致错误。操作错误率定义为在执行操作时引入错误的概率。单量子操作错误率量级：$10^{-3}$，双量子操作错误率量级：$10^{-2}$。本文主要研究双量子操作错误。

近期的量子计算机

QEC可实现错误免疫，但一个容错量子位需要10x-100x物理量子位来编码。现阶段量子位少的量子计算机（NISQ）无法实现QEC。
大程序需要几百万量子位，已存在或近期的量子计算机无法达到。对只需要几十位的量子程序，错误更正无法达到。
NISQ没办法执行错误更正，但能执行有用的工作。
可通过多次执行，根据大数定律可知，一个事件出现的次数与实验总次数比值随着实验次数的增加，趋近于事件的概率。

量子位元之间有限的连通性

若实现量子位全连通，连接需$O(N^2)$，不可行。
连接包括导线、以特定频率工作的谐振器，使连接做到可靠，是一项艰难的任务。因此大多量子计算机使用网格网络。
由于使用网格网络，所以产生了两个子问题：Qubit-Allocation：处理程序量子位到物理量子位的映射问题。Qubit-Movement：选择将一个量子位状态移动到另一个量子位状态的路径的问题。
Qubit-Movement 策略：此策略决定在将数据从芯片上的一个位置移动到另一个位置时应该使用的路由。
Qubit-Allocation 策略：该策略决定程序量子位元到数据量子位元的初始映射。经常通信的量子位元最好放在彼此附近。
本文工作采用Zulehner开发的编译器，对于给定链接的量子程序进行编译，生成指令队列、SWAPs和初始量子位映射。他开发的编译器采用贪婪算法减少SWAP次数，在执行交换操作时，用于qubit移动和qubit分配的基线策略假定统一的成本(特别是可靠性影响)。但是不正确，会有易变性。

分析 IBM-Q20 中的可变性

相干时间分布

标准差是离均差平方的算术平均数的平方根。平均偏差是数列中各项数值和其对应的算术平均数的离差绝对值的算术平均数。

单量子位位操作错误率

IMB量子计算机中的量子位操作是通过在量子位元装置上应用具有一定持续时间和频率的微波信号来实现的。但量子位器件是高度非线性的，微小的扰动或实验条件都会引起器件特性的漂移。
单位操作比双位操作更加稳定。

双量子位位操作错误率

IBM量子计算机中双量子位操作通过在目标设备、控制量子位设备以及连接两者的耦合链路上应用微波脉冲来执行的。与单量子位操作类似，双量子位操作的错误率也会发生变化。有一小部分耦合链路比大多数链路明显不可靠

双量子位位门误差的时间变化

链接的错误率可能随时间变化
强连接保持平均错误率的能力较强，弱连接保持平均错误率的能力较弱

双量子位位门误差的空间变化

不同节点和连接之间的误差率不一样

评估方法

系统级别可靠性的品质因数

以PST作为主要指标

评估基准

微基准是按照比例缩小的大的量子应用和子程序
选取准则：选取了纠缠模式不同的数据集

评估所用的工具

采用基于蒙特卡洛方法的错误注入模拟器
采用NISQ的迭代执行，分析结果模型
错误注入模拟器接收：1.NISQ程序 2.框架、配置和错误率 3. 管理策略
评估了以下方面的失败可能性：两量子位、单量子位、测量操作
对每个数据集执行100万次
错误建模为具有独立概率的不相关事件
映射和编译策略可以被一阶模拟器评估

架构和错误率参数

架构参数规定了量子位的数量和连通性
错误率参数规定了单比特、双比特和测量操作的错误率
文章对coherence错误进行了建模
IBM-Q20的门错误比coherence错误更加严重

量子位移动和分配的基准策略

Zulehner提出的基本映射策略

构建无权图，节点为量子位，边为量子位与量子位之间的连通
采用Floyd算法，计算任意两点之间的最短路径
对输入程序**分层**，使得每一层都包含能够被并行执行的独立操作。分层为： $$ L=\left{l_{0}, \ldots, l_{i}, l_{i+1}, \ldots, l_{n-1}\right} $$
对于每一个分层$l_{i}$，都要找到一个对应的映射$m_{i}$，使得这一层的控制非门都能有足够的物理连通性被执行
为每对相邻层$l_{i}$ 和 $l_{i+1}$找到最优swap操作集合$\left(S_{i \rightarrow i+1}\right)$，**这个操作集合能够将映射$m_{i}$转化到$m_{i+1}$。*搜索时要采用A算法。

可变感知的量子位移动

由于量子计算机的量子位大多数以网格状分布，因此两点之间沿任意路径的曼哈顿距离相同。
现有的方法采用插入的交换数作为代价函数。但文章的方法是将量子位从源移动到目标的总体失败率。但在失败率相同的时候，选择最小的交换数。
VQM利用了基线的局部性保留特性，同时使用了一种可变感知的启发式。

VQM算法流程

初始化权图，边的权值是失败概率，使用N次Dijkstra算法，获取任意两点之间的纠缠最小失败概率。
计算每个量子位的节点强度$d_{i}$，$d_{i}=\sum_{j}^{N} w_{i j}$
将输入程序分层，使得每一层都包含能够被并行执行的独立操作。分层为：

$$ L=\left{l_{0}, \ldots, l_{i}, l_{i+1}, \ldots, l_{n-1}\right} $$

找映射，量子位节点强度更高的量子位会被优先选中。
选择能够根据最小失败概率矩阵，找到最优交换操作。使用A*算法进行搜索，启发函数使用可靠性消耗和MAH（最大附加跳数）的加和。

MAH：Maximum Additional Hop，用于限制最大跳数，如果超过最大跳数的做法，即使cost低，也不予考虑。

可变感知的量子位分配

普通方法只注意分配过程使SWAP数最小，而VQA方法要使出错概率最小。
基线策略从精心选择的初始映射开始，然后尝试收敛到具有最小SWAP数量的配置。
VQA方法将最频繁使用的量子位分配到最稳定的物理量子位上，并保持局部性。VQA方法通过采用最可靠的初始映射，限制最常用的量子位到最可靠的连接上来实现。VQA方法通过分析程序中的前N条指令、跟踪控制非门操作涉及的对象，来估计最常被纠缠的量子位。

VQA算法流程

找到具有k个节点的具有最高ANS的子图，ANS等于k个节点的临边权值和的和
通过计算前t层的每一个量子位的控制非门数，找出***量子位活动***
优先映射量子位活动多的量子位到子图上
用基线算法找到层$l_{i}$ 和 $l_{i+1}$的SWAP数

VQA使用K-core算法来计算最强的子图集，该算法递归删除度数小于k的节点。

VQA对系统可靠性的影响

VQA具有高活动性(CNOT操作总数)的程序量子位元到具有较高节点强度的物理量子位的映射。这提高了在少数几个qubit对之间重复纠缠操作的工作负载的可靠性。

和IBM编译器的比较

baseline比原始IBM编译器提升了4倍，VQA和VQM可提升7倍

每天不同数据的比较

错误率变化程度大的数据，PST相对较高，反之则较低

对错误率大小变化的敏感性

错误率无论大小，总会有变化，总是适用。
VQM+VQA提供了显著的好处，这些好处随着相对变化的增加而增加。
改变了两个变量：一个是平均错误率，一个是Covariation（相关变异）

在IBM-Q5上的测试

two-qubit error rate is 4.2%, the worst link-error is 12%. We run each experiment with 4096 trials and analyze the output log to compute the PST for each program and policy.

分区的量子计算机

在实际所需的量子位比物理量子位少一半甚至更少的时候，探究分区是否有意义。
产生了2 copy mode
同时运行的两个副本每次可以提供两倍的无错误试验次数。但是这限制了物理量子位的映射的选择。因为单次实验可以选择连接较强，错误率较低的物理量子位进行映射，而两个副本导致了不得不选用连接较弱、错误率较高的物理量子位进行映射。

局限性分析

benchmarks可能不典型
错误模型可能假设有问题

总结

强调了量子位和量子位之间的连接的错误率中的可变性
提出了VQM，能使量子位的移动有最低失败概率
提出了VQA，能将程序量子位映射到更健壮的物理量子位上
提出了一套评价方法论来评估设备变化和管理策略对量子计算机系统级可靠性的影响

论文总结和评价

关于量子计算的知识

量子计算中，量子计算机是不可靠不稳定的。可能发生操作错误和保持性错误。操作错误分单比特位操作和双比特位操作。严重程度：双比特位操作错误>单比特位操作错误>保持性错误。

量子计算通过多次执行量子程序，记录每次的观测结果，根据大数定律，正确事件出现的次数与总试验次数的比值会趋近于该事件的概率。

简介

传统噪声中尺度量子计算机（NISQ, Noisy Intermediate Scale Quantum computers），由于量子位太少（10x-100x），不能够采用QEC来执行错误检测和错误更正，因为QEC需要10-100个量子位来编码一个错误检测位。那么该如何有效提升量子计算机的可靠性呢？

作者通过分析IBM-Q20的特征数据发现，量子位和量子位之间的连接的错误率是不完全一致的，是多变的。为了利用这一特性，作者提出了VQM和VQA，能使程序量子位被分配到更好的物理量子位上，能使swap操作更多地发生在更可靠的链接上。

基线策略

VQM和VQA是在基线准则上进行改进所得到的策略。

基线策略采用SWAP次数作为价值参数。

前提假设：所有的SWAP操作代价相同

基线映射策略

初始化无权无向图
使用最短路算法，计算任意两点纠缠所需最少的swap次数
程序指令分为n层，不同层包含不同的指令，不同层之间可以并行执行。
遍历所有的层，对于每一层，都要找到从程序量子位到物理量子位的映射，这样每一层的CNOT就可以有足够的物理连接被执行了。
对于每两层中间，通过A*搜索算法，以成本函数和基于曼哈顿距离的启发函数，搜索最优的SWAP集合，能使第一层的程序量子位到物理量子位的映射转化到第二层程序量子位到物理量子位的映射。

存疑：

量子程序中的指令是什么样子的？

分层是什么意思？分层依据的准则是什么？

这里的分层，每一层的所包含的程序量子位都完全一样？否则第5步中无法通过SWAP方法来把第一层的映射改为第二层的映射。

VQM

可构造无向有权图，采用最短路算法，计算距离矩阵
对每一个物理量子位计算节点强度，节点强度等于节点上的所有连线的权值
将输入程序分层
每一层寻找映射，映射要优先选择介电强度高的节点
找到从第一层映射到第二层映射的最优swap集，依据标准是最短路矩阵，有最大跳数的限制

VQA

找一个具有k个节点的子图，子图应当具有最大的ANS，ANS是子图中所有节点的边权的和的加和。
在前t层中，通过计算CNOT数，计算每个量子位的量子位活动
映射程序量子位到物理量子位，优先映射量子位活动较高的程序量子位
运用基线策略，找到层$l_i$和层$l_{i+1}$之间的映射