（图片来源：网络）
俄勒冈健康与科学大学和英特尔公司发布在ArXiv网站的一份报告《生物学和医学量子优势前景》[1]显示，如果实现广泛的量子优势，将大大有利于某些医学和生物学研究。该报告指出，追求卓越量子算法的优势之一是开发更好的经典算法和混合量子-经典算法。
该报告指出，随着第一代NISQ(含噪中等规模量子)设备从实验室进入云端，现在是生物学和医学领域的计算学家开始探索量子方法可能给他们的研究工具箱带来的价值的大好时机。
过去三十年里，生物学和医学已经发展成为高度定量的领域。然而，尽管计算方法和高性能计算(HPC)环境的扩展促进了实质性的进展，但对理解生物和临床系统的能力的基本限制仍然存在。
系统复杂性就是一个例子。实用算法通常通过简化框架来管理系统复杂性，导致现有的计算模型往往无法捕捉和协调重要的系统动力学。如果能够制造出足够强大的量子计算机，有望从根本上降低算法复杂性。反过来，也将以更高的效率模拟许多困难的问题，这可能会减少计算时间并提高实际模型的保真度。
第二个限制是规模。仅就医疗保健而言，2013年就产生了多达153 EB的数据，预计复合年增长率为48%，根据这一增长率推断，2020年产生的数据可能超过2300 EB。生物学中的高通量测序革命产生了大量高度复杂的基因组、表观基因组、转录组、蛋白质组和代谢组数据类型(以及其他数据类型)。这些海量数据资源对于在二次分析和再现性研究中重复使用高价值数据至关重要。然而，即使广泛使用HPC基础设施，大型生物信息学和计算生物学工作流通常也会持续数天、数周或更长时间。
虽然预计量子计算技术不会在短期内解决可扩展性限制，但是从长远来看，FTQC(容错量子计算)设备可能会为其中一些挑战提供部分解决方案。
如何定义量子优势？
我们如何从理论角度定义量子优势？该报告指出，理论上的量子优势由四个关键属性定义：
1.问题：一个正式的计算问题。
2.算法：一种经典算法和一种量子算法，每种算法都解决计算问题。
3.资源：经典算法和量子算法消耗的一个或多个资源，如时间、空间或数据。
4.界限：经典算法和量子算法的资源消耗的分析界限(例如，最坏情况下的时间复杂度界限)。
理论上的量子优势可以根据两个因素进行分类(如图1)。第一个与计算问题的经典难度有关，它由最著名的经典算法或可证明的上界定义。具体来说，计算问题可以根据它的经典算法复杂度(通常针对最坏情况输入)是多项式还是超越多项式分别划分为简单问题和困难问题。第二个因素与量子算法相对于经典算法的优势大小有关。通常这些优势来自计算资源复杂度的降低。与算法复杂度一样，优势的大小也可以分为多项式或超越多项式。
注：如果一个算法的时间T(n)没有任何多项式上界，则称这个算法具有超越多项式(superpolynomial)时间。
这里需要明确的是，“容易”和“困难”仅指经典的可计算性；它们不是指实际量子优势的可获得性或实现量子方法的困难。
图1 左上：多项式在经典困难问题上的优势。左下：多项式在经典简单问题上的优势。右上：超越多项式在经典困难问题上的优势。右下：超越多项式在经典简单问题上的优势。
量子优势潜在可行性
有关量子硬件方面各种量子优势潜在可行性的概述如表1所示。
表1 量子优势潜在可行性。注：表中数字为文献中的算法，可在报告原文查看。
追求NISQ优势
随着混合-量子经典方法的发展，理解量子优势及其计算基准变得更加重要。许多为NISQ设备开发的混合方法可以被称为变分量子算法(VQA)。一般来说，VQA利用三个基本组成部分：i)参数化量子电路(PQC)，ii)目标函数，以及iii)经典优化器(图2)。例如，变分量子本征求解器(VQE)和许多变分QML(量子机器学习)算法。
至关重要的是，这些算法在实现和应用中具有很大的灵活性。
图2 VQA的示意图。
如图2所示，VQA第一步是将问题和目标函数映射到哈密顿算符H。在此映射之后，VQA的执行过程如下：首先，量子电路被初始化，参数化量子电路的第一次执行可被视为初始ansatz。接下来，执行测量以提取计算目标函数损失所需的信息。使用此测量，经典优化器然后计算参数更新以最小化目标函数的损失。该过程迭代进行，直到系统从初始ansatz收敛到最低能量态。该低能态表示哈密顿算符最低能量态的近似和上界。
该报告介绍了有可能追求NISQ优势的四类混合算法，包括变分量子模拟(VQS)算法、变分量子机器学习(QML)算法、量子近似优化算法(QAOA)和量子退火算法(QA)。变分量子本征求解器(VQE)是最常见的VQS算法。通常QML方法可分为以下四类：
1.在具有经典数据的经典设备上执行的学习算法。
2.在具有量子数据的经典设备上执行的学习算法。
3.在具有经典数据的量子设备上执行的学习算法。
4.在具有量子数据的量子设备上执行的学习算法。
生物学和医学量子优势前景
1.模拟量子物理
在原子水平上模拟微观性质和过程是计算生物学研究的一个关键领域。这些任务通常需要量子力学模拟，这对于除了最小的量子系统以外的所有量子系统来说都是经典难题。这些固有的局限性意味着大多数经典方法都是近似的，并且通常提供定性的理解。相比之下，许多相同问题的量子力学模拟是量子计算机的自然任务。在NISQ时代之后，预计大型量子系统的模拟可用于预测经典设备无法有效计算的生化性质和行为。
该报告总结了生物学和医学领域在短期或中期内可能实现量子优势的具体应用，见表2。
表2 生物学和医学领域的预期量子优势。
2.模拟经典物理
经典模拟的量子算法。已经提出了许多有针对性的量子算法，用于寻找低能构象和搜索候选分子，其中许多是专门为蛋白质折叠而开发的。更一般地说，振幅放大可用于探索具有平方优势的经典变量的构象空间。此外，其他优化相关子程序也显示了理论上的量子优势，例如优化场景中的逃逸鞍点。
除了优化和搜索之外，还可以应用QML算法。已经有了一些例子，比如利用量子深度学习来搜索化学空间。考虑到混合量子-经典结构，这些方法的经验优势可能在短期内实现。
最后，近年来解决经典微分方程的量子算法也取得了进展，无论是在一般情况下还是在特定应用中，如有限元法(FEM)或Navier-Stokes。重要的是，在这些量子算法中，有一些用于解决更困难的非齐次和非线性偏微分方程的情况。
经典模拟的前景。关于构象空间的搜索，量子优势是可能实现的。但最近的工作表明，即使是FTQC，提供平方优势的一般方法(例如，振幅放大)本身的价值也可能有限。因此，预计领域知识和附加量子子程序的集成将是实现任何未来优势的关键。
对于QML，特别是混合量子-经典算法，值得进一步探索短期兼容方法以改进经典物理模拟。
最后，导致模拟困难的流体模拟的两个主要方面可能是系统尺寸和湍流。虽然尚不清楚是否可以用量子方法有效地解决湍流问题，但微分方程的量子算法可以降低系统规模方面的复杂度，这在某些情况下可能会带来超越多项式优势。
2.模拟经典物理
经典模拟的量子算法。已经提出了许多有针对性的量子算法，用于寻找低能构象和搜索候选分子，其中许多是专门为蛋白质折叠而开发的。更一般地说，振幅放大可用于探索具有平方优势的经典变量的构象空间。此外，其他优化相关子程序也显示了理论上的量子优势，例如优化场景中的逃逸鞍点。
除了优化和搜索之外，还可以应用QML算法。已经有了一些例子，比如利用量子深度学习来搜索化学空间。考虑到混合量子-经典结构，这些方法的经验优势可能在短期内实现。
最后，近年来解决经典微分方程的量子算法也取得了进展，无论是在一般情况下还是在特定应用中，如有限元法(FEM)或Navier-Stokes。重要的是，在这些量子算法中，有一些用于解决更困难的非齐次和非线性偏微分方程的情况。
经典模拟的前景。关于构象空间的搜索，量子优势是可能实现的。但最近的工作表明，即使是FTQC，提供平方优势的一般方法(例如，振幅放大)本身的价值也可能有限。因此，预计领域知识和附加量子子程序的集成将是实现任何未来优势的关键。
对于QML，特别是混合量子-经典算法，值得进一步探索短期兼容方法以改进经典物理模拟。
最后，导致模拟困难的流体模拟的两个主要方面可能是系统尺寸和湍流。虽然尚不清楚是否可以用量子方法有效地解决湍流问题，但微分方程的量子算法可以降低系统规模方面的复杂度，这在某些情况下可能会带来超越多项式优势。
3.生物信息学
针对生物信息学中的问题，已经提出了少量的量子算法(表2)。其中包括针对NP难问题的FTQC设备开发的理论算法，例如序列比对、利用振幅放大和量子行走的进化树推断。为了使这些理论量子算法实用化，预计这些理论量子算法需要大量的改进和努力。
在短期内，这些改进可能包括i)使用VQA、QAOA或QA框架为NISQ设备改写它们，ii)整合更大的生物学背景。这种类型的工作已经存在于新的基因组装配、序列比对和生物网络推断中。
从长期来看，可以通过优化近期方法和在可能的情况下集成快速量子算法子程序来追求运行优势。可能与这项工作相关的已知量子算法包括回溯算法、动态编程算法、字符串运算算法和微分方程算法。
考虑到这些措施，这些问题的运行优势可能仍然是最难实现的。
此外，量子优势的其他障碍包括i)现有经典启发式算法的复杂性及其解决的许多问题的内在并行性，ii)现有量子硬件和当代研究背景下问题实例的规模，iii)现有经典管道受益于广泛的机构支持和在职人员利益(包括在医疗环境中的广泛临床验证)，以及iv)FTQC基于实践中的振幅放大实现多项式优势的可能先决条件。因此，尽管目前在这个方向上的研究显示了长期前景，并且应该进一步探索，但是这些量子优势中的许多在短期内似乎不太可能。
4.量子机器学习
变分量子机器学习(QML)有望为广泛的生物学研究和临床应用提供一个方法学工具箱。
大量的数值和理论证据表明，NISQ硬件上的变分QML算法具有多种优势。其中包括存在设备、参数、特征和标签噪声时的鲁棒性。应用的广度可能类似于深度学习，这是一套用于生成和预测建模的高度灵活的方法学工具，目前在该领域广泛使用。
关于量子优势，需要进一步的实验工作来评估现有变分QML的潜在优势是否能够产生运行优势。特别是样本复杂性优势可能会产生巨大影响。事实上，如果在生物和临床研究中常见的数据分布上能够证明哪怕是很小的多项式缩减，它们可能会在实例很少(例如，由于疾病发生率)或样本采集昂贵、有创或困难的情况下找到重要的应用。符合这一标准的例子包括罕见表型的诊断和预后，从EHR数据中识别多种药物的不良反应，以及根据临床结果诊断癌症及其亚型，如药物敏感性和疾病预后。总之，尽管QML优势的实际应用在很大程度上仍停留在理论上，但它们解决现有领域限制的潜力为进一步研究变分QML方法提供了充分的动力。
5.量子数据结构
在生物信息学和计算生物学中，非传统的数据结构长期以来一直被经典算法所利用。例如,许多用于纠错序列数据的最先进算法利用布隆过滤器(Bloom Filter)，其核心优势在于能够以较低的假阳性查找概率换取显著的内存节约——这是大型生物信息学管道中的常见限制。
可以想象，量子计算机固有的概率性质和量子信息提供的新的数据输入模式，如角度和相位编码，可能推动在FTQC体系中开发类似有用的量子数据结构和抽象，如QRAM。从中期来看，共同努力开发一个开放的量子数据结构库可能有助于提高我们对量子方法类型的理解，这些量子方法可能具有长期的实际优势。
报告全文：
https://arxiv.org/pdf/2112.00760.pdf
编辑：王衍
