摘要
水文裂缝网络建模是计算地球科学中的一个标志性挑战。要准确预测裂缝系统的关键特征(如渗流),就需要求解远远超出当前或未来高性能能力的大型线性系统。量子计算机理论上可以绕过经典方法面临的内存和速度限制,但必须首先解决几个技术问题。在这些困难中,主要的是这样的系统通常是病态的,即系统中的小变化会导致解的大变化,这可能会降低线性求解算法的性能。我们测试了几种现有的量子技术来改善条件数,但发现它们还不够。然后引入逆拉普拉斯预条件因子,改进了系统条件数的缩放O(N)\ (O大概{N}) (\ \)并承认量子实现。这些结果是开发断裂系统量子求解器的关键的第一步,既提高了水文建模的状态,又为量子线性系统算法提供了新的现实应用。
简介
求解线性系统的量子算法比经典算法具有实际的量子优势1.然而,在一个有意义的、真实的线性系统量子优势的例子能够被展示之前,仍然存在几个技术和概念上的挑战。在技术方面,许多这些量子线性系统(QLS)算法只能在未来的纠错硬件上实现1,而其他一些则是为当今嘈杂的中型量子设备设计的,但加速效果不那么明显2.在概念方面,现有算法有许多必须满足的注意事项,以获得良好的性能3..理想系统\ (Ax = b \)对于显示量子加速满足:(1)一个(2)量子算符是否条件良好\ (e ^ {iat} \)可以有效地实现,(3)量子态成正比b(4)能有效地制备出只有特定值或统计量的解吗x有趣的是,(5)不存在一个经典算法,利用这些或其他系统的属性来同样快速地求解它。最后一点是特别值得注意的,因为大方程组通常可以被小方程组所取代,这些小方程组可以保持足够的精度(并且可以用适当的成本进行经典求解)。4.因此,QLS算法的现有应用在很大程度上是综合的或具体的例子,精心选择以避免这些限制,但也缺乏实际应用5,6.
在这项工作中,我们开始了用QLS算法模拟裂缝系统中流体流动的研究。水文流在地球物理学中是一个非常具有挑战性的问题,因为经常进行模拟的尺度(公里或更大)与非均匀性尺度(厘米或更小)之间的对比需要在非常大的网格上离散问题。在这里,我们解决了确定地下液体(例如水或油)压力的常见问题,无论是在特定位置,即在一口井中,还是在一个大范围内的平均压力,即有效渗透率。提取单个位置的压力或研究平均特性(而不是需要系统中每个点的确切压力)解决了QLS要求列表中的第4点。正如我们在章节中讨论的那样裂缝网络和粗粒化,这类问题不能在不丢失关键信息的情况下简化为一个更小的方程组,因此当前的经典技术无法在现实世界规模下捕捉问题的全部范围(第5点)一个出现在地下流动应用中的向量一般是稀疏的b是相对均匀的,第2点和第3点似乎是通过量子RAM解决的3..然而,这些观点是相当微妙的,将在未来的工作中详细研究。
我们的工作重点是第一点,改进线性系统的条件数。矩阵的条件数描述了系统对小扰动的敏感程度,或者更具体地说,右手边的误差有多大,b,传播到解决方案中的错误,x在最坏的情况下。简单的矩阵,如酉矩阵,有条件数1,增加条件数会使线性系统更难求解。量子和经典线性系统算法通常在条件数大的系统上表现较差。减少压裂条件数量的经典方法被称为预处理剂,已经被成功地开发出来,并专门针对裂缝系统进行了定制,最突出的例子是多网格预处理剂7.然而,由于底层技术和算法设计的限制,它们不能简单地直接移植到量子计算机上8.因此,为了利用量子计算机求解相关断裂网络的大型线性系统,并超越经典技术,必须开发一种有效的断裂网络量子预处理算法。好的预处理通常与所要解决的线性系统类型相关,并利用问题中的一些潜在的数学或物理结构。与此同时,还必须找到一种有效的方法来计算系统的预处理形式,由于内存限制,这将需要在量子计算机本身上做非常大的系统。这两个约束——为特定的应用量身定制,同时也有一个有效的量子实现——很可能在未来解决量子计算机上的大型、有趣的线性系统的尝试中发挥突出作用。
我们表明,现有的减少条件数的技术要么没有量子实现,要么不太适合断裂系统。然而,我们发现逆拉普拉斯算子在断裂系统上是有效的,并且可以在量子计算机上有效地实现。见图。1对于我们的研究结果的总结。此外,我们表明,与经典方法相比,量子计算机可以以多项式优势求解现实的断裂系统。最后,我们讨论了剩余的算法瓶颈,这些瓶颈需要解决,以释放裂缝系统QLS的全部潜力。
结果
在本节中,我们将进一步详细描述地球物理问题,并讨论为什么它对经典计算机来说不是完全可处理的(第“裂缝网络和粗粒化”)。然后,我们回顾了现有的三种量子预处理算法,并研究了它们如何改善几个合成断裂网络实例的条件数。这些例子的条件数(不带预处理)均为O(N),最好的预处理剂将这种比例降低到大致\ (O大概{N}) (\ \)(部分”现有量子预处理的测试),这可能足以产生比经典技术的多项式优势。最后,我们分析了将预处理因子合并到完整的QLS算法中可能会如何影响总体运行时(“逆拉普拉斯预条件的算法缩放”)。
裂缝网络和粗粒化
在一个复杂的裂缝网络中,许多尺度的裂缝——从千米到厘米——相交。关键的是,小裂缝通常不能被忽视,因为它们可以从根本上改变网络拓扑结构,例如,将系统推到渗流阈值以上,如图所示。2.小裂缝也可能共同为网络提供大的表面积,提供裂缝和下伏岩石之间的关键连接。因此,在对这些网络中的流动进行建模时,必须包括所有裂缝尺度,这就导致了先进的网格划分技术的发展9以及高性能模拟器10.然而,这些方法并没有提供一个可行的方法来对所有的尺度进行建模。即使是最先进的高性能计算机和最先进的方法,也只能模拟裂缝长度变化超过三个数量级的大型裂缝网络11.要想对真实世界的裂缝网络进行高精度建模,所需要的网格远远超出当前或未来的经典能力。,一个1km的域,分辨率为1cm\ (10 ^ {15} \)自由度。更大的域或更精细的网格将需要更大的方程组。
裂缝网络地下渗流的数值模型是基于离散化模型的7
在哪里k是渗透率,f流体流量,和h就是压强。每个人k,f,h是一个在整个定义域空间上变化的函数。压力是地下流体应用的关键,如废液处理和水力压裂12.它对传输应用也很关键,因为压力梯度驱动传输。在压裂系统中,k是高度非均质的,当从岩石基质移动时急剧增加(在哪里k是小的)到骨折(哪里k大)。
我们离散Eq. (1)采用两点通量有限体积法,该方法是地下流量求解器代码库中使用的标准数值格式之一,包括:fehm13,tough214,pflotran15.两点通量有限体积法保证了质量守恒,这是一个非常理想的性质,为这些数值求解。这就得到了一个稀疏的、对称的、正定的系数矩阵。我们认为岩石基质的渗透性是恒定的。虽然这种近似方法并不完美,但它比离散裂缝网络方法进步了一大步,后者有效地将岩石基质视为零渗透率7.然而,这种方法确实捕捉到了裂缝流动的基本物理特性——大部分但不是全部的流动都发生在高渗透裂缝中。
在这项工作中,我们研究了多种二维裂缝网络模型。我们研究的最简单的系统包括两个裂缝相交于a,然后我们研究了分形式递归的-系统生成更复杂的裂缝网络,如图。3..与下伏岩石相比,裂缝的相对渗透率是裂缝系统分析中的一个关键参数,我们研究了五种不同类型的裂缝:
- 骨折类型1:
“简单,低”是-裂缝渗透率比下伏岩石高10%的系统。
- 骨折类型2:
“简单,高”是-含裂缝体系\ (10 ^ 4 \)比下面的岩石渗透性强几倍。
- 骨折类型3和4:
“分形,低/高”与上述相同,但采用分形系统。
- 5型骨折:
“Fractal, Var.”是一个分形系统,其中裂缝的渗透率差异随着裂缝的变小而减小,即最大的裂缝具有差异\ (10 ^ 4 \)最小的骨折对比度为1.1,随着对比度的缩小\((\text{断裂长度})^{1/2}\),在实践中常用11.
现有量子预处理的测试
最近开发的QLS算法为模拟裂缝网络的全部复杂性提供了一种新的途径。自从量子计算机问世以来n量子比特可以表示\ (2 ^ n \)维向量,庞大的方程组可以用少量的量子位来求解。也就是说,对于上述1km域的1cm分辨率问题,量子计算机可能只需要\(O(\log(10^{15})\约50)\)量子比特,而经典计算机需要\ (O (10 ^ {15}) \)经典比特。虽然可能需要额外的量子资源,无论是以辅助量子比特还是量子RAM的形式,这突出了量子方法的原始潜力,即精确模拟现实地下流动所必需的巨大方程系统。此外,量子线性系统算法的计算复杂度在某些情况下可以指数级优于最佳的经典算法16.
由Harrow, Hassidim, and Lloyd (HHL)介绍的原始QLS算法1解决一个稀疏问题N-变量方程组\(Ax = b\)运行时为\(O(\log (N) \kappa (A)²)\),在那里\(\kappa (A):= \Vert A\Vert A^{-1}\Vert\)条件号是一个(在这项工作中我们使用\(\ \绿色\绿色)没有下标表示2范数(或运算符范数),即。\(\垂直A\垂直等于\垂直A\垂直_2\),并显式地使用\(\Vert A\Vert _F\)参照Frobenius范数)。最经典的算法是共轭梯度法\ (O (N \ sqrt{\卡帕(A)}) \)在稀疏矩阵上,所以量子算法提供了一个指数级的加速\ \(\卡帕(A))是小的(为了符号清晰,我们经常使用'\ (\ kappa \)单独表示\ \(\卡帕(A))).
自引入HHL算法以来,引入了更多的QLS算法,包括对HHL的改进16,17,绝热方法18,19,以及可在近期量子计算机上实现的变分算法2,5.所有这些量子方法的一个共同特征是缩放\ (\ kappa \)这充其量是线性的,与\ (O大概{\ kappa}) (\ \)最佳经典方法的扩展。经典分析中常用的技术是进一步约简\ (\ kappa \)通过使用预处理剂。这项技术依赖于找到一个矩阵米这样\(\kappa (MA) \ll \kappa (A)\).然后你会发现x令人满意的\(MAx = Mb\).矩阵米一般取决于特定的矩阵一个,并且针对不同的情境开发了不同的预处理方法。
尽管人们对QLS算法有很大的兴趣和兴趣,但在开发特定于应用程序的预处理算法方面做的工作相对较少。需要强调的是,在这项工作中,我们只考虑可在量子计算机上实现的预处理算法,而不是任何类型的经典-量子预处理方法。虽然我们不排除这种方法的可能性,但全尺寸地下流动问题的极端内存要求(如上所述)表明,用经典方法计算预处理矩阵将是难以解决的。目前文献中有三种通用量子预处理算法:循环法20.,为稀疏近似逆方法21、快速逆法22.这些算法在“”节中详细描述。方法,这里我们只给出要点。
循环方法是一种万能方法,也就是说,唯一的输入是一个矩阵一个输出是一个前置条件米.对于SPAI,我们给出了一个稀疏模式的预处理米,并且已经开发了几种技术来确定裂缝系统的良好稀疏模式23.快速逆方法是为这种形式的系统设计的\ (A + B \),在那里\ (^ {1} \)很容易计算。然后使用\ (^ {1} \)作为预处理剂。如章节所述方法,断裂体系可分解为\(\Delta + A_F\),即拉普拉斯式\三角洲(\ \)描述了在没有裂缝的情况下的系统\ (A_F \)是骨折的贡献。因为拉普拉斯算子的奇异值分解是已知的24,\ \(△^ {1}\)可以有效地计算并用作预处理剂。
在无花果。4我们数值评估了循环、SPAI和逆拉普拉斯预处理对节中描述的所有裂缝类型的影响。裂缝网络和粗粒化“到\ (O (10 ^ 6) \)变量。来估计预调理器的性能如何与N,我们对应用于每种骨折类型的每种预处理条件的最后四个数据点的对数进行线性回归。我们不包括第一点,因为他们有时表现出方差,由于小的矩阵大小,然而\ (N > 10 ^ 3 \),所有结果在量子位数上显示出明显的指数级缩放,在方程数上显示出明显的多项式级缩放。我们发现循环压裂法和SPAI方法对于所考虑的裂缝系统来说是较差的选择。虽然这两个预处理条件持续地减少了系统的条件数,但它们并没有改善条件数的扩展方式N,这对于释放QLS算法解决大问题的全部潜力是必要的。然而,逆拉普拉斯预条件确实有意义地改善了条件数的缩放。在低渗透率对比的情况下,系统的条件数\(δ^ \ \ {1})是很低的,缩放为\ \ (le O (N ^ {0.05}) \).高渗透性对比系统也不公平,与\ (\ kappa \)的预条件分形系统缩放为\ (O (N ^ {0.6}) \).变渗透分形系统是目前研究中最现实的系统,它有一个先决条件\ (\ kappa \)哪个近似地渐近缩放\ (O (N ^ {0.55}) \).
逆拉普拉斯预条件的算法缩放
识别预处理条件米这就减少了系统的条件数一个通常不足以保证QLS算法解决预条件系统的良好性能\(MAx = Mb\).这是因为必须找到一种有效的方法来计算乘积妈以使其在量子计算机上易于访问的方式。这可以通过有效计算的经典预言来完成妈,或者通过使用神谕的量子算法一个而且米然后计算妈.如前所述,在这项工作中,我们只研究了预处理因子可以应用于量子计算机本身的情况,因为全面水文模拟需要相当大的内存。不幸的是,简单的计算妈在一般情况下,量子计算机上的一般矩阵乘法加一个\ (O (N ^ 2) \)开销25并且会从减少的条件数中消除任何好处。前面讨论的三种方法都通过巧妙的技术绕过了这一限制:循环方法用量子傅里叶变换算法计算乘积,SPAI方法利用稀疏性米而且一个,快速逆方法假设有效的块编码米而且一个.
如“现有量子预处理的测试,数据如图所示。4表明循环预处理和SPAI预处理并不能显著提高结垢率N本文所考虑的断裂实例的条件数。因此,在完整的QLS算法中为实现这些预处理条件中的任何一个而确定完整的算法运行时是不值得的。然而,逆拉普拉斯式将条件数减少到之间的比例\ (O (N ^ {0.05}) \)来\ (O (N ^ {0.6}) \),这可能足以使其优于经典算法。因此,估计逆拉普拉斯预条件对求解地下流动系统的总运行时间的影响是有指导意义的。
在原HHL算法中实现逆拉普拉斯预条件是有可能的,而Tong等人的QLS算法。22给出了一种应用预调节器并求解结果系统的直接方法。因此,我们可以使用他们算法的缩放作为概念证明,以了解逆拉普拉斯是否能够充分改善条件数以恢复一些量子加速。这个分析故意忽略了QLS警告列表中的第2点和第3点所产生的复杂性,即有效地转换经典数据一个而且b变成合适的量子态和算符。我们强调,该分析旨在作为预处理QLS算法在求解断裂系统时如何扩展的保守估计。希望有更有效的实现,我们将在章节中详细讨论。”讨论,并将在未来的工作中进一步探索。
正如我们在"方法的快速逆QLS算法\ \(△^ {1}\)因为预处理条件给出了一个运行时的下限
缩放N的\(\垂直A-\德尔塔\垂直)而且\(\Vert A^{-1}\Delta \Vert\)取决于所研究的确切断裂系统,必须通过实验确定。在无花果。5我们展示了可变对比度的分形系统的这些成分的缩放。我们关注这个特殊的例子,因为它是不同类型的骨折中最现实的。就像在章节里一样现有量子预处理的测试,我们估计大-N通过数据点的线性回归(在对数-对数图上)对不同成分进行缩放\ (N > 10 ^ 3 \).在表1我们总结了每个组件的缩放以及整体缩放(模\ \ log (N) (\))与相同系统上的共轭梯度标度相比。
使用快速逆QLS算法和逆拉普拉斯预条件,我们可以实现对所有断裂系统的最佳通用经典缩放的多项式改进。该方法利用的块编码\ \(△^ {1}\)而且\ (A -δ\ \)计算乘积\(δ^ \ \ {1}).然而,由于\(\Vert \Delta ^{-1}\Vert\)线性缩放N,块编码至少需要这么长时间。未来的QLS算法可以专门针对裂缝系统进行计算\(δ^ \ \ {1})的稀疏性甚至更有效一个.
讨论
在这项工作中,我们开始了使用QLS算法求解描述地下流动的方程组的研究。正如我们在章节中讨论的那样裂缝网络和粗粒化,对于经典计算机来说,在现实世界中捕捉这些系统的完整行为是非常内存密集的。量子计算提供了另一种路径,可能会使用更少的资源,并提供更好的问题规模扩展。然而,必须解决几个概念上的问题(除了需要改进量子计算硬件之外)。这些问题中最突出的是这些系统的不良状态数量和将信息加载到量子计算机上的方法。在这里,我们已经通过使用量子预处理条件研究了第一个问题,我们把后一个问题留给将来的工作。
我们已经证明了之前引入的两种量子预处理剂,循环方法和SPAI方法,并不能改善缩放N的\ \(\卡帕(A))因此不会帮助这些断裂系统获得量子优势。然而,逆拉普拉斯是断裂系统的一个有效的预处理条件,并易于接受量子实现。特别地,它可以通过快速逆QLS算法来实现,并且该求解器的整体伸缩性优于最佳的通用经典算法。
与经典技术相比,到目前为止,我们还没有解决一个事实,即对于统一网格上基于pde的系统,例如这里考虑的那些,可以使用更专门的方法。几何多重网格法是利用结构化网格求解方程组的一种方法O(N)或\ (O (N \ log N) \)26.由于QLS算法附加了大量的警告和严格的要求,值得注意的是(尽管这还不够),我们的初步结果表明,量子性能至少可以与最先进的、高度调谐的经典技术相媲美。这是在传统技术不可避免的内存要求之外的。尽管如此,很明显有必要进一步完善QLS算法,更深入地研究现有断裂系统的具体物理和数学结构。
一个明显需要改进的领域是使用更有效的量子方法来实现前置条件系统\(δ^ \ \ {1}).在我们研究的最现实的情况下,具有可变对比度的分形系统,\(\kappa (\Delta ^{-1}A)\)渐近线到大致\ (O (N ^ {0.55}) \).因此,原则上只求解预条件系统的标度,例如用最近的绝热QLS算法18,将是\ (O (N ^{0.55}日志{N}) \ \),对几何多重网格方法进行了显著改进。
另外,虽然逆拉普拉斯式为多项式加速打开了一扇门,但指数加速需要一个更好的前置条件。例如,虽然经典多重网格方法的直接量子端口是不可信的,但其中的一些想法可能被用于构建一个可以在量子计算机上实现的类似方法。减少缩放到的条件数\ (O日志{N}) (\ \)在量子环境下是可能的。
这项研究表明,断裂网络是一个具有挑战性的现实问题,量子计算有可能取得重大进展。精确模拟流行为所必需的大型线性系统是稀疏的,但不能是粗粒度的。条件号\ (\ kappa \)的值趋于线性缩放N然而,逆拉普拉斯前置条件,它很容易接受量子实现,可以大大提高这种缩放,而且它很可能会在\ (\ kappa \).未来的工作将致力于将我们的应用特定的预处理技术整合到一个完整的量子线性求解器中,理想的目标是在NISQ设备上实现。
方法
在本节中,我们将更详细地回顾“现有量子预处理的测试,以及在“节中找到的快速逆算法的缩放界的推导。逆拉普拉斯预条件的算法缩放”。
循环预调节器
邵等人的循环预处理方法。20.给出了循环预处理的一种有效量子实现C基于量子傅里叶变换F.一个\ (n \ n \)矩阵C如果是循环的\(C_{ij} = C_{(i-j)\mod n}\).经典应用中循环预处理条件的使用是基于这样一个事实:对于给定的循环矩阵C和一个任意矩阵一个,CA而且\ \ (C ^ {1})可在\(O(n \log n)\)步骤,使用快速傅里叶变换。循环预处理在求解Toeplitz方程组中特别有用27.
对于任意矩阵一个,可通过构造循环预处理器
在哪里\(F_{jk} = \frac{1}{\sqrt{n}}\omega ^{jk}\)与\(\ ω = e^{-2\ i/n}\).\ (C ^ {1} (A) \)然后使用预调理剂。F可以通过量子傅里叶变换有效地实现,并且中间项简化为
一种有效地准备Eq中状态的算法。4给出了20..这种方法适用于任意密集的非厄米矩阵,但是在上没有上界\ \(卡帕(CA) \),并在实践中用于随机密集矩阵\(\kappa (CA) = O(\kappa (A))\).
稀疏近似逆
求解系统的稀疏近似逆(SPAI)方法\ (Ax = b \)试图找到一个矩阵米这样\(MA \约I\),在那里米具有(用户定义的)稀疏模式。例如,如果有人给出一个稀疏模式n非零行和d那么,每行有非零元素米是通过解\(n \乘d\)独立最小二乘问题。这种方法的诀窍在于确定要选择哪种稀疏模式米.
Clader等人。21显示了预条件系统
可以通过稍微修改的HHL算法来解决。实际求解Eq. (5)有误差\ε(\ \)是
在分段中"现有量子预处理的测试的稀疏模式,我们采用相对标准的方法一个为米.你也可以尝试其他方法23,这可以显著减少条件数,但同样不能改善缩放N对于这里研究的断裂系统。最后,d不需要是常数。只要\(\kappa (MA) = O(1)\),稀疏度模式可缩放\(d \propto N^{\le 1/7}\)为了至少恢复一些量子优势。然而,对于这里所考虑的系统和稀疏模式,在d有相应的小幅下降吗\ \(卡帕(MA) \).例如,当应用中描述的技术时23对“简单”系统,即分形深度为1,密度为1米五倍只会减少\ \(卡帕(MA) \)是原来的两倍。因此,很难想象一个系统的大小或稀疏模式,这样的增量增加d能产生足够大的削减\ \(卡帕(MA) \)让手术变得有价值。
快速逆
Tong等的快速逆方法。22求解线性系统\ (Ax = b \)在哪里一个可分解为
在哪里\ \(绿色现代文本{大}}{\ \绿色\ gg \绿色现代文本{小}}{\ \绿色\).然后他们给出了一个QLS算法\(现代文本{大}}{\ ^ {1}\)作为预处理剂,解决系统问题\ (I +现代文本{大}}{\ ^{1}现代{\文本{小}})x =现代文本{大}}{\ ^ {1}b \)缩放范围为\(\绿色现代文本{小}}{\ \绿色\绿色现代文本{大}}{\ ^{1}\绿色\)而且\(\绿色^{1}\绿色\).
这种技术依赖于有效的块编码\(现代文本{大}}{\ ^ {1}\)而且\(现代文本{小}}{\ \).一个\((\alpha, m, \ ε)\)矩阵的block-encoding一个是由幺正式给出的\ (U_A \):
在哪里\ \ (*)表示任意矩阵块,\α(\ \)缩放常数是这样的吗\(\Vert U_A\Vert =1\),和误差\ε(\ \)的边界是\(\ vangle 0^m|\otimes I_n)U_A(|O^m\rangle \otimes I_n)\ vvert \le \epsilon\).因为\α(\ \)在这个算法的缩放中起着关键作用,我们注意到\(\Vert U_A\Vert =1\)意味着\(\alpha \ge \Vert A\Vert\).
为了使用\(现代文本{大}}{\ ^ {1}\)作为前置条件,\(现代文本{大}}{\ \)必须fast-invertible.一个矩阵米快速可逆矩阵是否可以有效地制备\((\Theta (1), m, \) \)分块编码\ (U ' _M \)的\ (M ^ {1} \).这需要访问oracle for\ (M ^ {1} \),以及对该oracle正在准备的查询的数量\ (U ' _M \)必须独立于\ \(卡帕(M) \).例如,如果米是正态的,特征值分解\ (M = VDV ^{\匕首}\)给出了一个V这可以在量子电路中有效地实现D可以通过oracle访问,那么米fast-invertible。
快速逆QLS算法以输入为参数\((\alpha _s, m_s, 0)\)分块编码\ (u_ \)的\(现代文本{小}}{\ \),以及\((\alpha '_b, m'_b, 0)\)分块编码\ (U ' _b \)的\(现代文本{大}}{\ ^ {1}\)通过快速反转实现。然后他们使用量子奇异值变换的修正版本28构造的块编码\((A_{\text{大}}+A_{\text{小}})^{-1}\)与错误\ε(\ \)在
的应用\ (u_ U ' _b \)连同他们的逆,控制版本,和其他原始门。在这里\(\tilde{\sigma}_{\min}\)的最小奇异值有下界吗\(I+A_{\text {big}}^{-1}A_{\text {small}}\),即预条件系统。
这种方法的好处是提供了预条件矩阵的条件数的上界,缺点是需要分解一个这符合一长串的要求。对于断裂问题,我们有自然分解
拉普拉斯在哪里\三角洲(\ \)描述了在没有裂缝的情况下的流动\ (A_F \)表示骨折基质。幸运的是,离散拉普拉斯是正常的,并有一个已知的特征值分解24,因此它满足快速可逆条件,我们可以用它作为预处理条件。然而,我们不能保证\(\垂直\德尔塔\垂直\gg \垂直A-德尔塔\垂直\),这是获得良好缩放所必需的。尽管如此,我们仍然可以数值测试算法的伸缩性,看看在没有性能保证的情况下它是如何执行的。
影响该算法性能的参数,式(9),为块编码参数\(\α' _b \)而且\ (alpha _ \ \),以及预处理系统的最小奇异值的下界妈,\(\tilde{\sigma}_{\min}\).为了评估该算法对我们的应用程序的潜在有用性,我们将探索这些参数的最乐观值。由于一些小的技术细节,我们重新调整了整个系统\(\Vert \Delta ^{-1}\Vert\),这就给出\(现代{\文本{大}}= \ \绿色\δ^{1}\绿色\)而且\(\α' _b \)的块编码参数\(现代文本{大}}{\ ^ {1}\))\(= \ θ (1)\).我们还有\(现代{\文本{小}}=δ)(A - \ \绿色\三角洲^{1}\绿色\),所以\(\alpha _s \ge \Vert A-\Delta \Vert\ Vert\ Delta ^{-1}\Vert\),\(1 / \波浪号{\σ}_{\分钟}\通用电气\绿色^{1}\三角洲\绿色\).因此,快速逆QLS算法的总体缩放范围为
数据可用性
本研究中使用和/或分析的数据集可根据合理要求从通讯作者处获得。
参考文献
哈罗,A. W., Hassidim, A. & Lloyd, S.线性方程组的量子算法。理论物理。启。103, 150502年。https://doi.org/10.1103/PhysRevLett.103.150502(2009)。
Bravo-Prieto C。et al。变分量子线性求解:线性系统的一种混合算法。公牛。点。理论物理。Soc。20., 1-14(2020)。
艾伦森,S.阅读细则。Nat。物理。https://doi.org/10.1038/nphys3272(2015)。
蒙塔纳罗,A. & Pallister, S.量子算法和有限元方法。理论物理。启一个93, 553年。https://doi.org/10.1103/physreva.93.032324(2016)。
黄,H.-Y。,Bharti, K. & Rebentrost, P. Near-Term Quantum Algorithms for Linear Systems of Equations.arXiv: 1909.07344(2019)。
量子计算在地球物理学中的应用。在第五届EAGE上游高性能计算研讨会1 - 5。https://doi.org/10.3997/2214-4609.2021612005(2021)。
Greer, S., Hyman, J. & O 'Malley, D.求解三维离散裂缝网络流动的线性求解器的比较。水Resour。Res。https://doi.org/10.1029/2021WR031188(2022)。
韩亚尼,m.f。大规模量子计算的资源成本。博士论文(2021)。
海曼,j.d.。et al。dfnworks:用于模拟地下流动和运移的离散裂缝网络框架。第一版。Geosci。84, 10 - 19。https://doi.org/10.1016/j.cageo.2015.08.001(2015)。
米尔斯,R. T.,陆,C., Lichtner, P. C. & Hammond, G. E.在超规模计算机上使用PFLOTRAN模拟地下流动和输送。期刊。:Conf. Ser.78, 012051年。https://doi.org/10.1088/1742-6596/78/1/012051(2007)。
Hyman, J., Aldrich, G., Viswanathan, H., Makedonska, N. & Karra, S.裂缝尺寸与透射率相关性:裂缝尺寸截断幂律分布对稀疏三维离散裂缝网络传输模拟的影响水Resour。Res。52, 6472-6489(2016)。
Pachalieva, A., O 'Malley, D., Harp, D. & Viswanathan, H.基于物理知识的机器学习与可微分编程用于异构地下储层压力管理。科学。代表。2022, 14(2022)。
FEHM:模拟地下多相多流体传热和传质的控制体积有限元代码。在洛斯阿拉莫斯秘密报告LA-UR-07-3359(2007)。
普鲁斯,K.奥尔登堡,C. M.莫里迪斯,G.;Tough2用户指南版本2(1999)。
Lichtner, P。等.PFLOTRAN用户手册:描述地表和地下过程的大规模并行无功流和传输模型。(报告不代表。:LA-UR-15-20403) Los Alamos National Laboratory(2015)。
蔡尔兹,科塔里,R. &索玛,R. D.线性方程组的量子算法与指数改进依赖于精度。SIAM J. Comput。46, 1920 - 1950。https://doi.org/10.1137/16M1087072(2017)。
Ambainis,。变时幅放大和求解线性方程组的更快的量子算法.arXiv: 1010.4458(2010)。
苏巴基亚,Y., Somma, R. D. & Orsucci, D.受绝热量子计算启发的线性方程组的量子算法。理论物理。启。122, 060504(2019)。
哥,P。等.基于离散绝热定理的最优尺度量子线性系统求解.arXiv: 2111.08152(2021)。
邵志刚,向辉。线性方程组的量子循环预处理。理论物理。启一个98, 062321年。https://doi.org/10.1103/PhysRevA.98.062321(2018)。
克拉德,雅各布斯,斯普劳斯。预处理量子线性系统算法。理论物理。启。110, 250504年。https://doi.org/10.1103/PhysRevLett.110.250504(2013)。
佟勇,安东,Wiebe, N.和Lin L.快速反演,预处理量子线性系统求解器,快速格林函数计算和矩阵函数的快速求值。理论物理。启一个104, 032422年。https://doi.org/10.1103/PhysRevA.104.032422(2021)。
李国强,李国强,李国强。基于共轭梯度法的稀疏近似逆预处理算法。的完整性。第一版。19, 120-126(2013)。
德梅尔,j.w.。应用数值线性代数(暹罗,1997)。
邵,C。矩阵乘法的量子算法.https://doi.org/10.48550/ARXIV.1803.01601(2018)。
斯特朗,G。计算科学与工程“,”Sirsi) i9780961408817(2007)。
格雷,R. M. Toeplitz和循环矩阵:综述。发现。Commun趋势。正理论。2, 155 - 239。https://doi.org/10.1561/0100000006(2006)。
Gilyén, A., Su, Y., Low, G. H. & Wiebe, N.量子奇异值变换及其超越:量子矩阵算术的指数改进。在第51届ACM SIGACT计算理论研讨会论文集.https://doi.org/10.1145/3313276.3316366(ACM, 2019)。
确认
这项工作得到了美国能源部通过洛斯阿拉莫斯国家实验室(LA-UR-22-24431)的支持。洛斯阿拉莫斯国家实验室由Triad国家安全有限责任公司为美国能源部国家核安全管理局运营(合同编号89233218CNA000001)。DO和JG感谢洛斯阿拉莫斯国家实验室通过20220077ER项目对实验室指导研究和发展计划的支持。
作者信息
作者及隶属关系
贡献
D.O.和J.G.构想了这项研究,J.G.进行了实验并分析了结果。所有作者都审阅了手稿。
相应的作者
道德声明
相互竞争的利益
作者声明没有利益竞争。
额外的信息
出版商的注意
施普林格自然对出版的地图和机构从属关系中的管辖权主张保持中立。
权利和权限
开放获取本文遵循知识共享署名4.0国际许可协议,允许以任何媒介或格式使用、分享、改编、分发和复制,只要您对原作者和来源给予适当的署名,提供知识共享许可协议的链接,并注明是否有更改。本文中的图像或其他第三方材料包含在文章的创作共用许可协议中,除非在材料的信用额度中另有说明。如果材料未包含在文章的创作共用许可协议中,并且您的预期使用不被法定法规所允许或超出了允许的使用范围,您将需要直接获得版权所有者的许可。如欲查看本牌照的副本,请浏览http://creativecommons.org/licenses/by/4.0/.
关于本文
引用本文
Golden, J. O 'Malley, D. & Viswanathan, H.水文线性系统的量子计算和预处理。Sci代表12, 22285(2022)。https://doi.org/10.1038/s41598-022-25727-9
收到了:
接受:
发表:
DOI:https://doi.org/10.1038/s41598-022-25727-9
这篇文章被引用
地质裂缝网络的量子算法
科学报告(2023)