arXiv:2610.27915
Sparse block encoding with low subnormalisation for quantum linear solvers on unstructured meshes
Leigh Lapworth, Jarrett Smalley, Christoph Sünderhauf
Abstract
Unstructured meshes are widely used in modelling and simulation in Computational Fluid Dynamics (CFD) due to their geometric flexibility. However, they require an efficient block encoding circuit describing the system. Here, we present a new block encoding methodology for unstructured mesh solvers based on decomposing the system matrix into a sum of 1-sparse matrices. This block encoding is engineered to reduce subnormalisation even in the absence of structure by hiding the contribution of large matrix elements behind others. We investigate three methods of 1-sparse decomposition. Our circuit constructions can optionally take advantage of limited matrix bandwidth and repeated values. For example we consider digitisation (reduced precision), where the number of multiplexed rotation gates is equal to the number of non-unique matrix entries. We evaluate our methodologies using 2D and 3D CFD matrices for unstructured aerofoil meshes, structured cavity, and duct meshes, with and without matrix preconditioning. Our results show that we are able to achieve a block encoding with a near constant subnormalisation factor as the number of matrix preconditioning infill levels increases. This significantly reduces the subnormalised condition number and, in one case, reduces the degree of the QSP polynomial approximation to $1/x$ by 100,000. Reduced precision digitisation is shown to become more effective as the number of preconditioning infill levels is increased and, in one case, reduces the number of multiplexed rotations from 2,785,576 to 546 whilst maintaining an infidelity of $2.6\times10^{-5}$ relative to the classical solution. The effect of digitisation on QSVT solutions is demonstrated using 2D and 3D unstructured mesh aerofoil cases. Due to its flexibility and automatic applicability, we believe our 1-sparse decomposition block encoding can offer benefits to other quantum applications.
AI Summary
Quantum linear solvers for unstructured-mesh CFD need explicit block encodings whose normalisation does not erase the benefit of preconditioning. This paper constructs encodings from $A=\sum_{k=0}^{S-1}A_k$, with each $A_k$ 1-sparse, giving $\alpha=\sum_k\|A_k\|_{\max}$. It compares three classical decomposition heuristics and develops circuits using row–column indices, diagonal offsets, and dictionaries of offsets and rotation angles. A magnitude-ordered “max-search” groups large entries to reduce $\alpha$. Evaluations use structured cavity/duct and unstructured 2D/3D aerofoil matrices, with classical sparse approximate inverse (SPAI) preconditioning. Max-search yields approximately constant $\alpha$ as preconditioner infill increases; the tested decompositions have $S/s_r\lesssim1.6$. Existing $q$-norm encoding gives lower normalisation, typically by factors of $1.32$–$1.76$, while circuit analyses identify gate-cost advantages for the proposed encoding in unstructured cases. Reduced-precision digitisation compresses repeated rotation values. For a $16{,}384$-dimensional coupled duct matrix, data-loading rotations fall from $2{,}785{,}576$ to $546$, with normalised-solution infidelity $2.6\times10^{-5}$. Emulated QSVT solutions for 2D and 3D aerofoils retain comparable errors using 9- and 12-bit digitisation; the 3D calculation uses a degree-$101{,}267$ polynomial. The normalisation and digitisation trends are empirical: the SPAI norm argument does not guarantee constant $\alpha$. Digitisation accuracy deteriorates sharply below case-dependent precision thresholds, and multiplexed NOT operations still scale with the number of nonzeros. The approach requires classical preprocessing and additional qubits; encoding choices and advantages remain matrix-dependent.
Error found: The headline 546-rotation figure excludes, or fails to reconcile, the Prepare and Unprepare rotations required by the paper's own 2S+U circuit-cost formula. The claimed one-to-one correspondence between unique matrix entries and data rotations requires qualification because different sparse components normalize identical entries by different factors. The reported normalized solution distance of 7.2×10^-3 implies conventional pure-state infidelity approximately 5.18×10^-5, not the quoted 2.6×10^-5. The SPAI appendix incorrectly infers that decreasing RMS guarantees a reduced entry range and fewer occupied digitisation bins.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, 21 figures