A Quantum Computational Compiler and Design Tool for Technology-Specifific Targets

前提知识

酉矩阵

一个矩阵的共轭转置和它的逆相等。

即： $$ U^{-1}=U^{\dagger} $$

$$ U^{H} U=U U^{H}=E_{n} $$ 其中，$U^{H}$为$U$的共轭转置，$E_n$为n阶单位矩阵。

不理解

Local optimizations based on removing partitions of gates that equal the identity function are implemented recursively until technology library cost function cannot be further reduced.（P6）
single-target gate？

关键词汇理解

technologically-independent：技术无关，即没有映射到实际量子计算机，不考虑量子计算机实际物理体系结构的
technology-dependent ：考虑量子计算机体系结构的
Quantum Multiple valued Decision Diagram (QMDD)，量子多值决策图
quantum information processing（QIP），量子信息处理
quantum operator=quantum gate
connectivity tree reroute algorithm（CTR），连接树重新路由算法
switching functions，可逆的二进制转换函数，即量子电路

摘要

为了充分利用量子计算机性能，编译器需要对细节做优化，将量子程序映射到实际结构上。现有的大多数技术并没有考虑量子计算机本身的特点。我们的方法基于实际架构的约束来执行。这个工具基于实际结构执行优化，具有高质量的架构相关的映射结果。并进行了数学方面的等价检查，使我们的映射结果与原有算法等价。

简介

QC体系结构各不相同，需要特殊的技术使合成工具能够将广义量子线路映射到特定QC体系结构上。这个工具需要重新配置一个量子线路，让一个量子计算机上的可执行的量子线路映射到另一个设备上。该技术促进了量子逻辑自动转化工具的发展、硬件编译器的发展。技术利用形式等价性验证产生的物理映射结果和最初的逻辑线路是否相等。该技术也可以自动优化逻辑线路。

过去已经产生了可逆逻辑、考虑架构限制的网格模型量子结构、单双量子门。

此处讨论的特点是：

逻辑量子线路被映射到物理量子线路的体系结构上。
形式等价性检查，确认生成的最终电路在功能上与原始形式等价。

通过形式验证达到了高效的量子线路合成和映射。编译过程中，实现了量子多值决策图（QMDD），用于电路等价性检查。

原型工具实现了对原始量子线路图到实际量子计算机上的量子线路图的映射、优化和验证转换。文中以IBMQ系列量子计算机为例，是因为这些计算机提供了他们具体的架构，但本文工作也可以用于其他的架构，因此是模块化的。

第2节提供了量子逻辑，计算和操作的背景信息，并介绍了QMDD数据结构。第3节描述了IBM量子机器和工具。第4节概述了基于量子计算机物理体系结构的量子逻辑综合和编译的方法。第5节回顾了实验结果。第6节得出了当前研究的结论，并详述了量子合成和编译工具的未来发展和改进。

背景

量子计算

叠加态和纠缠态在经过观测后消失
量子算子表示量子态的特定时间演化，从而有目的地转换量子位状态，从而产生有意义的QIP。如果将量子算法建模为一个电路，那么量子运算可以看作是量子逻辑门。
量子位多，退相干性高，superconducting solid-state qubits是目前效果最好的量子位实现手段。

量子费用

维持量子在计算中的稳定性是非常重要的
减少操作数是非常重要的
提出了量子位费用，其中T门为三比特位操作，额外成本设为0.5，C门额外成本为0.25，量子成本越高说明退相干可能性越大。 $$ q_{c o s t}=0.5 \times t+0.25 \times c+a $$

可逆逻辑

可逆逻辑指的是理论上可以通过反向执行算法来恢复输入信息的实现
为了实现可逆性，要求输入和输出端口相同，输入输出有闲余端口用于维持可逆性。编译和优化工具的优化目标是：在维持可逆性的前提下，最小化闲余端口。
与QIP操作对应的状态转换被建模为酉转换，及具有可逆性。
希望可以实现用户输入不可逆算法，由工具转换为可逆。
存在将二进制切换函数变成可逆函数的算法，一旦转换了切换功能，就可以将它们转换成QIP电路或QC程序，以便在量子机器上进行评估。
所有的QIP和QC过程在逻辑和物理上都是可逆的，这是量子力学假设和公理的结果。
对应于QIP操作的状态变换是酉变换。
一种方法：对输入的以ESOP形式表达的转换函数进行转换，转换为可逆的Toffoli流的形式。占用时间短。
后来的一项工作，包含了ESOP的工作，使用决策图（DD，decision diagram）来进行表示。一个顺序二维决策图用一堆不相交的立方体表示了一个不可逆函数。
现有的量子合成工作使用诸如ESOP和DD表示之类的技术将经典规范转换为可逆逻辑[2,6]，但由于可逆逻辑在实际QC上是不可实现的，因此产生的输出与技术无关。

量子多值决策表

对于n个量子位的逻辑门需要的酉矩阵大小为$2^n\times 2^n$
QMDD可以用有向无环图表示量子逻辑门，类似空间八叉树。
量子多值决策表被用于等价性检测，因为对于初始量子线路和映射到物理量子线路上的量子程序，只要操作顺序不变，量子多值决策表是相同的。

IBM Q

可以讲IBM Q系列表示为一个字典，键为CNOT的控制位，值列表为CNOT控制位对应的目标。

设计了一个称为“耦合复杂度”的度量，用于描述物理量子位的耦合复杂度。
将耦合复杂度定义为耦合映射中发现的允许CNOT耦合数量与量子机器的所有量子的二排列之比。越接近1，两个量子位互联的可能性更高。

ibmqx2 = {0:[1,2], 1:[2], 3:[2,4], 4:[2]}

$complex=\frac{6}{C_5^2}=\frac{6}{20}=0.3$

量子逻辑合成方法

最终量子程序要以量子汇编语言展示。
前端接受多种输入，包括经典的开关函数，前端都会对其进行处理。
前端的处理结果是一个与实际物理量子设备无关的可逆表示。
前端生成的可逆表示被后端的设计工具处理。
后端进行转化和优化，映射到一个具体的物理量子机器上。
后端可以进行多量子位门的分解，也进行了两量子位操作的优化。
多量子位操作在物理上难以实现，分解的方法是必要的。树的数据结构有助于为CNOT找到最短的SWAP路由。
CRT算法被用来自动路由不符合硬件条件的CNOT操作。基于耦和图的树结构决定了SWAP操作的最短路径。
SWAP操作继续移动控制量子位，直到可以在指定目标上执行所需的CNOT操作。在执行CNOT操作之后，控制量子位反向遍历SWAP路径以返回其原始位置，以便保留电路中的原始量子位分配。
构建CRT 树时，只要两者之间有连接，即可构建CRT树枝，因为CNOT其实可以通过四个H门进行转向。
后端构建基于实际架构的QASM，主要符合两个方面：1.符合物理架构2.最小化量子代价
实现了以下的映射和优化过程：1.CNOT可翻转。2.CTR用于路由不直接连接的量子位。3.广义Toffoli门被分解为Toffoli流。4.将Toffoli操作分解为一个和两个量子位操作符。5.在不能进一步降低技术库成本函数之前，将递归地实现基于删除等同于标识函数的门的分区的本地优化。6.在不能进一步降低技术库成本函数之前，递归地实现基于移除逻辑上相同的电路标识可以最小化的门分区的局部优化。
所有的综合优化程序完成后，调用形式验证，使用QMDD进行等价测试。非常重要，因为验证了工具的转换和优化不会改变算法逻辑。

实验

负责映射和优化，用于合成和编译的后端工具使用Python完成。
工具的目的是使用经典的计算方法，而不是模拟量子算法，来合成依赖于技术的算法。
工具可以对IBM Q系列设备、和自己提出来的96qubits设备进行计算，可直接在个人电脑上进行计算。
benchmarks：Optimal Single-target Gates，大小为3-6。他们中药师因为他们被作为查表法的的重要部分
单目标门可以被分解为一个和两个量子位操作。作为独立于物理线路的.qc文件被输入到合成工具中。
映射到模拟器时，是和物理线路无关的。
模拟器的结果是一个技术独立的线路，考虑了T数和总门数，没有考虑多比特位操作要放在哪。
在没有被物理线路限制的情况下，基准线路的量子位和连接已经是最精简的了，经过基于费用的优化和映射，其门数和成本函数并不会减少。
不被物理结构支持的门需要被分解或重路由，具有低“耦合复杂度”的线路往往需要更多的门来实现技术相关的映射。
映射结束后，结果线路可能被内建的局部优化器优化。