理解量子路线编译的复杂性
Understanding the Complexity of Quantum Circuit Compilation
什么是量子线路（quantum circuit?）
量子线路相对说来可能是一件棘手的事情。在某些计算问题中，量子计算有望比传统计算更快，但并非所有计算问题。量子计算机能否比传统计算机更快取决于所解决问题的性质。当加速可能时，加速的幅度也取决于问题的性质。例如，在某些类型的问题中，量子计算的求解时间可以通过经典计算减少到大约求解时间的平方根。也就是说，在经典计算机上需要一百万次操作的问题可能需要在量子计算机上进行1,000次操作。
什么是量子比特（Qubit）
量子计算机中的基本存储器单元是量子比特（qubit），它是经典计算机上位的概括。经典位可以采用两个不同的值，0和1. 在任何给定的时间里，只能有一位具有这两个值中的一个。因此，有点类似于放在桌子上的硬币：它可以处于头像的状态（我们可以认为相当于设置为0的位）或者处于印花的状态（设为1）。相反，量子比特可以具有比0和1更多的值。在给定时间，量子比特的状态可以是0和1的组合，称为量子叠加（Superpostion）。使用硬币是类比，叠加类似于在空中旋转的硬币。非正式地说，就像量子比特同时处于两种基本状态（0和1）。更正式地说，叠加是基本状态0和1之间的加权组合（weighted combination ）。
量子算法（quantum algorithms）如何工作的？
量子算法通过在量子比特子集上应用量子运算（称为量子门，即Quantum gate）来工作。量子门类似于经典程序中的指令。使用门表示的量子算法称为量子线路。
目前的量子计算模型要求量子算法被指定为理想硬件上的量子线路，忽略了可能特定于实际硬件的细节。这使得量子算法在不同类型的硬件上更具可移植性，并且它允许程序员专注于问题的解决方案，而不是特定于给定硬件的细节。
因此，需要将由人类专家编写的量子程序转换为给定量子计算机可以执行的表示。这被称为量子线路编译（QCC，quantum circuit compilation ）。请参见图中的插图。编译量子电路需要添加额外的门，这些门将量子比特的状态移动到期望门可以在实际量子处理器的物理约束下作用于它们的位置。在某种程度上，这类似于如何将经典程序从程序员理解的语言（例如，C ++）编译成硬件可以执行的二进制表示。
在可能对应于给定量子程序（Quantum Program）的许多编译电路中，具有较短执行时间的线路是优选的。部分原因是称为退相干（decoherence）的现象：由于诸如与物理环境的相互作用等因素，量子位状态可能在短时间后被改变。例如，商业版的IBM 20-qubits环境l里具有大约100微秒的相干时间。具有较短执行时间的电路可以在退相干发生之前完成其运行。
但是，以最短的可能执行时间计算编译线路可能需要付出代价。具体地说，问题在于是否可以有效地执行这种编辑（即，在相当短的时间内）。到目前为止，这是一个悬而未决的问题。
最近，IBM Q团队在组合SoCS 2018研讨会上发表了一篇名为“关于量子线路编译的复杂性（On the Complexity of Quantum Circuit Compilation）”的文章.在这项工作中，我们对以最短的执行时间计算编译电路的难度进行了全面的理论分析。
我们发现在某些类型的电路上，是完全NP问题。换句话说，对于问题的一些（但不是全部）实例，可能很难以这样的方式编译输入电路，即它们将在尽可能短的时间内执行程序。
这是理解编译量子线路的计算复杂性的重要一步，以便它们可以在给定的硬件配置上有效运行。未来的工作可以研究其他类型的量子电路编译问题的复杂性。此外，重要的是要探索具有良好执行时间但不一定是最佳的编译线路是否可以使用有界次优算法一直有效地计算。这些算法可以保证解决方案与不超过给定阈值的最佳解决方案之间存在一定的差距。
我们关于量子线路编译问题复杂性的理论结果与Qiskit非常相关。更具体地说，Qiskit Terra提供了量子软件堆栈的基础，以优化特定物理量子器件的量子电路。因此，我们设想持续努力开发更有效的近似编译算法，该算法也提供次优保证。 要了解有关量子原理的更多信息或在实际量子计算硬件上创建和运行算法，请访问 IBM Q Experience。
#Qtum_Work英文地址：https://www.ibm.com/blogs/research/2018/08/understanding-complexity-quantum-circuit-compilation/
本文来自投稿，不代表Qtumist 量子客立场，如有转载，请注明出处：https://www.qtumist.com/post/3864
QTUMIST ◆ 量子客
www.qtumist.com