Search

Quantum algorithms provide an exponential speedup for solving certain classes of linear systems, including those that model geologic fracture flow. However, this revolutionary gain in efficiency does not come without difficulty. Quantum algorithms require that problems satisfy not only algorithm-specific constraints, but also application-specific ones. Otherwise, the quantum advantage carefully attained through algorithmic ingenuity can be entirely negated. Previous work addressing quantum algorithms for geologic fracture flow has illustrated core algorithmic approaches while incrementally removing assumptions. This work addresses two further requirements for solving geologic fracture flow systems with quantum algorithms: efficient system state preparation and efficient information extraction. Our approach to addressing each is consistent with an overall exponential speed-up., Comment: 13 pages, 12 figures, LA-UR-23-31328

Solving large systems of equations is a challenge for modeling natural phenomena, such as simulating subsurface flow. 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 flow in porous, homogenous materials, coarse-graining offers a sufficiently-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 offer a theoretically-exponential improvement over their classical counterparts, and in this work we introduce two quantum algorithms for fractured flow. The first algorithm, designed for future quantum 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., Comment: 20 pages, 12 figures

Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.

Homomorphic encryption has been an area of study in classical computing for decades. The fundamental goal of homomorphic encryption is to enable (untrusted) Oscar to perform a computation for Alice without Oscar knowing the input to the computation or the output from the computation. Alice encrypts the input before sending it to Oscar, and Oscar performs the computation directly on the encrypted data, producing an encrypted result. Oscar then sends the encrypted result of the computation back to Alice, who can decrypt it. We describe an approach to homomorphic encryption for quantum annealing based on spin reversal transformations and show that it comes with little or no performance penalty. This is in contrast to approaches to homomorphic encryption for classical computing, which incur a significant additional computational cost. This implies that the performance gap between quantum annealing and classical computing is reduced when both paradigms use homomorphic encryption. Further, homomorphic encryption is critical for quantum annealing because quantum annealers are native to the cloud -- a third party (such as untrusted Oscar) performs the computation. If sensitive information, such as health-related data subject to the Health Insurance Portability and Accountability Act, is to be processed with quantum annealers, such a technique could be useful., Comment: to be published at IEEE HPEC 2020

It was recently shown that certain subsurface hydrological inverse problems -- here framed as determining the composition of an aquifer from pressure readings -- can be solved on a quantum annealer. However, the quantum annealer performance suffered when solving problems where the aquifer was composed of materials with vastly different permeability, which is often encountered in practice. In this paper, we study why this regime is difficult and use several pre- and post-processing tools to address these issues. This study has three benefits: it improves quantum annealing performance for real-world problems in hydrology, it studies the scaling behavior for these problems (which were previously studied at a fixed size), and it elucidates a challenging class of problems that are amenable to quantum annealers.

Inverse problems often involve matching observational data using a physical model that takes a large number of parameters as input. These problems tend to be under-constrained and require regularization to impose additional structure on the solution in parameter space. A central difficulty in regularization is turning a complex conceptual model of this additional structure into a functional mathematical form to be used in the inverse analysis. In this work we propose a method of regularization involving a machine learning technique known as a variational autoencoder (VAE). The VAE is trained to map a low-dimensional set of latent variables with a simple structure to the high-dimensional parameter space that has a complex structure. We train a VAE on unconditioned realizations of the parameters for a hydrological inverse problem. These unconditioned realizations neither rely on the observational data used to perform the inverse analysis nor require any forward runs of the physical model, thus making the computational cost of generating the training data minimal. The central benefit of this approach is that regularization is then performed on the latent variables from the VAE, which can be regularized simply. A second benefit of this approach is that the VAE reduces the number of variables in the optimization problem, thus making gradient-based optimization more computationally efficient when adjoint methods are unavailable. After performing regularization and optimization on the latent variables, the VAE then decodes the problem back to the original parameter space. Our approach constitutes a novel framework for regularization and optimization, readily applicable to a wide range of inverse problems. We call the approach RegAE.