Quantum linear system (QLS) algorithms offer the potential to solve large-scale linear systems exponentially faster than classical methods. However, applying QLS algorithms to real-world problems remains challenging due to issues such as state preparation, data loading, and efficient information extraction. In this work, we study the feasibility of applying QLS algorithms to solve discretized three-dimensional heterogeneous Poisson equations, with specific examples relating to groundwater flow through geologic fracture networks. We explicitly construct a block encoding for the 3D heterogeneous Poisson matrix by leveraging the sparse local structure of the discretized operator. While classical solvers benefit from preconditioning, we show that block encoding the system matrix and preconditioner separately does not improve the effective condition number that dominates the QLS runtime. This differs from classical approaches where the preconditioner and the system matrix can often be implemented independently. Nevertheless, due to the structure of the problem in three dimensions, the quantum algorithm achieves a runtime of $O(N^{2/3} \ \text{polylog } N \cdot \log(1/ε))$, outperforming the best classical methods (with runtimes of $O(N \log N \cdot \log(1/ε))$) and offering exponential memory savings. These results highlight both the promise and limitations of QLS algorithms for practical scientific computing, and point to effective condition number reduction as a key barrier in achieving quantum advantages.
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.
It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. The quantum annealing algorithm performed best for quick, approximate answers, but performance rapidly plateaued. In this paper, we utilize reverse annealing instead of forward annealing in the quantum annealing subroutine for nonnegative/binary matrix factorization problems. After an initial global search with forward annealing, reverse annealing performs a series of local searches that refine existing solutions. The combination of forward and reverse annealing significantly improves performance compared to forward annealing alone for all but the shortest run times.
Daniel O'Malley, John K. Golden, Velimir V. Vesselinov
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.