Quantum Algorithms for Geologic Fracture Networks Jessie M. Henderson1 2Marianna Podzorova1 3 4M. Cerezo1 5 6John K. Golden1Leonard Gleyzer1 7Hari S. Viswanathan1and Daniel OMalley1

2025-05-02 0 0 4.28MB 20 页 10玖币

侵权投诉

Quantum Algorithms for Geologic Fracture Networks

Jessie M. Henderson,1, 2 Marianna Podzorova,1, 3, 4 M. Cerezo,1, 5, 6 John K.

Golden,1Leonard Gleyzer,1, 7 Hari S. Viswanathan,1and Daniel O’Malley1

1Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA

2Southern Methodist University, Dallas, Texas 75205, USA

3Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA

4The University of Maryland Department of Computer Science and Joint Center for

Quantum Information & Computer Science, College Park, Maryland 20742, USA

5Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87545, USA

6Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, New Mexico 87544

7Brown University, Providence, Rhode Island 02912, USA

Solving large systems of equations is a challenge for modeling natural phenomena, such as simulat-

ing subsurface ﬂow. To avoid systems that are intractable on current computers, it is often necessary

to neglect information at small scales, an approach known as coarse-graining. For many practical

applications, such as ﬂow in porous, homogenous materials, coarse-graining oﬀers a suﬃciently-

accurate approximation of the solution. Unfortunately, fractured systems cannot be accurately

coarse-grained, as critical network topology exists at the smallest scales, including topology that

can push the network across a percolation threshold. Therefore, new techniques are necessary to

accurately model important fracture systems. Quantum algorithms for solving linear systems of-

fer a theoretically-exponential improvement over their classical counterparts, and in this work we

introduce two quantum algorithms for fractured ﬂow. The ﬁrst algorithm, designed for future quan-

tum computers which operate without error, has enormous potential, but we demonstrate that

current hardware is too noisy for adequate performance. The second algorithm, designed to be

noise resilient, already performs well for problems of small to medium size (order 10 to 1000 nodes),

which we demonstrate experimentally and explain theoretically. We expect further improvements

by leveraging quantum error mitigation and preconditioning.

I. Introduction

Simulating geologic ﬂow requires solving systems of

equations, a process that can become computationally

prohibitive as system dimension increases [1]. Classical

computers can thus solve large systems only when infor-

mation is removed from consideration. Coarse-graining

is one technique for reducing system size. Originally

developed to model multi-scale biochemical systems, it

has become an oft-used means of simplifying linear sys-

tems, including in the geosciences [2–4]. Speciﬁcally,

the coarse-graining technique of upscaling can be accu-

rately applied to geological problems involving spatially-

large, materially-homogeneous regions. The technique

combines mesh nodes and assigns them an averaged, or

upscaled, permeability or other geological feature, los-

ing mesh resolution but, in this context, still preserving

approximately accurate solutions [5].

Unfortunately, fracture network problems cannot be

classically solved in their entirety, nor can they be accu-

rately solved with upscaling, making simulation of frac-

ture systems one of the most challenging problems in geo-

physics [6–9]. Fractures exist over a range of at least 10−6

to 104meters, and the computational requirements in-

volved in completely solving systems comprising over ten

orders of magnitude quickly become prohibitive. Such

systems also cannot be accurately upscaled because the

information thereby lost pertains to small fractures that

ought not generally be neglected. Collectively, such frac-

tures can radically transform the network topology, in-

cluding by possibly pushing the network over a perco-

lation threshold. The small fractures can collectively

contribute a signiﬁcant amount of surface area, enabling

stronger interaction between the fractures and the rock

matrix, potentially providing complete connectivity that

would not otherwise exist in a region [10].

Thus, accurate geologic ﬂow models should include

fractures at the entire range of scales. While advanced

meshing techniques [11] and high-performance simula-

tors [12] allow inclusion of increased fracture range, even

such sophisticated approaches do not make it possible to

model the full fracture scale. So, as illustrated in Fig. 1,

classical approaches to geologic fracture problems depend

upon upscaling that neglects information which can dra-

matically aﬀect the solution.

By contrast, quantum algorithms provide eﬃcient so-

lutions for solving large linear systems that could include

the entire scale of geologic fractures [13]. Properties

of quantum computing are fundamentally diﬀerent than

classical counterparts, theoretically permitting the solu-

tion of classically intractable problems [14–16]. Among

other beneﬁts, quantum computers store solutions as a

vector, ψ, containing 2nelements, where nis the num-

ber of qubits (or quantum bits). A quantum computer

can thereby solve vast systems of equations with a rela-

tively small number of qubits: nqubits allows for solving

a system with 2nvariables. Consider a straightforward

example involving a cubic fracture domain comprising

one-kilometer and employing a one-centimeter resolution.

Given 105centimeters to a kilometer, simulating this re-

arXiv:2210.11685v1 [quant-ph] 21 Oct 2022

FIG. 1. Schematic workﬂow for applying classical and quantum algorithms to fracture ﬂow problems. Discretizing

fracture systems on classical computers involves reducing the computational cost by truncating the fracture network to exclude

small fractures. This setting-aside of information provides a solution that does not accurately reﬂect all ﬂow. Conversely,

quantum computing has the potential to solve large, complete fracture systems given properties of quantum mechanics and

algorithms designed to take advantage of those properties.

gion would require (105)3= 1015 nodes. While a classical

computer would thus require O(1015)bits, a quantum

computer would require only O(log2(1015)) ≈O(101)

qubits.

This article illustrates using quantum algorithms to

solve fracture ﬂow linear systems problems (LSPs) for

which upscaling is not appropriate. We introduce two al-

gorithms and provide proof-of-concept application using

IBM’s suite of quantum devices. We consider problems

formulated as a numerical discretization of ∇·(k∇h) = f,

where kis the permeability, fis a ﬂuid source or sink,

and his the pressure to be computed. This discretization

results in a linear system of equations (Ax=b), where A

is a matrix, and xand bare vectors. The solution, x, rep-

resents the pressure at each of the discretized nodes, and

quantum algorithms prepare a normalized vector propor-

tional to this solution.

We note that obtaining this solution from a quantum

computer works diﬀerently than from a classical machine.

Upon quantum algorithm completion, the entire solution

is not readily available, and indeed, requires exponential

time to obtain [17]. This is no issue for applications in

which the goal is not to know the entire solution, but

is instead to completely solve the problem, such that

any portion of the solution that a user obtains is ac-

curate. Fortunately, fracture networks present just such

a situation; ordinarily, we are interested in the pressure

at a small, ﬁxed number of nodes on the computational

mesh, such as the nodes corresponding to a well location.

Rather than extract the pressure at all nodes from the

quantum computer, we need only obtain the pressures

at nodes corresponding to the area of interest. Further-

more, fracture ﬂow problems can be speciﬁed in such a

way that the complexity required to obtain information

about multiple nodes’ pressures is reduced. A procedure

that we term ‘smart encoding’ allows obtaining the aggre-

gated pressures of a series of nodes at the computational

cost of a single node. (See Sec. IX B online for further

details.)

The paper proceeds as follows. Sec. II A ﬁrst presents

two algorithms–the Harrow-Hassidim-Lloyd and Subasi-

Somma-Orsucci algorithms—that have proven potential

for solving LSPs on error-corrected, or fault-tolerant,

quantum computers [13]. Despite the potential for ex-

ponential gain in certain cases, the high noise levels of

current hardware result in poor performance [18–21].

Sec. II B then turns to algorithms designed for contem-

porary, noisy intermediate-scale quantum (NISQ) com-

puters [22–25]. Speciﬁcally, we experimentally illustrate

the noise resilience of the Variational Linear Solver al-

gorithm [26], which provides improved solution accuracy

even on available error-prone machines for fracture LSPs

of small to medium size (10 to 1000 nodes). We conclude

by situating our results and suggesting future improve-

ments.

II. Results

A. Algorithms for the Fault-Tolerant Era

The ﬁrst algorithm for solving quantum linear systems

problems (QLSPs) was introduced by Harrow, Hassidim,

and Lloyd (HHL) [13]. It solves the sparse N-variable

system Ax=bwith a computational complexity that

scales polynomially with log(N)and the condition num-

ber, κ, of the matrix A[13]. This provides an exponen-

tial speedup over the best classical approaches when κis

small, such as when an eﬀective preconditioner is used.

However, the quantum circuit requirements of HHL—

when applied to problems of even moderate size—are

well-beyond the capabilities of currently available quan-

tum hardware [27]. This is largely because HHL utilizes

complex subroutines, such as Quantum Phase Estima-

tion, which require qubits that operate with almost no

quantum noise or error. On NISQ hardware, HHL is thus

impractical for systems of interest; the largest system

solved to date using HHL is of dimension 16 ×16 [28–

33]. Once large fault-tolerant quantum computers are

developed, the exponential speedup oﬀered by HHL (and

variations/improvements thereon) could play a critical

role in advancing subsurface ﬂow modeling.

In the interim, progress in QLSP algorithms has oc-

curred in two directions. The ﬁrst is to tailor QLSP

algorithms to the strengths and weaknesses of current

NISQ computers, such as the algorithm we present in

Sec. II B does [26,29,34–36]. The second is to design

algorithms that are still intended for fault-tolerant com-

puters, but which do not rely on as many complex sub-

routines as HHL and thus may perform adequately on

NISQ devices [37–40]. One such example is the adiabatic

approach of Subasi, Somma, and Orsucci (SSO) [37].

This approach requires only a single subroutine, known

as Hamiltonian simulation, while still oﬀering the equiv-

alent quantum speed-up of HHL.

Before embarking on the purely NISQ-oriented ap-

proach of Sec. II B, we tested the SSO algorithm on a

collection of very simple subsurface ﬂow problems to as-

sess how well current hardware could handle one fault-

tolerant algorithm. As described in Sec. I, the problem

was to compute pressures of a one-dimensional grid of

either N= 4 or N= 8 nodes. (See subﬁgures (c) and

(d) of Fig. 2for a cartoon visualization.) Pressures on

the boundaries were ﬁxed, and the answer to the QLSP

encoded the internal pressures.

The computational complexity and resulting accuracy

of the SSO algorithm depend upon a unitless, user-

deﬁned parameter, q, which is connected to how long

the algorithm is allowed to run. We showed that—up to

a point—the algorithm returned better results as qin-

creased; for both N= 4 and N= 8 problems running

on a noiseless quantum simulator, the error kAx−bk

approached 0 for q= 104. On the quantum hardware,

the average error after an equivalent time was approxi-

mately 0.21 for an N= 4 problem and 0.54 for an N= 8

problem. (Note that for these problems, kbk= 1.)

Fig. 2illustrates these results and two noteworthy

points. First, the N= 8 problem exhibited a clear limit

to how much the hardware results would improve with

increasing q. Indeed, despite increasing qby four orders

of magnitude, the average error when run on the quan-

tum hardware decreased by only about 0.2. This suggests

that—on NISQ-era devices—SSO’s utility is limited even

for problems with as few as 8 nodes.

Second, Fig. 2compares the errors achieved on quan-

tum simulators and hardware to the error when obtain-

ing a result from the a quantum state known as the

maximally-mixed state. This comparison contextualizes

the quality of the errors achieved by SSO, because the

maximally-mixed state corresponds to a state where noise

has destroyed all information in the quantum system, and

thus can be characterized as one of random information.

Speciﬁcally, for the fracture ﬂow LSPs we solved, obtain-

ing a result from a quantum computer in the maximally-

mixed state is equivalent to obtaining any of the possible

states with equal probability. (In other words, a result

from a quantum computer in the maximally-mixed state

is a ‘solution’ chosen at random from a uniform distribu-

tion of all possible solutions.) Such a ‘solution’ is thus not

meaningful, because any accuracy is due to randomness,

and not to the performance of the SSO algorithm.

Fig. 2illustrates that the SSO algorithm oﬀered very

little improvement upon such a randomly-determined so-

lution. For example, in the N= 8 case, the hardware

results oﬀered an improvement of just about 24%: the

result from the maximally-mixed state had an error of

0.71, the quantum hardware achieved an average error

of 0.54, and so the improvement due to SSO was solely

0.71−0.54

0.71 = 0.24.

The fact that SSO’s performance on such small prob-

lems was so limited illustrates that, although fault-

tolerant algorithms like HHL and SSO have signiﬁcant

promise, the noise on contemporary devices is too high

for accurately solving even very small problems using

these methods.

B. An Algorithm for the Near-Term Era

An alternative to fault-tolerant algorithms are those

designed to operate in the NISQ regime, often by leverag-

ing robust classical computing alongside quantum hard-

ware. Variational Quantum Algorithms (VQAs) [22,23,

25] encode a task of interest—in our case, solving a lin-

ear system—in an optimization problem. In these al-

gorithms, the classical computer steers the optimization

process while the quantum computer computes a cost

function, which is being optimized. The goal is to train a

parameterized quantum circuit such that the parameters

minimizing the cost function are also those that cause the

circuit to compute the solution to the problem of inter-

est. There are multiple approaches to solving the QLSP

in near-term devices [26,34,35]; we focus on the Vari-

ational Linear Solver (VLS) algorithm of Ref. [26]. The

VLS algorithm trains parameters in a quantum circuit

such that, when a cost function is minimized, the solu-

tion encoded by the trained circuit is proportional to the

solution xof the LSP.

We employed the VLS algorithm to determine pres-

sures at each node in a discretized model of the subsur-

face. With VLS, we can currently tackle much more com-

FIG. 2. Solving 4-node and 8-node fracture systems

using the SSO algorithm. Subﬁgure (a) presents results

for a one-dimensional grid of 4 nodes, while subﬁgure (b) does

the same for a grid of 8 nodes. Each subﬁgure presents the

maximum, minimum, and average error in 75 runs on either

IBM’s quantum simulator (solid blue line) or the ibmq_rome

quantum computer (dashed red line). The error is plotted

against the number of iterations, q, used. The ﬁgures also

include a dotted gray line illustrating the error that would be

achieved if the returned ‘solution’ from the quantum computer

was the result of the maximally-mixed state. As described in

the main text, this serves as a benchmark for assessing the

quality of the solution SSO achieved. Subﬁgures (c) and (d)

present cartoons of the problems solved: each color indicates

a unique node pressure, with ﬁxed pressures of 1 and 0 on the

boundaries.

plex problems than we solved with the SSO algorithm.

The problems we considered contained a pitchfork frac-

ture with up to 8192 nodes in the discretization.

1. A 6x8 Domain with a Uniform Pitchfork

We started with the results of Fig. 3, which illustrates

that VLS determined the pressures in a 32-node region

with a ﬁdelity of greater than 99%. Fidelity is a mea-

sure of accuracy deﬁned as the inner product between

two vectors. Thus, ﬁdelity is 1—or 100%—when two

vectors have the same direction and proportional mag-

nitude, which equates to a perfect solution in our frac-

ture situation. (Recall that, since the quantum com-

puter produces a solution vector normalized to 1, the

output is proportional to the pressure solution.) Con-

versely, ﬁdelity is 0 when two vectors are orthogonal to

each other, meaning an entirely inaccurate fracture pres-

sure solution. Subﬁgures (a) and (b) illustrate that the

VLS training process—in which we simulated the quan-

tum hardware—generated circuit parameters such that

a ﬁdelity of 0.9987 was achieved in the best simulation

(highlighted in magenta). Furthermore, subﬁgures (c)

and (d) illustrate that noise on quantum hardware did

not appreciably damage the solution: when running the

circuit with the parameters found via optimization, we

achieved a ﬁdelity of 0.9911, only 0.0076 away from the

ﬁdelity achieved using a noiseless simulator.

Although this is a very small problem when compared

to what classical algorithms can accommodate today, this

result is signiﬁcant because it experimentally illustrates

that the VLS approach has some resilience to the noise

present in NISQ machines. That in turn suggests why ac-

curate results from quantum computers—even on small

problems—are worth exploring. Quantum computing,

both algorithmic and physical implementation, is still in

its infancy, so, accurately solving proof-of-concept prob-

lems like this one is an important step towards under-

standing how to make use of quantum computing for

fracture systems.

2. Larger Domains with Uniform Pitchforks

Success with the 32-node problem led us to consider

using VLS to solve larger problems. As predicted, noise

aﬀected these solutions more than in the case of Fig. 3

because increasing region size requires larger circuits—

including more qubits and more parameterized quantum

gates—to encode the problem. Nonetheless, we again

found that our solutions were quite accurate: the lowest

ﬁdelity was 0.8834 for an 8192-node problem.

Fig. 4illustrates the details, with subﬁgure (e) being

the most signiﬁcant result: it indicates that—for all prob-

lem sizes considered—we achieved solutions that were

signiﬁcantly more accurate than solutions that had de-

graded to noise alone. As in Sec. II A, we compared

the quality of the solution achieved on quantum hard-

ware to a ‘solution’ that would have been the result of

the maximally-mixed state. And, as in Sec. II A, the

maximally-mixed state result is a random solution se-

lected from the distribution of all possible solutions. Un-

like with SSO, we found that the quality of VLS’s solution

was signiﬁcantly higher than that from the random solu-

tion, even for problems that were larger and more com-

plicated than those solved with SSO. Even the worst ﬁ-

delity achieved was appreciably above that achieved by a

random, noise-only solution: 0.8834 compared to 0.1472.

The performance of VLS on scaled problems was sur-

prising; even as these are relatively small problems, and

even as VLS is designed for noisy hardware, we might

have seen signiﬁcantly worse solution quality, as illus-

trated by Fig. 4. This is because, although VLS oﬄoads

some computations onto error-proof classical machines,

any circuits running on contemporary quantum comput-

ers are susceptible to noise. However, quantum algo-

rithms may be less susceptible to noise, if they posses

properties that store the relevant information in speciﬁc

ways, to keep it ‘protected’ from the aﬀects of at least

some types of noise. When we found that the quan-

tum hardware’s worst ﬁdelity for scaled problems was

appreciably above the associated ‘noise-only’ ﬁdelity, we

decided to explore the extent to which the VLS algo-

rithm is noise-resilient [41]. In particular, a type of

noise known as depolarizing noise aﬀects quantum states

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

QuantumAlgorithmsforGeologicFractureNetworksJessieM.Henderson,1,2MariannaPodzorova,1,3,4M.Cerezo,1,5,6JohnK.Golden,1LeonardGleyzer,1,7HariS.Viswanathan,1andDanielO'Malley11LosAlamosNationalLaboratory,LosAlamos,NewMexico87545,USA2SouthernMethodistUniversity,Dallas,Texas75205,USA3TheoreticalDivision,L...

展开>> 收起<<

Quantum Algorithms for Geologic Fracture Networks Jessie M. Henderson1 2Marianna Podzorova1 3 4M. Cerezo1 5 6John K. Golden1Leonard Gleyzer1 7Hari S. Viswanathan1and Daniel OMalley1.pdf

共20页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Quantum Algorithms for Geologic Fracture Networks Jessie M. Henderson1 2Marianna Podzorova1 3 4M. Cerezo1 5 6John K. Golden1Leonard Gleyzer1 7Hari S. Viswanathan1and Daniel OMalley1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: