Block encoding the 3D heterogeneous Poisson equation with application to fracture flow

Abstract

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/\epsilon ))$, outperforming the best classical methods (with runtimes of $O(N\log N\cdot \log (1/\epsilon ))$) 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.

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum error correction below the surface code threshold
• Application-Oriented Performance Benchmarks for Quantum Computing
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Block-encoding structured matrices for data input in quantum computing
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators
• Quantum Realization of the Finite Element Method
• Quantum linear system algorithm with optimal queries to initial state preparation