CS Paper Radar

A Preconditioned Quantum Linear Solver for Periodic Two-Phase Heat Conduction with Mesh-Independent Condition Number

Krishnan Suresh

cs.CE math.NAmath.AP ·submitted 2026-10-30 12:56 UTC · v1

Abstract

We consider here computational homogenization of a periodic two-phase conduction problem. Quantum linear-system algorithms for its finite element discretization are limited by the condition number of the stiffness matrix. This condition number grows quadratically with the number of elements per side. Classically, preconditioning by the homogeneous (single-phase) operator bounds the condition number by the conductivity contrast, for every mesh size. On a quantum computer, however, a preconditioner encoded as a separate factor multiplies the subnormalizations, and the quadratic dependency returns. In this paper, we absorb the closed-form inverse square root of the homogeneous operator into the finite element factors. The preconditioned operator then becomes the product of a norm-preserving gradient operator $\mat{V}$, a diagonal matrix of scaled conductivities, and $\mat{V}^T$. Each factor has norm at most one. The block encoding therefore has subnormalization one, and its condition number is bounded by just the conductivity contrast, for every mesh size and in every dimension. The operator $\mat{V}$ is applied as a quantum Fourier transform, a small rotation at each wavenumber, and an inverse transform. Quantum singular value transformation then block-encodes the inverse of the preconditioned operator. We test the method numerically on three periodic cells with up to $10^6$ unknowns. The results confirm that the condition number does not depend on the mesh, and the energy-norm error of the inverse is below the polynomial tolerance at every mesh. On meshes of $4 \times 4$ and $8 \times 8$ elements, we also build the entire inverse as one Qiskit circuit and simulate it by state vector, with the rotation at each wavenumber built from uniformly controlled rotations. The output state agrees with the finite element solution to within the polynomial tolerance.

Closest papers

Nearest neighbours by meaning across the whole index.

Voxel-based block variational quantum linear solver: a hybrid quantum-classical method for static analysis of solids

cs.CE ·2026-09-24 ·Feng Wu, Chen Li, Li Zhu, Yuxiang Yang, Xu Guo
similarity 0.61
Abstract · 35 pages, 22 figures, 5 tables

In solid mechanics, finite element discretization of large-scale static problems produces large sparse linear systems whose solution requires substantial computation time and memory. The variational quantum linear solver (VQLS) offers a hybrid quantum-classical route, but its use in quantum finite element analysis is limited by the decomposition of nonunitary matrices, barren plateaus, and the measurement cost of expectation values. We propose a voxel-based block variational quantum linear solver (Voxel-BVQLS) that combines structured matrix decomposition, the principle of minimum potential energy, and batched quantum tests. First, we construct an LCU decomposition of the stiffness matrix from the recursive block-banded structure of voxel-grid finite element matrices, with the number of unitary terms bounded independently of the problem size. Second, we optimize the ansatz parameters using a minimum-potential-energy objective in place of a conventional VQLS loss function, thereby mitigating barren plateaus in the studied problems. Third, we introduce a block-Hadamard test whose circuit directly estimates weighted sums of multiple inner products, reducing the number of circuit configurations required per iteration. We assessed the proposed method in noiseless classical simulations using three examples. These examples show that the method reduces both the number of unitary terms in the LCU decomposition and the number of iterations required to converge, while still yielding solutions of finite accuracy. Voxel-BVQLS thus provides a structured hybrid quantum-classical framework for quantum finite element analysis on regular grids.

0.21

Quantum Block Encodings for Periodic Two-Phase Finite Element Operators: 2D Poisson and 2D Elasticity

cs.CE ·2026-09-15 ·Krishnan Suresh
code/dataunusual similarity 0.56
Abstract

Quantum algorithms require embedding linear operators into unitaries using block encodings. The costs associated with these block encodings determine whether a quantum speedup is achieved. Efficient \emph{shift decomposition} encodings have been proposed for 2D homogeneous scalar operators. Here, we present exact block encodings for 2D homogeneous elasticity, 2D two-phase bilinear Poisson, and 2D two-phase elasticity periodic finite-element operators. For 2D homogeneous elasticity, the resulting linear combination of unitaries (LCU) has $L = 17$ terms for every Poisson ratio $ν$ and every mesh resolution, and the subnormalization is the closed form $α= E(33+ν)/\bigl[6(1-ν^{2})\bigr]$, exceeding $\|\mathbf{K}\|_{2}$ by the resolution-independent factor $(33+ν)/24$. To address two-phase periodic microstructures, we introduce two oracles with distinct roles: a node-to-element oracle, built from cyclic shifts, that carries a nodal index to each of the four incident element indices, and a microstructure-specific material oracle that marks phase membership with a sign. This yields 25 and 57 LCU terms for two-phase Poisson and elasticity, respectively; the latter reduces to 49 at $ν= 1/3$. The term counts are independent of mesh resolution, volume fraction, and phase contrast. The subnormalizations, provided in closed form, are independent of mesh resolution and volume fraction. In the scalar case, the tight bound $α= \|\mathbf{K}\|_\infty$ is achieved whenever a node lies entirely in the stiffer phase. In the elasticity case, that bound is not attained, since the shear coupling contributes entries of both signs to a row. An open-source implementation is available at https://github.com/UW-ERSL/PyBlockEncode

0.63

Quantum oblique eigenprojection

cs.DS quant-phphysics.chem-ph ·2026-09-30 ·Alexander M. Dalzell, Yuan Su
similarity 0.55
Abstract · 41 pages, 3 figures

Every square matrix decomposes its underlying Hilbert space into generalized, nonorthogonal eigensubspaces. We show that a quantum computer can perform such an oblique eigenprojection $Π$ given block encoding access to the input matrix. Our approach has a query complexity nearly linear in the inverse gap and a normalization factor close to $\lVertΠ\rVert$ under a spectral-set condition on the input. This covers common assumptions on the numerical range or diagonalizability and matches known results for orthogonal eigenprojections. We achieve this with a two-sided block preconditioning that uses a discrete Fourier transform of the matrix resolvent. We describe applications to: (i) preparing eigenstates of matrices with complex eigenvalues, extending the quantum eigenvalue transformation algorithm of Low and Su beyond real spectra; (ii) solving continuous-time algebraic Riccati equations, cubically speeding up a prior solver of Rodenas-Ruiz, Zhao, and Lee; and (iii) solving ordinary Sylvester equations, quadratically improving a direct augmented method of Wang and Liu. Our result suggests a promising route to applying nonanalytic matrix functions on quantum computers.

0.53

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

cs.DS quant-phmath.OC ·2026-10-30 ·Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul
theory similarity 0.52
Abstract

Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.

0.06

Quantum-Classical Hybrid Methods for Optimization: Lessons from Classical Decomposition

cs.ET math.OCquant-ph ·2026-10-19 ·David E. Bernal Neira
survey similarity 0.52
Abstract · 34 pages main paper, 91 pages including supplementary material, 7 figures, invited paper after CPAIOR 2024 workshop on quantum computing

Quantum and physics-inspired solvers provide specialized sampling interfaces for Ising and quadratic unconstrained binary optimization models, but constrained optimization requires broader coordination and certification. This survey uses classical decomposition to analyze how such solvers can be integrated into hybrid quantum-classical algorithms. We distinguish formal decomposition, reformulation and reduction, and computational orchestration. For each interface, we ask what the transformation preserves, which assumptions make the outer method converge, and which certificates the implemented inner routine supplies. The central questions are whether that information meets the classical algorithm's requirements and whether hybridization improves solution quality or total cost enough to justify its coordination overhead. Benders decomposition, column generation, graph reduction, and copositive methods illustrate this distinction by separating heuristic proposals from classical certification. We also distinguish component effects within a fixed wrapper, reduction--solver interactions, and comparisons between complete quantum-enabled and classical systems. The analyzed studies provide conditional component benefits and favorable co-design evidence, but do not establish transferable end-to-end superiority over strong classical comparators. The resulting framework identifies opportunities for constraint programming and operations research in structure-preserving design, safeguarded hybrid algorithms, and controlled benchmarking.

0.09

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

cs.DS quant-ph ·2026-09-30 ·Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén, Francisca Vasconcelos
similarity 0.52
Abstract

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

0.28

Finite-Element Electromagnetic Analysis and Evaluation of Antenna Performance Metrics Using a Quantum Linear System Solver

cs.CE quant-ph ·2026-10-28 ·Hiroaki Ominato, Takahiro Ohyama, Shiro Kawabata
similarity 0.51
Abstract · 10 pages, 5 figures

Electromagnetic analysis based on the finite element method is widely used in antenna design. At higher frequencies, however, the required mesh refinement makes solving large sparse linear systems the main contributor to computational cost. Quantum linear system solvers offer a potential means of accelerating this step, but their output is a superposition state: reconstructing all components of the classical solution vector would forfeit the quantum speedup. Prior studies have proposed methods for obtaining physical quantities such as scattering cross sections and scattering parameters from the solution state. To support antenna design using fault-tolerant quantum computers, we formulate the total radiated power, the radiated power within a prescribed solid angle, and the dielectric and conductive losses as observables for efficient evaluation from a quantum solution state. These observables avoid the measurement cost of reconstructing all components of the output quantum state. We develop an end-to-end hybrid quantum--classical workflow that combines finite-element electromagnetic analysis, matrix preconditioning, a quantum linear system solver, and the evaluation of antenna design metrics. To validate the workflow, we performed numerical experiments evaluating these observables for an axisymmetric coaxially fed monopole antenna. Under idealized conditions, the relative errors in the total radiated power and the dissipated power with respect to the classical finite-element solution were on the order of $10^{-3}$, confirming the consistency of the workflow. The proposed method is expected to provide a basis for using quantum linear system solvers to evaluate antenna performance and, in the future, to design high-frequency wireless devices.

0.29

Unifying and Extending Strong Simulation of Quantum Circuits

cs.DS quant-ph ·2026-09-30 ·Floris Geerts, Rihan Hai, Matthias Lanzinger, Reinhard Pichler, Emanuel Sallinger +1 more
similarity 0.51
Abstract · 50 pages

We establish functional aggregate queries (FAQs) as a unifying language for exact classical simulation of quantum circuits. A circuit becomes a sum-product query: factors encode gates, internal wire variables are aggregated, and free boundary variables index transition amplitudes. The central insight is that distinct sources of simulation tractability can be exploited within the same InsideOut evaluation scheme. The query specifies what is computed; the evaluation plan, semiring, and representation of intermediate factors determine the cost. This view unifies structural and algebraic simulation guarantees. With explicit factor representations, FAQ evaluation recovers the treewidth bound for tensor-network contraction and yields finer sparsity-sensitive bounds via fractional covers. Over a formal phase semiring, compressed intermediate factors recover rank-width-based simulation for compatible quadratic phase representations. For Clifford circuits, affine-quadratic factors are closed under multiplication and marginalization and remain polynomial in size, yielding polynomial-time exact amplitude computation without any bounded-width assumption. Beyond these recoveries, the framework yields a new tractability criterion: tensor layout symmetry width. This parameter combines local cut-rank with separator symmetry through exact tree-tensor representations. We give a constructive evaluation bound and exhibit a circuit family with bounded tensor layout symmetry width but unbounded phase-graph rank-width and circuit line-graph treewidth. These results establish representation-aware FAQ evaluation as a common algorithmic foundation for classical simulation and a systematic route to new tractable regimes.

0.29