1. 首页
  2. 量子模拟

QC观察丨理解量子电路编译的复杂性

QC观察丨理解量子电路编译的复杂性
IBM Research – Ireland《量子电路编译复杂性》的作者,从左到右:Akihiro Kishimoto,Radu Marinescu,Adi Botea。

什么是量子电路?

量子电路可能是一件棘手的事情。在某些计算问题中,量子计算有望比传统计算更快,但并非所有计算问题。量子计算机能否比传统计算机更快取决于所解决问题的性质。当加速成为可能时,加速的幅度也取决于问题的性质。例如,在某些类型的问题中,量子计算的求解时间可以通过传统计算减少到大约求解时间的平方根。也就是说,在传统计算机上需要1,000,000次操作的问题在量子计算机上可能只需要进行1,000次操作。

什么是量子比特?

量子计算机中的基本存储器单元是量子比特(qubit),它是传统计算机上比特(bit)的概括。传统的比特可以采用两个不同的值0和1。在任何给定时间,一个比特具有这两个值中的其中一个。因此,有点类似于在桌子上的硬币:它可以处于头像向上(我们可以认为相当于比特设为0)或者处于头像向下(比特设为1)的状态。相比之下,量子比特可以有比0和1更多的值。在给定时间,量子比特的状态可以同时是0和1的组合,称为叠加。使用我们的硬币类比,叠加类似于在空中旋转的硬币。非正式地说,就像量子比特同时处于两种基本状态(0和1)。更正式地说,叠加是基本状态0和1之间的加权组合。

量子算法如何工作?

量子算法通过在量子比特子集上应用量子运算(称为量子门)来工作。量子门类似于经典程序中的指令。使用门表示的量子算法称为量子电路。

目前的量子计算模型要求量子算法被指定为理想硬件上的量子电路,忽略了可能特定于实际硬件的细节。这使得量子算法在不同类型的硬件上更具可移植性,并且它允许程序员专注于问题的解决方案,而不是特定于给定硬件的细节。

因此,需要将由人类专家编写的量子程序转换为给定量子计算机可以执行的表示。这被称为量子电路编译(QCC)。请参见下图中的插图。编译量子电路需要添加额外的门,这些门将量子比特状态移动特定的位置,在这些位置上预期的门可以在实际量子处理器的物理约束下作用于量子比特。在某种程度上,这类似于经典程序如何从程序员理解的语言(例如,C ++)编译成硬件可以执行的二进制表示。

QC观察丨理解量子电路编译的复杂性

在可能对应于给定量子程序的许多编译电路中,具有较短执行时间的电路是优选的。部分原因是称为退相干的现象:由于诸如与物理环境的相互作用等因素,量子比特状态可能在短时间后被改变。例如,商业IBM 20-qubit环境具有大约100微秒的相干时间。具有较短执行时间的电路可以在退相干发生之前完成其运行。

但是,以最短的可能执行时间计算编译电路可能需要付出代价。具体而言,问题在于是否可以有效地执行这种编辑(即,在相当短的时间内)。到目前为止,这是一个悬而未决的问题。

最近,IBM量子计算研究所爱尔兰团队在2018年SoCS组合搜索研讨会上发表了一篇名为《关于量子电路编译的复杂性》的文章。在这项研究工作中,该团队对以最短的执行时间计算编译电路的难度进行了全面的理论分析。

他们发现在某些类型的电路上,问题是非完全多项式(NP-complete)。换句话说,对于问题的一些(但不是全部)实例,可能很难以这样的方式编译输入电路,即它们将在尽可能短的时间内执行程序。

这是理解编译量子电路的计算复杂性的重要一步,以便它们可以在给定的硬件配置上有效运行。未来的工作可以研究其他类型的量子电路编译问题的复杂性。此外,重要的是要探索具有良好执行时间但不一定是最佳的编译电路是否可以使用有界次优算法一直有效地计算。这些算法可以保证解决方案与不超过给定阈值的最佳解决方案之间存在一定差距。

关于量子电路编译问题复杂性的理论结果与Qiskit非常相关。更具体地说,Qiskit Terra提供了量子软件堆栈的基础,以优化特定物理量子器件的量子电路。因此,该团队设想持续努力开发更有效的近似编译算法,该算法也提供次优保证。

要了解有关量子原理的更多信息或在实际量子计算硬件上创建和运行算法,请访问IBM Q Experience。

本文是《量子计算前沿》基于相关资料原创编译,并整理在量子客(Qtumist.com)上发布。

请尊重原创,转载须征求同意 !

详情可关注微信公众号:量子计算前沿,订阅更多!

 

 

本文由量客特约作者撰写,如若转载,请联系该作者获取授权。转载请注明出处:https://www.qtumist.com/post/3420

发表评论

登录后才能评论