betaFeedback

WorksMathematics

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

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 10610^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×44 \times 4 and 8×88 \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.

Introduction

Quantum linear-system algorithms prepare a quantum state proportional to the solution of a linear system Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}. Following the work of Harrow, Hassidim, and Lloyd [1], later algorithms have improved the dependence of the cost on the condition number and on the precision [2, 3, 4, 5, 6]. In their modern form, the matrix is supplied as a block encoding, a unitary circuit that contains a scaled copy of A\mathbf{A} as one of its blocks, and the quantum singular value transformation (QSVT) applies a polynomial approximation of 1/x1/x to it. If the condition number of A\mathbf{A} is bounded and its block encoding is efficient, the cost of these algorithms grows only polylogarithmically with the number of unknowns [1, 2]. Linear systems from discretized partial differential equations are natural candidates for these algorithms, since their size grows rapidly with mesh refinement [7, 8]. For such systems, Aaronson [9] lists four obstacles that can remove the polylogarithmic advantage end to end: reading the right-hand side, encoding the operator, the condition number, and reading out the solution. This paper is concerned with the third: the condition number.

For the stiffness matrix of a second-order elliptic problem on a mesh with NN elements per side, the condition number grows as Θ(N2)\Theta(N^{2}). The number of queries to the block encoding grows at least linearly with the condition number, so it grows at least in proportion to N2N^{2}. The classical remedy is preconditioning: a matrix that is cheap to apply and spectrally close to the inverse is multiplied onto the system, and the condition number of the product no longer depends on NN. On a quantum computer, the preconditioner, if applied as a separate factor, must itself be supplied as a block encoding, and the subnormalizations of the block encodings multiply. For several natural preconditioners, the subnormalization of the preconditioner grows with the mesh. The product of the subnormalizations then raises the condition number seen by the circuit back to at least Θ(N2)\Theta(N^{2}), and the preconditioned solve needs at least as many queries as the unpreconditioned one [10, 11, 12]. Whether a preconditioner helps on a quantum computer therefore depends on how it enters the block encoding, not only on its classical properties.

In this paper, we ask whether the homogeneous (single-phase) preconditioner can be carried into a quantum block encoding without the multiplication of subnormalizations, and what the resulting circuit costs when it is built from gates. We consider periodic two-phase heat conduction on a structured mesh of bilinear elements, and construct the block encoding of the preconditioned operator and of its inverse.

In § 2, we set up the two-phase problem, its classical preconditioner, and the block-encoding and QSVT baseline, and show why a separately encoded preconditioner fails. In § 3, we introduce fast inversion and factor the preconditioned operator as VTΣV~\mathbf{V}^{\mathsf{T}}\mathbf{\Sigma}\widetilde{\mathbf{V}}, with every factor of norm one, and derive the Fourier structure of V\mathbf{V} in one and two dimensions. We then construct its circuit, block-encode the operator and its inverse, and give the gate-level circuit, its precision, and its cost, with the wavenumber-controlled stage from a companion paper [13]. The open-source implementation and its use are described in § 4. Numerical experiments on three cells with up to 10610^{6} unknowns, and a state-vector simulation of the entire circuit on small meshes, are reported in § 5, and the method is assessed in § 6. Table 1 lists the principal symbols used in this paper.

Principal symbols. Bold upright letters denote matrices and vectors, calligraphic letters denote unitaries and the Fourier transform, and (⋅)+(\cdot)^{+} denotes the pseudo-inverse. The left columns cover the two-phase problem and its finite element matrices; the right columns cover the Fourier structure, the block encodings, and the inverse. Symbols used in one subsection only are defined there and not listed.

SymbolMeaningSymbolMeaning
σmin⁡, σmax⁡\sigma_{\min},\ \sigma_{\max}conductivities of matrix and inclusionF\mathcal{F}two-dimensional discrete Fourier transform, N2×N2N^{2} \times N^{2}
ρ\rhocontrast σmax⁡/σmin⁡\sigma_{\max}/\sigma_{\min}k\boldsymbol{k}wavenumber
vfv_finclusion volume fractionS^(k)\widehat{S}(\boldsymbol{k})eigenvalue of K\mathbf{K} at wavenumber k\boldsymbol{k}
χ\chiphase indicator, 1 in the inclusionV\mathbf{V}partial isometry W1/2G(K+)1/2\mathbf{W}^{1/2}\mathbf{G}(\mathbf{K}^{+})^{1/2}, 8N2×N28N^{2} \times N^{2}
N, hN,\ helements per side; h=1/Nh=1/NV^(k)\widehat{\mathbf{V}}(\boldsymbol{k})unit vector of length 8 that forms V\mathbf{V}
Ndof, mN_{\mathrm{dof}},\ munknowns N2N^{2}; qubits log⁡2Ndof\log_{2}N_{\mathrm{dof}}Q(k)\mathbf{Q}(\boldsymbol{k})16×1616 \times16 unitary with first column V^(k)\widehat{\mathbf{V}}(\boldsymbol{k})
ddspatial dimensionA\mathbf{A}Kχ/σmax⁡\mathbf{K}^{\chi}/\sigma_{\max}
f\mathbf{f}heat source, orthogonal to the constant fieldsα\alphasubnormalization of an encoding of A\mathbf{A}
Kχ, K\mathbf{K}^{\chi},\ \mathbf{K}two-phase and unit-conductivity stiffness matricesκ\kappacondition number seen by QSVT
G\mathbf{G}nodal values to gradients at quadrature points, 8N2×N28N^{2} \times N^{2}Rχ\mathbf{R}_{\chi}material reflection I−2diag⁡(χ)\mathbf{I}-2\operatorname{diag}(\chi)
W\mathbf{W}quadrature weights wI, w=h2/4w\mathbf{I},\ w=h^{2}/4UV, UΣ~, UM~\mathcal{U}_{V},\ \mathcal{U}_{\widetilde{\Sigma}},\ \mathcal{U}_{\widetilde{M}}block encodings of V, Σ~, M~\mathbf{V},\ \widetilde{\boldsymbol{\Sigma}},\ \widetilde{\mathbf{M}}
Σ, Σ~\boldsymbol{\Sigma},\ \widetilde{\boldsymbol{\Sigma}}conductivity at quadrature points; Σ/σmax⁡\boldsymbol{\Sigma}/\sigma_{\max}qtq_todd QSVT polynomial that approximates 1/x1/x
σˉ\bar{\sigma}average of Σ~\widetilde{\boldsymbol{\Sigma}} over the cell, equal to vf+(1−vf)/ρv_f+(1-v_f)/\rhodt, Cd_t,\ Cdegree of qtq_t (queries to UM~\mathcal{U}_{\widetilde{M}}); its subnormalization max⁡[−1,1]∣qt∣\max_{[-1,1]}|q_t|
M, M~\mathbf{M},\ \widetilde{\mathbf{M}}preconditioned operator; its encoded formϵp\epsilon_presidual tolerance of qtq_t
Π, Π0\mathbf{\Pi},\ \mathbf{\Pi}_0projectors onto the complement of the constant fields, and onto themF, δF,\ \deltafractional bits; encoding error of UV\mathcal{U}_{V}

Table 1.

Problem Formulation and Obstacles

In this section, we formulate the two-phase problem and its preconditioned operator and examine why the classical construction does not directly carry over to block encodings.

Periodic Two-Phase Poisson Problem

Consider a periodic cell of two isotropic phases, an inclusion in a matrix, and the heterogeneous Poisson equation −∇⋅(σ∇u)=f-\nabla\cdot(\sigma\nabla u) = f on the cell (Figure 1(a)). In engineering, this equation models steady heat conduction, with uu the temperature, σ\sigma the thermal conductivity, and ff the heat source. The phases have conductivities σmax⁡\sigma_{\max} (inclusion) and σmin⁡\sigma_{\min} (matrix), with contrast ρ=σmax⁡/σmin⁡≥1\rho= \sigma_{\max}/\sigma_{\min} \ge1; vfv_f denotes the inclusion volume fraction. Such cells are the unit cells of computational homogenization [14, 15, 16], which computes their effective conductivity from one cell problem per macroscopic gradient. The worked example of this paper is a square inclusion of 0.25 volume fraction, centered in the cell (Figure 1(a)) that can be encoded at O(1)O(1) cost [17].

Figure 1. The worked example of this paper. (a) A square inclusion of volume fraction 0.25, centered in the unit cell. (b) The same cell discretized by a structured N×NN \times N mesh of bilinear Q4 elements; each element is assigned to the inclusion or the matrix by the phase indicator χ\chi, and all elements share one element matrix up to the scale σmin⁡\sigma_{\min} or σmax⁡\sigma_{\max}.

A standard approach to solving the two-phase problem is to discretize the cell with a structured N×NN \times N mesh of bilinear quadrilateral (Q4) elements, as in Figure 1(b), and perform a finite element analysis (FEA). With one unknown per node, the periodic mesh has Ndof=N2N_{\mathrm{dof}} = N^2 degrees of freedom; with NN a power of two, these are represented on m=log⁡2Ndofm = \log_2 N_{\mathrm{dof}} qubits. We denote the periodic two-phase finite-element stiffness matrix by Kχ\mathbf{K}^{\chi}.

Classical Preconditioning

The two-phase stiffness matrix Kχ\mathbf{K}^{\chi} is ill-conditioned under mesh refinement. On a mesh of width h=1/Nh = 1/N in dd dimensions, the largest eigenvalue of Kχ\mathbf{K}^{\chi} on the complement of the constant fields is Θ(hd−2)\Theta(h^{d-2}) and the smallest is Θ(hd)\Theta(h^d). The condition number of Kχ\mathbf{K}^{\chi} therefore grows as Θ(N2)\Theta(N^2) in every dimension. The conductivity contrast contributes a further factor of up to ρ\rho. One remedy is to precondition Kχ\mathbf{K}^{\chi} by the stiffness matrix K\mathbf{K} of the homogeneous cell with unit conductivity [18, 19, 20]. K\mathbf{K} is the natural choice because of two properties, discussed next.

K\mathbf{K} is diagonalizable by the Fourier transform

First, unlike Kχ\mathbf{K}^{\chi}, the matrix K\mathbf{K} is circulant. It is therefore diagonalized by the unitary two-dimensional discrete Fourier transform F\mathcal{F}, with entries Fkj=N−1e−2πik⋅j/N\mathcal{F}_{\boldsymbol{k}\boldsymbol{j}}=N^{-1}e^{-2\pi i\boldsymbol{k}\cdot\boldsymbol{j}/N} for the mesh nodes j\boldsymbol{j} and the wavenumbers k\boldsymbol{k} in {0,…,N−1}2\{0,\ldots,N-1\}^{2}:

K=F†diag⁡k(S^(k))F(1)\mathbf{K}=\mathcal{F}^{\dagger}\operatorname{diag}_{\boldsymbol{k}}\left(\widehat{S}(\boldsymbol{k})\right)\mathcal{F} \tag*{(1)}

where S^(k)\widehat{S}(\boldsymbol{k}), the eigenvalue of K\mathbf{K} at wavenumber k\boldsymbol{k}, is a trigonometric function of k\boldsymbol{k} known in closed form [21, 22, 20]. Equation (1) is worked out on the smallest mesh in Example 1.

Example 1. For N=2N=2 in two dimensions, order the four nodes and the four wavenumbers as (0,0)(0,0), (0,1)(0,1), (1,0)(1,0), (1,1)(1,1). The assembled stiffness matrix and the transform are

K=13[8−2−2−4−28−4−2−2−48−2−4−2−28],F=12[11111−11−111−1−11−1−11]=F†(2)\mathbf{K}=\frac{1}{3}\begin{bmatrix}8&-2&-2&-4\\-2&8&-4&-2\\-2&-4&8&-2\\-4&-2&-2&8\end{bmatrix},\qquad \mathcal{F}=\frac{1}{2}\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}=\mathcal{F}^{\dagger} \tag*{(2)}

since e−2πik⋅j/2=±1e^{-2\pi i\boldsymbol{k}\cdot\boldsymbol{j}/2}=\pm1. The columns of F†\mathcal{F}^{\dagger} are the constant field, the fields that alternate in yy and in xx, and the checkerboard. Multiplying each by K\mathbf{K} gives the eigenvalues S^=0,4,4,\widehat{S}=0,4,4, and 8/38/3, and

F†diag⁡(0,4,4,83)F=K.(3)\mathcal{F}^{\dagger}\operatorname{diag}\left(0,4,4,\frac{8}{3}\right)\mathcal{F}=\mathbf{K}. \tag*{(3)}

The zero belongs to the constant field, which K\mathbf{K} maps to zero. The pseudo-inverse, denoted (⋅)+(\cdot)^{+}, inverts the three nonzero entries and keeps the zero:

K+=F†diag⁡(0,14,14,38)F=132[7−3−3−1−37−1−3−3−17−3−1−3−37](4)\mathbf{K}^{+}=\mathcal{F}^{\dagger}\operatorname{diag}\left(0,\frac{1}{4},\frac{1}{4},\frac{3}{8}\right)\mathcal{F} =\frac{1}{32}\begin{bmatrix}7&-3&-3&-1\\-3&7&-1&-3\\-3&-1&7&-3\\-1&-3&-3&7\end{bmatrix} \tag*{(4)}

and (K+)1/2(\mathbf{K}^{+})^{1/2} is formed in the same way from diag⁡(0,12,12,38)\operatorname{diag}(0,\frac{1}{2},\frac{1}{2},\sqrt{\frac{3}{8}}).

The same construction, including the zero eigenvalue, holds for every NN. The constant fields form the null space of both Kχ\mathbf{K}^{\chi} and K\mathbf{K} and carry the zero eigenvalue of K\mathbf{K}; the smallest nonzero eigenvalue decreases as h2h^2 [21], so ∥K+∥2=Θ(N2)\lVert\mathbf{K}^{+}\rVert_2 = \Theta(N^2). By Equation (1), any function ff of K\mathbf{K} is F†diag⁡k(f(S^(k)))F\mathcal{F}^{\dagger}\operatorname{diag}_{\mathbf{k}}\left(f(\hat{S}(\mathbf{k}))\right)\mathcal{F}, with f(0)f(0) replaced by 00 [23]. In particular, K+\mathbf{K}^{+} and (K+)1/2(\mathbf{K}^{+})^{1/2}, the matrix used in the preconditioner below, are applied to a vector with two fast Fourier transforms, at a cost of O(Ndoflog⁡Ndof)O(N_{\mathrm{dof}}\log N_{\mathrm{dof}}) operations.

On a quantum computer, the two transforms are quantum Fourier transforms, and the cost lies in the diagonal factor. For N=2N=2, the eigenvalues are rational and their reciprocals are exact. For general NN, S^(k)\hat{S}(\mathbf{k}) is a trigonometric function of k\mathbf{k}, and applying K+\mathbf{K}^{+} or (K+)1/2(\mathbf{K}^{+})^{1/2} requires evaluating its reciprocal or square root coherently for all N2N^2 wavenumbers. This fixed-point arithmetic dominates the gate count of the method (§ 3.8).

K\mathbf{K} and Kχ\mathbf{K}^{\chi} are spectrally equivalent

The second property is that K\mathbf{K} and Kχ\mathbf{K}^{\chi} are assembled from the same element matrix and differ only in the conductivity assigned to each element, so K\mathbf{K} has the same mesh-dependent spectrum as Kχ\mathbf{K}^{\chi}, and preconditioning by K\mathbf{K} removes it. To establish this, observe that both admit the factored form [20]

Kχ=GTWΣG,K=GTWG,(5)\mathbf{K}^{\chi}=\mathbf{G}^{T}\mathbf{W}\boldsymbol{\Sigma}\mathbf{G}, \qquad\mathbf{K}=\mathbf{G}^{T}\mathbf{W}\mathbf{G}, \tag*{(5)}

where G\mathbf{G} maps nodal values to gradients at the quadrature points, W=wI\mathbf{W}=w\mathbf{I} is the common quadrature weight w=h2/4w=h^2/4, and Σ\boldsymbol{\Sigma} is diagonal with entry σmin⁡\sigma_{\min} or σmax⁡\sigma_{\max} at each quadrature point according to the phase of its element. With two gradient components at each of the four quadrature points of each of the N2N^2 elements, G\mathbf{G} is 8N2×N28N^2 \times N^2, and W\mathbf{W} and Σ\boldsymbol{\Sigma} are 8N2×8N28N^2 \times8N^2.

For a single element, with corners ordered (0,0)(0,0), (1,0)(1,0), (1,1)(1,1), (0,1)(0,1) and local coordinates (ξ,η)∈[−1,1]2(\xi,\eta)\in[-1,1]^2, the gradients of the four bilinear shape functions at a point (ξ,η)(\xi,\eta) form the 2×42\times4 matrix

B(ξ,η)=12h[−(1−η)1−η1+η−(1+η)−(1−ξ)−(1+ξ)1+ξ1−ξ].(6)\mathbf{B}(\xi,\eta)=\frac{1}{2h} \begin{bmatrix} -(1-\eta) & 1-\eta& 1+\eta& -(1+\eta) \\ -(1-\xi) & -(1+\xi) & 1+\xi& 1-\xi \end{bmatrix}. \tag*{(6)}

The element block of G\mathbf{G} stacks B\mathbf{B} at the four Gauss points (ξg,ηg)∈{±1/3}2(\xi_g,\eta_g)\in\{\pm1/\sqrt{3}\}^2, ordered as (−,−)(-,-), (+,−)(+,-), (+,+)(+,+), (−,+)(-,+), into an 8×48\times4 matrix Ge\mathbf{G}_e, with the xx- and yy-gradients at point gg in rows 2g−12g-1 and 2g2g, and G\mathbf{G} places these blocks in the rows of each element and the columns of its four nodes. With w=h2/4w=h^2/4, the element stiffness matrix is

GeTwGe=16[4−1−2−1−14−1−2−2−14−1−1−2−14],(7)\mathbf{G}_e^{T}w\mathbf{G}_e=\frac{1}{6} \begin{bmatrix} 4 & -1 & -2 & -1 \\ -1 & 4 & -1 & -2 \\ -2 & -1 & 4 & -1 \\ -1 & -2 & -1 & 4 \end{bmatrix}, \tag*{(7)}

independent of hh, and Equation (5) is the usual assembly of these element matrices, each scaled by the conductivity of its element.

Since Σ\boldsymbol{\Sigma} acts as a scalar at each quadrature point, uTKχu\mathbf{u}^{T}\mathbf{K}^{\chi}\mathbf{u} is a weighted sum over quadrature points of (Gu)TW(Gu)(\mathbf{G}\mathbf{u})^{T}\mathbf{W}(\mathbf{G}\mathbf{u}) of the unit-conductivity cell, and every nodal vector u\mathbf{u} satisfies

σmin⁡uTKu≤uTKχu≤σmax⁡uTKu.(8)\sigma_{\min}\mathbf{u}^{T}\mathbf{K}\mathbf{u}\leq\mathbf{u}^{T}\mathbf{K}^{\chi}\mathbf{u}\leq\sigma_{\max}\mathbf{u}^{T}\mathbf{K}\mathbf{u}. \tag*{(8)}

That is, the energy of the two-phase cell lies between those of a cell made entirely of matrix and a cell made entirely of inclusion phase.

To carry these energy bounds over to a preconditioned operator, we apply the preconditioner symmetrically, on both sides, so that the preconditioned operator

M=1σmax⁡(K+)1/2Kχ(K+)1/2(9)\mathbf{M}=\frac{1}{\sigma_{\max}}(\mathbf{K}^{+})^{1/2}\mathbf{K}^{\chi}(\mathbf{K}^{+})^{1/2} \tag*{(9)}

remains symmetric positive semidefinite. For v\mathbf{v} orthogonal to the constant fields, set u=(K+)1/2v\mathbf{u}=(\mathbf{K}^{+})^{1/2}\mathbf{v}. Then uTKu=vTv\mathbf{u}^{T}\mathbf{K}\mathbf{u}=\mathbf{v}^{T}\mathbf{v} and vTMv=uTKχu/σmax⁡\mathbf{v}^{T}\mathbf{M}\mathbf{v}=\mathbf{u}^{T}\mathbf{K}^{\chi}\mathbf{u}/\sigma_{\max}, and Equation (8) becomes

1ρ≤vTMvvTv≤1.(10)\frac{1}{\rho}\leq\frac{\mathbf{v}^{T}\mathbf{M}\mathbf{v}}{\mathbf{v}^{T}\mathbf{v}}\leq1. \tag*{(10)}

The Rayleigh quotient of M\mathbf{M} is thus bounded by the contrast alone, so the nonzero spectrum of M\mathbf{M} lies in [1/ρ,1][1/\rho, 1] for every mesh size NN and every phase arrangement χ\chi. Classically, preconditioning removes the mesh dependence.

Figure 2 shows both spectra for the square inclusion at ρ=10\rho= 10. Relative to the largest eigenvalue, the smallest eigenvalue of Kχ\mathbf{K}^{\chi} falls by a factor of about 4 each time NN doubles, whereas every eigenvalue of M\mathbf{M} stays in [1/ρ,1][1/\rho, 1]. The bound of Equation (10) is attained at both ends, which matters for the lower bound of § 2.7. Reversing the substitution above, take u\mathbf{u} with v=K1/2u\mathbf{v} = \mathbf{K}^{1/2}\mathbf{u}. If the gradient of u\mathbf{u} vanishes in every inclusion element, those elements contribute nothing to either Kχu\mathbf{K}^{\chi}\mathbf{u} or Ku\mathbf{K}\mathbf{u}, the remaining terms of the assembly differ only by the factor σmin⁡\sigma_{\min}, and Kχu=σmin⁡Ku\mathbf{K}^{\chi}\mathbf{u} = \sigma_{\min}\mathbf{K}\mathbf{u}; then v\mathbf{v} is an eigenvector of M\mathbf{M} with eigenvalue 1/ρ1/\rho. A field whose gradient vanishes in every matrix element gives the eigenvalue 1 in the same way. Only the fields that vary across the interface give eigenvalues strictly between the ends, which is why Figure 2(b) shows most eigenvalues at 1/ρ1/\rho or 1.

Figure 2. Sorted nonzero eigenvalues of (a) the two-phase operator Kχ\mathbf{K}^{\chi}, scaled by its largest eigenvalue, and (b) the preconditioned operator M\mathbf{M}, for the square inclusion at ρ=10\rho= 10. In (a), the smallest eigenvalue falls by a factor of about 4 per doubling of NN, which is the Θ(N2)\Theta(N^2) growth of the condition number; in (b), every eigenvalue lies in [1/ρ,1][1/\rho, 1] at every NN, and all but 2N−12N - 1 of them equal 1/ρ1/\rho or 1. Both axes are logarithmic.

These results are established classically [19, 24, 20]. They underlie the FFT-based homogenization solvers, in which preconditioned conjugate gradients converges in O(ρlog⁡(1/ϵ))O(\sqrt{\rho}\log(1/\epsilon)) iterations independent of NN, each costing O(Ndoflog⁡Ndof)O(N_{\mathrm{dof}}\log N_{\mathrm{dof}}) operations [18, 25, 22, 20].

Quantum Block Encoding

Before we ask if the classical preconditioner carries over to quantum, we must address a more basic requirement: a quantum computer applies only unitary operations, and the stiffness matrix Kχ\mathbf{K}^{\chi} is not unitary. The standard way to act with a non-unitary matrix is to embed it, suitably scaled, as the leading block of a larger unitary. A unitary U\mathcal{U} acting on aa ancilla qubits and the mm system qubits is a block encoding of a matrix A\mathbf{A} with subnormalization α\alpha [3] if

A=α(⟨0∣⊗a⊗I)U(∣0⟩⊗a⊗I)(11)\mathbf{A} = \alpha\left(\langle0|^{\otimes a}\otimes I\right)\mathcal{U}\left(|0\rangle^{\otimes a}\otimes I\right) \tag*{(11)}

that is,

U=[A/α∗∗∗](12)\mathcal{U} = \begin{bmatrix} \mathbf{A}/\alpha& * \\ * & * \end{bmatrix} \tag*{(12)}

where the blocks marked ∗* are whatever is needed to make U\mathcal{U} unitary. For example, a scalar aa with ∣a∣≤1|a| \le1 is the leading block of the 2×22 \times2 rotation

[a−1−a21−a2a](13)\begin{bmatrix} a & -\sqrt{1-a^2} \\ \sqrt{1-a^2} & a \tag*{(13)} \end{bmatrix}

which block-encodes aa with one ancilla and subnormalization 1; a scalar bb with ∣b∣>1|b| > 1 requires α≥∣b∣\alpha\ge|b|, so that b/αb/\alpha can appear as an entry of a unitary.

Operationally, preparing the ancillas in ∣0⟩⊗a|0\rangle^{\otimes a} and the system in a state ∣ϕ⟩|\phi\rangle, applying U\mathcal{U}, and measuring the ancillas in ∣0⟩⊗a|0\rangle^{\otimes a} leaves the system in the state proportional to A∣ϕ⟩\mathbf{A}|\phi\rangle, with success probability ∥Aϕ∥2/α2\|\mathbf{A}\phi\|^{2}/\alpha^{2} [23]. Two consequences follow. First, since every block of a unitary has spectral norm at most 1, the subnormalization satisfies α≥∥A∥2\alpha\ge\|\mathbf{A}\|_{2} for every block encoding, however it is built. Second, α\alpha is a cost: a larger α\alpha lowers the success probability, and, as shown in § 2.6, it multiplies the condition number. A useful block encoding therefore needs a circuit whose gate count grows at most polylogarithmically with NdofN_{\mathrm{dof}} and a subnormalization close to ∥A∥2\|\mathbf{A}\|_{2}.

For the periodic two-phase operator, an encoding that meets both requirements follows the construction of [17]: Kχ/σmax⁡\mathbf{K}^{\chi}/\sigma_{\max} is written as a linear combination of unitaries built from cyclic shifts of the position register and the material reflection Rχ=I−2diag⁡(χ)R_{\chi}=I-2\operatorname{diag}(\chi), which multiplies each inclusion element by −1-1 and each matrix element by +1+1. The number of terms is fixed by the Q4 stencil, and the subnormalization α\alpha of this encoding of Kχ/σmax⁡\mathbf{K}^{\chi}/\sigma_{\max}, the meaning of α\alpha hereafter, is independent of NN and bounded uniformly in ρ\rho; the cell geometry enters only through RχR_{\chi}, which for a square inclusion with dyadic side length costs O(1)O(1) gates [17]. The details of this encoding are not needed here; the cost of inverting it by QSVT is given in § 2.6.

Quantum Singular Value Transformation

The quantum singular value transformation (QSVT) [3, 4] applies a polynomial to a block-encoded matrix. Given a block encoding U\mathcal{U} of a symmetric matrix A\mathbf{A} with subnormalization α\alpha, and a polynomial pp with ∣p(x)∣≤1|p(x)| \le1 on [−1,1][-1,1], QSVT uses a number of queries to U\mathcal{U} equal to the degree of pp to block-encode

p(A/α)=∑jp(λj)ujujT(14)p(\mathbf{A}/\alpha)=\sum_{j}p(\lambda_j)\mathbf{u}_j\mathbf{u}_j^{\mathsf{T}} \tag*{(14)}

where λj\lambda_j and uj\mathbf{u}_j are the eigenvalues and eigenvectors of A/α\mathbf{A}/\alpha. For p(x)≈1/xp(x)\approx1/x, the polynomial must follow 1/x1/x down to the smallest eigenvalue of A/α\mathbf{A}/\alpha, so the degree is set by the condition number seen by the circuit,

κ=α∥A+∥2(15)\kappa=\alpha\|\mathbf{A}^{+}\|_{2} \tag*{(15)}

as dt=O(κlog⁡(κ/ϵ))d_t=O(\kappa\log(\kappa/\epsilon)) for accuracy ϵ\epsilon [2, 3]. We use the odd Chebyshev-iteration polynomial qtq_t of degree 2t−12t-1 of Gribling et al. [26 Cor. 12], which minimizes the relative residual max⁡1/κ≤∣x∣≤1∣xqt(x)−1∣\max_{1/\kappa\le|x|\le1}|xq_t(x)-1| among odd polynomials of that degree.

For A=Kχ/σmax⁡\mathbf{A}=\mathbf{K}^{\chi}/\sigma_{\max}, α≥∥Kχ∥2/σmax⁡\alpha\ge\|\mathbf{K}^{\chi}\|_{2}/\sigma_{\max} (§ 2.5), so κ\kappa is at least the condition number of Kχ\mathbf{K}^{\chi}, which grows as Θ(N2)\Theta(N^{2}) (§ 2.2). For the encoding of [17], α\alpha exceeds ∥Kχ∥2/σmax⁡\|\mathbf{K}^{\chi}\|_{2}/\sigma_{\max} by a factor bounded in NN, so κ\kappa, and with it dtd_t, grows as Θ(N2)\Theta(N^{2}).

Quantum Preconditioning

Multiplying block encodings multiplies their subnormalizations [3], so a preconditioner encoded as a separate factor cannot lower the condition number seen by QSVT. Under block encoding, (K+)1/2(\mathbf{K}^{+})^{1/2} must itself be encoded as the leading block of a unitary, with a subnormalization αP≥∥(K+)1/2∥2=∥K+∥21/2\alpha_{\mathrm{P}}\ge\|(\mathbf{K}^{+})^{1/2}\|_{2}=\|\mathbf{K}^{+}\|_{2}^{1/2} (§ 2.5), which grows as NN. In this subsection, we show that this scaling cancels the benefit of the preconditioner and relate the result to prior work.

The product barrier. Let U\mathcal{U} and UP\mathcal{U}_{\mathrm{P}} block-encode A=Kχ/σmax⁡\mathbf{A}=\mathbf{K}^{\chi}/\sigma_{\max} and (K+)1/2(\mathbf{K}^{+})^{1/2} with subnormalizations α\alpha and αP\alpha_{\mathrm{P}}. The product UPUUP\mathcal{U}_{\mathrm{P}}\mathcal{U}\mathcal{U}_{\mathrm{P}} block-encodes (K+)1/2A(K+)1/2=M(\mathbf{K}^{+})^{1/2}\mathbf{A}(\mathbf{K}^{+})^{1/2}=\mathbf{M} ((9)) with subnormalization αP2α\alpha_{\mathrm{P}}^{2}\alpha [3], so the condition number seen by QSVT ((15)) is κP=αP2α∥M+∥2\kappa_{\mathrm{P}}=\alpha_{\mathrm{P}}^{2}\alpha\|\mathbf{M}^{+}\|_{2}. On the complement of the constant fields, A+=(K+)1/2M+(K+)1/2\mathbf{A}^{+}=(\mathbf{K}^{+})^{1/2}\mathbf{M}^{+}(\mathbf{K}^{+})^{1/2}, so ∥A+∥2≤αP2∥M+∥2\|\mathbf{A}^{+}\|_{2}\le\alpha_{\mathrm{P}}^{2}\|\mathbf{M}^{+}\|_{2}. Hence

κP=αP2α∥M+∥2≥α∥A+∥2=κ(16)\kappa_{\mathrm{P}}=\alpha_{\mathrm{P}}^{2}\alpha\|\mathbf{M}^{+}\|_{2}\ge\alpha\|\mathbf{A}^{+}\|_{2}=\kappa \tag*{(16)}

the preconditioned solve is never cheaper than the unpreconditioned one of § 2.6, and κP\kappa_{\mathrm{P}} grows at least as Θ(N2)\Theta(N^{2}). Pechan et al. [12] prove the same inequality for every preconditioner encoded as separate factors.

An explicit bound. The lower bound on κP\kappa_P can be made explicit. If some node lies outside the closure of the inclusion, the nodal field equal to 1 at that node and 0 elsewhere has zero gradient in every inclusion element and gives the eigenvalue 1/ρ1/\rho of M\mathbf{M} (§ 2.2). Then ∥M+∥2=ρ\|\mathbf{M}^{+}\|_2=\rho, and

κP≥αρ∥K+∥2.(17)\kappa_P \ge\alpha\rho\|\mathbf{K}^{+}\|_2. \tag*{(17)}

For all three cells of § 5.2 at N=1024N=1024 and ρ=10\rho=10, with the subnormalization α=16/3\alpha=16/3 of the encoding of [17], this bound is 1.4×1061.4\times10^6; the encoding of § 3 has a condition number of at most 10 on the same mesh.

Prior work. The barrier is related to four earlier work.

  1. Preconditioned block encodings: Lapworth et al. [11] report it numerically for preconditioned quantum linear solvers.

  1. Inverse-Laplacian preconditioning: Golden et al. [10] precondition hydrological flow, a scalar elliptic problem of the type treated here, by the inverse Laplacian, and find that its norm grows linearly in the number of unknowns, so that its block encoding carries the mesh dependence it removes classically.

  1. FFT-based fixed-point iteration: Liu et al. [8] implement the iteration of Moulinec and Suquet [18] for the cell problem with quantum Fourier transforms, encoding each of its SS steps as a separate non-unitary map. The SS steps form a polynomial of degree SS in the preconditioned operator, composing them multiplies their subnormalizations, and the success probability of the composed circuit is not analyzed.

  1. Wavelet preconditioning: Bagherimehrab et al. [27] and Gharat et al. [28] transform the operator to a wavelet basis and apply a diagonal preconditioner, which bounds the condition number of the preconditioned matrix independently of NN. The cost of QSVT depends instead on the condition number seen by the circuit, which includes the subnormalization of the preconditioner and, for factors encoded separately, is bounded below by Equation (16) [12].

Deiml and Peterseim [29] avoid the barrier by building the preconditioner into the encoding, with a multilevel construction that does not require periodicity, at a subnormalization that grows with the fine-scale resolution and with the coefficient contrast. A preconditioner therefore lowers the cost of QSVT only if it is built into the block encoding of Kχ\mathbf{K}^{\chi}, not multiplied onto an encoding of Kχ\mathbf{K}^{\chi}; such an encoding is built in § 3.

Fast-Inversion Block Encoding

Several concepts and equations were introduced in § 2, and four of them are used in this section.

  • Factored form: Kχ=GTWΣG\mathbf{K}^{\chi}=\mathbf{G}^{T}\mathbf{W}^{\Sigma}\mathbf{G} and K=GTWG\mathbf{K}=\mathbf{G}^{T}\mathbf{W}\mathbf{G} (Equation (5)), where G\mathbf{G} maps nodal values to gradients at the quadrature points.

  • Fourier diagonalization: K=F†diag⁡k(S^(k))F\mathbf{K}=\mathbf{F}^{\dagger}\operatorname{diag}_{\mathbf{k}}\left(\widehat{\mathbf{S}}(\mathbf{k})\right)\mathbf{F} (Equation (1)), so functions of K\mathbf{K}, such as (K+)1/2\left(\mathbf{K}^{+}\right)^{1/2}, are diagonal in the Fourier basis.

  • Preconditioned operator: M\mathbf{M} of Equation (9), whose nonzero eigenvalues lie in [1/ρ,1][1/\rho,1] for every NN (Equation (10)).

  • Cost of QSVT: the number of queries grows with the condition number seen by the circuit, κ=α∥A+∥2\kappa=\alpha\|\mathbf{A}^{+}\|_2 (Equation (15)), which includes the subnormalization; encoding (K+)1/2\left(\mathbf{K}^{+}\right)^{1/2} as a separate factor makes it grow as N2N^2 (Equation (17)).

The aim of this section is a block encoding of M\mathbf{M} with subnormalization 1, so that the condition number seen by QSVT is at most ρ\rho for every NN, and a block encoding of its inverse. The construction follows the FFT-based solvers of homogenization step by step, and Table 2 lists the correspondence. In those solvers, a transform to wavenumbers, one small operation at each wavenumber, and a transform back apply the preconditioner in O(Ndoflog⁡Ndof)O(N_{\mathrm{dof}}\log N_{\mathrm{dof}}) operations. The circuit has the same three stages, with quantum Fourier transforms in place of FFTs and a rotation of a small register in place of the multiplication at each wavenumber.

StepFFT-based solverCircuit (this paper)
PreconditionerK+\mathbf{K}^{+} applied to a vector by two FFTs(K+)1/2(\mathbf{K}^{+})^{1/2} absorbed into the gradient operator V\mathbf{V}; never encoded on its own
To wavenumbersFFT, O(Ndoflog⁡Ndof)O(N_{\mathrm{dof}}\log N_{\mathrm{dof}}) operationsquantum Fourier transform, O(log⁡2Ndof)O(\log^{2}N_{\mathrm{dof}}) gates
At each wavenumbermultiply by S^(k)−1\hat{\mathbf{S}}(\mathbf{k})^{-1}rotate the local register to the unit vector V^(k)\hat{\mathbf{V}}(\mathbf{k})
Back to the meshinverse FFTinverse quantum Fourier transform
Conductivitymultiply by Σ\mathbf{\Sigma} at each quadrature pointUΣ\mathcal{U}_{\Sigma}, one controlled material reflection
Condition numberat most ρ\rho, every NNat most ρ\rho, every NN
Solveconjugate gradients, O(ρlog⁡(1/ϵ))O(\sqrt{\rho}\log(1/\epsilon)) iterationsQSVT, O(ρlog⁡(1/ϵp))O(\rho\log(1/\epsilon_p)) queries

Table 2. The FFT-based classical solver and the block-encoded circuit of this section, step by step. Read each row across: the right column is the quantum counterpart of the left. The costs are counts per application or per solve, not run times, and the two columns are not comparable in absolute terms.

In § 3.1, we review fast inversion of Tong et al. [30], which applies to K\mathbf{K}, and explain why it does not apply directly to the two-phase operator. In § 3.2, we write M\mathbf{M} as a product of three factors of norm 1, VTΣV\mathbf{V}^{T}\mathbf{\Sigma}\mathbf{V}. We derive the Fourier structure of V\mathbf{V} in one and two dimensions in § 3.3 and § 3.4, and build its circuit in § 3.5.

We encode Σ~\tilde{\mathbf{\Sigma}} and M\mathbf{M} in § 3.6 and the inverse in § 3.7, and in § 3.8 we give the gate-level circuit for the wavenumber-controlled stage, choose its precision, and state its cost.

Fast Inversion

Tong et al. [30] introduced fast inversion in the context of quantum preconditioning. A matrix is fast-invertible if a block encoding of its inverse can be built at a cost independent of its condition number. This holds when the matrix is diagonalized by a quantum Fourier transform and its eigenvalues are known in closed form [30 Prop. 2]. The homogeneous matrix K\mathbf{K} is of this kind (§ 2.2). For an operator A+B\mathbf{A}+\mathbf{B} with A\mathbf{A} fast-invertible, Tong et al. apply QSVT to the preconditioned operator I+A−1B\mathbf{I}+\mathbf{A}^{-1}\mathbf{B}, with a number of queries that grows with the product of the subnormalizations of A−1\mathbf{A}^{-1} and B\mathbf{B} [30 Thm. 1]. This product does not grow with the mesh when B\mathbf{B} is a lower-order term, such as a bounded potential added to the Laplacian [30].

However, this approach fails for the two-phase operator. In the natural splitting, A=σmin⁡K\mathbf{A}=\sigma_{\min}\mathbf{K} is the operator of a cell made entirely of the soft matrix, and B=Kχ−σmin⁡K\mathbf{B}=\mathbf{K}^{\chi}-\sigma_{\min}\mathbf{K} is the additional stiffness contributed by the inclusion. Unlike that of a potential, the norm of B\mathbf{B} is proportional to the largest eigenvalue of K\mathbf{K}, while the norm of A−1\mathbf{A}^{-1} is set by the smallest nonzero eigenvalue of K\mathbf{K}. Their product grows as Θ(N2)\Theta(N^{2}), and the query count of [30 Thm. 1] grows at least in proportion to N2N^{2}, as in Equation (16).

In this paper, we use fast inversion for K\mathbf{K} in a different way. Instead of preconditioning from the left, we apply (K+)1/2(\mathbf{K}^{+})^{1/2} on both sides and absorb it into the factors of Kχ\mathbf{K}^{\chi} (§ 3.2). The preconditioner is then never encoded as a separate factor, and the preconditioned operator is encoded with subnormalization 1, and it is inverted by QSVT in § 3.7.

Unit-Norm Factorization

Our goal is a block encoding of the preconditioned operator M\mathbf{M} of Equation (9) with subnormalization 1. We first rewrite M\mathbf{M} so that the preconditioner does not appear as a separate factor. The idea is to apply the preconditioner to the gradients rather than to the stiffness matrix.

We start from the factored form Kχ=GTWΣG\mathbf{K}^{\chi}=\mathbf{G}^{\mathsf{T}}\mathbf{W}\mathbf{\Sigma}\mathbf{G} of Equation (5). Substituting it into Equation (9) gives

M=1σmax⁡(K+)1/2GTWΣG(K+)1/2.\mathbf{M}=\frac{1}{\sigma_{\max}}(\mathbf{K}^{+})^{1/2}\mathbf{G}^{\mathsf{T}}\mathbf{W}\mathbf{\Sigma}\mathbf{G}(\mathbf{K}^{+})^{1/2}.

Two steps put this product in a symmetric form. First, we write Σ~=Σ/σmax⁡\tilde{\mathbf{\Sigma}}=\mathbf{\Sigma}/\sigma_{\max} for the scaled conductivity, a diagonal matrix whose entries are 1 at the quadrature points of the inclusion and 1/ρ1/\rho at those of the matrix. Second, we split W=W1/2W1/2\mathbf{W}=\mathbf{W}^{1/2}\mathbf{W}^{1/2} and move one factor W1/2\mathbf{W}^{1/2} to the right of Σ~\tilde{\mathbf{\Sigma}}, which is allowed because W1/2=wI\mathbf{W}^{1/2}=\sqrt{w}\mathbf{I} commutes with every matrix. The result is

M=[W1/2G(K+)1/2]TΣ~[W1/2G(K+)1/2].(18)\mathbf{M}=\left[\mathbf{W}^{1/2}\mathbf{G}(\mathbf{K}^{+})^{1/2}\right]^{\mathsf{T}}\tilde{\mathbf{\Sigma}}\left[\mathbf{W}^{1/2}\mathbf{G}(\mathbf{K}^{+})^{1/2}\right]. \tag*{(18)}

We denote the bracketed matrix by

V=W1/2G(K+)1/2,(19)\mathbf{V} = \mathbf{W}^{1/2}\mathbf{G}(\mathbf{K}^{+})^{1/2}, \tag*{(19)}

so that the preconditioned operator becomes

M=VTΣ~V.(20)\mathbf{M} = \mathbf{V}^{T}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}. \tag*{(20)}

Reading Equation (19) from right to left, (K+)1/2(\mathbf{K}^{+})^{1/2} maps the N2N^2 nodal values to N2N^2 nodal values, G\mathbf{G} maps nodal values to the 8 gradient values of each element, and W1/2\mathbf{W}^{1/2} multiplies each gradient value by w\sqrt{w}. The matrix V\mathbf{V} therefore has the size of G\mathbf{G}, 8N2×N28N^2 \times N^2. Its key property is that it preserves length.

Proposition 1 (Unit-norm factorization). For every mesh size NN and every phase arrangement χ\chi,

VTV=Π,∥V∥2=1,(21)\mathbf{V}^{T}\mathbf{V} = \boldsymbol{\Pi}, \qquad\lVert\mathbf{V}\rVert_{2} = 1, \tag*{(21)}

where Π\boldsymbol{\Pi} is the orthogonal projector onto the complement of the constant fields.

Proof. From Equation (5), VTV=(K+)1/2GTWG(K+)1/2=(K+)1/2K(K+)1/2\mathbf{V}^{T}\mathbf{V} = (\mathbf{K}^{+})^{1/2}\mathbf{G}^{T}\mathbf{W}\mathbf{G}(\mathbf{K}^{+})^{1/2} = (\mathbf{K}^{+})^{1/2}\mathbf{K}(\mathbf{K}^{+})^{1/2}, which is the projector onto the range of K\mathbf{K}. Since K\mathbf{K} is symmetric, this range is the orthogonal complement of its kernel, the constant fields. Finally, VTV=Π\mathbf{V}^{T}\mathbf{V} = \boldsymbol{\Pi} means that the singular values of V\mathbf{V} are the square roots of the eigenvalues of Π\boldsymbol{\Pi}, which are 0 and 1, so ∥V∥2=1\lVert\mathbf{V}\rVert_{2} = 1.

In words, V\mathbf{V} preserves the Euclidean norm of every nodal vector orthogonal to the constant fields and maps the constant fields to zero; a matrix with this property is a partial isometry [31]. Only Equation (5) is used in the proof, so the proposition holds in every dimension dd.

By Equation (20), M\mathbf{M} is thus a product of three factors of norm 1. The two copies of V\mathbf{V} depend on the mesh but not on the microstructure. The diagonal factor Σ~\widetilde{\boldsymbol{\Sigma}} is the only factor that depends on χ\chi, and its entries are 1 and 1/ρ1/\rho. The subnormalization of a product of block encodings is the product of their subnormalizations, so block encodings of V\mathbf{V} and Σ~\widetilde{\boldsymbol{\Sigma}} with subnormalization 1 give a block encoding of M\mathbf{M} with subnormalization 1. The encoding of V\mathbf{V} is constructed in Sections 3.3 to 3.5, those of Σ~\widetilde{\boldsymbol{\Sigma}} and M\mathbf{M} in Section 3.6, and that of the inverse in Section 3.7. The gate-level circuit, its precision, and its cost are then given in Section 3.8.

The Isometry in One Dimension

Since (K+)1/2(\mathbf{K}^{+})^{1/2} is a dense matrix, V\mathbf{V} is dense, and a circuit that loads its entries one by one would need a number of gates that grows with the number of entries. What makes V\mathbf{V} cheap is not sparsity but periodicity: V\mathbf{V} is circulant, so the Fourier transform diagonalizes it, and the entire matrix is carried by one number per wavenumber,

V=F†diag⁡k(V^(k))F.(22)\mathbf{V} = \mathcal{F}^{\dagger}\operatorname{diag}_{k}\bigl(\widehat{V}(k)\bigr)\mathcal{F}. \tag*{(22)}

This subsection derives V^(k)\widehat{V}(k) in one dimension, where it is a phase. Section 3.4 repeats the derivation on the Q4 mesh, where the diagonal becomes block diagonal.

Consider the periodic one-dimensional cell with NN linear elements of length h=1/Nh = 1/N and nodes j=0,…,N−1j = 0,\ldots,N-1 taken modulo NN, with one quadrature point per element of weight w=hw = h. The gradient matrix is then N×NN \times N, with (Gu)j=(uj+1−uj)/h(\mathbf{G}\mathbf{u})_j = (u_{j+1} - u_j)/h, so every row has the same two entries shifted by one column from the row above. This is where the periodicity enters: G\mathbf{G} is circulant, and so is every factor of V\mathbf{V}. Applying G\mathbf{G} to the plane wave uj=eiθju_j = e^{i\theta j}, with θ=2πk/N\theta= 2\pi k/N, multiplies it by

G^(k)=eiθ−1h=2iheiϕsin⁡ϕ,ϕ=θ2−πkN.(23)\widehat{G}(k) = \frac{e^{i\theta}-1}{h} = \frac{2i}{h}e^{i\phi}\sin\phi,\qquad\phi= \frac{\theta}{2} - \frac{\pi k}{N}. \tag*{(23)}

The same plane wave is an eigenvector of K\mathbf{K}, with eigenvalue S^(k)=w∣G^(k)∣2=(4/h)sin⁡2ϕ\widehat{S}(k) = w\lvert\widehat{G}(k)\rvert^2 = (4/h)\sin^2\phi, and of W1/2=hI\mathbf{W}^{1/2} = \sqrt{h}\mathbf{I}. The three factors of V\mathbf{V} are therefore diagonal in the same basis, and multiply wavenumber by wavenumber:

V^(k)=h G^(k) S^(k)−1/2=ieiπk/N,k=1,…,N−1,(24)\widehat{V}(k) = \sqrt{h}\,\widehat{G}(k)\,\widehat{S}(k)^{-1/2} = i e^{i\pi k/N},\qquad k = 1,\ldots,N-1, \tag*{(24)}

since sin⁡ϕ>0\sin\phi> 0 for these kk, and V^(0)=0\widehat{V}(0) = 0 at the constant field. Two things cancel: the element length hh, so the result does not depend on the mesh, and the magnitude, so every nonzero V^(k)\widehat{V}(k) has modulus 1. The second is Proposition 1 in this setting, and it is what makes the subnormalization 1: the inverse square root S^(k)−1/2\widehat{S}(k)^{-1/2}, which alone grows as NN, is absorbed exactly by the growth of G^(k)\widehat{G}(k).

The remaining structure is in the phase itself, which is linear in kk and therefore factors over its bits: one single-qubit phase gate on each qubit of the wavenumber register, and one more for the constant factor ii. The one-dimensional UV\mathcal{U}_{V} is thus Equation (22) read as a circuit, a quantum Fourier transform, n+1n+1 phase gates with n=log⁡2Nn=\log_{2}N, and the inverse transform, together with one gate, controlled on k=0k=0, that moves the input to a state outside the encoded block (§ 3.5). It needs no arithmetic.

In two dimensions, Equation (22) holds but the last paragraph does not. An element has four nodes and eight gradient values, so V^(k)\widehat{V}(k) becomes a unit vector in eight dimensions and the diagonal becomes block diagonal; and its entries depend on kk through sines and cosines of ϕ1\phi_{1} and ϕ2\phi_{2} that do not factor over the bits of kk. We derive V^(k)\widehat{V}(k) in § 3.4 and prepare it with fixed-point arithmetic in § 3.8; this arithmetic is the main cost of the entire method.

The Isometry in Two Dimensions

We now repeat the steps of § 3.3 for the Q4 mesh. Identify each element with its lower-left node, so that element jj has the nodes j+cj+c for the four corner offsets c∈{0,1}2c\in\{0,1\}^{2}. The 8 gradient values of element jj, two components at each of four Gauss points, are linear combinations of the four nodal values uj+cu_{j+c}, with coefficients from the matrix B of Equation (6) that are the same for every element. As in one dimension, G is therefore circulant, now in blocks: each element contributes a block of eight rows, and the blocks repeat with a shift. A block-circulant matrix is block-diagonalized by the discrete Fourier transform [32],

G=(F†⊗I8)blockdiag⁡kG^(k)F.(25)\mathbf{G}=(\mathcal{F}^{\dagger}\otimes I_{8})\operatorname{blockdiag}_{k}\widehat{\mathbf{G}}(k)\mathcal{F}. \tag*{(25)}

where I8I_{8} is the 8×88\times8 identity matrix.

The block G^(k)\widehat{\mathbf{G}}(k) is found as in one dimension, by applying G\mathbf{G} to the plane wave uj=eiθ⋅ju_{j}=e^{i\boldsymbol{\theta}\cdot j}: each nodal value uj+cu_{j+c} equals eiθ⋅ce^{i\boldsymbol{\theta}\cdot c} times uju_{j}, and the eight gradient values of element jj equal G^(k)\widehat{\mathbf{G}}(k) times uju_{j}. With the half angles ϕj=πkj/N\phi_{j}=\pi k_{j}/N and the Gauss points (ξg,ηg)∈{±1/3}2(\xi_{g},\eta_{g})\in\{\pm1/\sqrt{3}\}^{2}, this gives the vector of length 8

G^(k)=2ihei(ϕ1+ϕ2)[sin⁡ϕ1(cos⁡ϕ2+iηgsin⁡ϕ2)sin⁡ϕ2(cos⁡ϕ1+iξgsin⁡ϕ1)]g=1,…,4.(26)\widehat{\mathbf{G}}(k)=\frac{2i}{h}e^{i(\phi_{1}+\phi_{2})}\left[\begin{array}{c} \sin\phi_{1}(\cos\phi_{2}+i\eta_{g}\sin\phi_{2})\\ \sin\phi_{2}(\cos\phi_{1}+i\xi_{g}\sin\phi_{1}) \end{array}\right]_{g=1,\ldots,4}. \tag*{(26)}

where the subscript gg denotes the four 2×12\times1 blocks, one per Gauss point, stacked into a vector of length 8. The first entry of each block is the xx-gradient and the second the yy-gradient. Both vanish at k=0k=0, since a constant field has no gradient. The one-dimensional result of Equation (23) has the same factor (2i/h)eiϕsin⁡ϕ(2i/h)e^{i\phi}\sin\phi.

The other two factors of V are already diagonal in the Fourier basis. The weight W1/2=wI\mathbf{W}^{1/2}=\sqrt{w}I, with w=h2/4w=h^{2}/4, has the block

We1/2=wI8,(27)\mathbf{W}_{e}^{1/2}=\sqrt{w}I_{8}, \tag*{(27)}

and (K+)1/2=F†diag⁡k(S^(k)−1/2)F(\mathbf{K}^{+})^{1/2}=\mathcal{F}^{\dagger}\operatorname{diag}_{k}(\widehat{S}(k)^{-1/2})\mathcal{F} by § 2.2, with the entry for k=0k=0 set to 0. In the product V=W1/2G(K+)1/2\mathbf{V}=\mathbf{W}^{1/2}\mathbf{G}(\mathbf{K}^{+})^{1/2}, the transforms in the middle cancel, since FF†=I\mathcal{F}\mathcal{F}^{\dagger}=I, and the block-diagonal matrices multiply block by block. For every mesh size NN, this gives

V=(F†⊗I8)blockdiag⁡k(V^(k))F,V^(k)=We1/2G^(k)S^(k)−1/2,(28)\mathbf{V}=(\mathcal{F}^{\dagger}\otimes I_{8})\operatorname{blockdiag}_{k}(\widehat{\mathbf{V}}(k))\mathcal{F},\qquad\widehat{\mathbf{V}}(k)=\mathbf{W}_{e}^{1/2}\widehat{\mathbf{G}}(k)\widehat{S}(k)^{-1/2}, \tag*{(28)}

with V^(0)=0\widehat{\mathbf{V}}(0)=0, the two-dimensional counterpart of Equation (24). In one dimension, V^(k)\widehat{V}(k) is a phase; here it is a vector of length 8, and it has unit length for every k≠0k\ne0. To see this, note that Equation (28) gives VTV=F†diag⁡k(∥V^(k)∥22)F\mathbf{V}^{T}\mathbf{V}=\mathcal{F}^{\dagger}\operatorname{diag}_{k}(\lVert\widehat{\mathbf{V}}(k)\rVert_{2}^{2})\mathcal{F}, since V is real. By Proposition 1, this equals Π\Pi, the same product with 1 on the diagonal except at the constant field k=0k=0. Hence ∥V^(k)∥2=1\lVert\widehat{\mathbf{V}}(k)\rVert_{2}=1 for every k≠0k\ne0: the isometry is a unit vector at each wavenumber.

In explicit form, w=h/2\sqrt{w}=h/2 cancels the factor 2/h2/h of Equation (26), and S^(k)=w∥G^(k)∥22\widehat{S}(k)=w\lVert\widehat{\mathbf{G}}(k)\rVert_{2}^{2} by Equation (5). For k≠0k\ne0 and each Gauss point g=1,…,4g=1,\ldots,4, the xx- and yy-entries of V^(k)\widehat{\mathbf{V}}(k), in local states ∣2g−2⟩|2g-2\rangle and ∣2g−1⟩|2g-1\rangle, are

V^2g−2(k)=iei(ϕ1+ϕ2)sin⁡ϕ1(cos⁡ϕ2+iηgsin⁡ϕ2)S^(k)1/2,V^2g−1(k)=iei(ϕ1+ϕ2)sin⁡ϕ2(cos⁡ϕ1+iξgsin⁡ϕ1)S^(k)1/2.(29)\widehat{V}_{2g-2}(k)=ie^{i(\phi_{1}+\phi_{2})}\frac{\sin\phi_{1}(\cos\phi_{2}+i\eta_{g}\sin\phi_{2})}{\widehat{S}(k)^{1/2}},\qquad\widehat{V}_{2g-1}(k)=ie^{i(\phi_{1}+\phi_{2})}\frac{\sin\phi_{2}(\cos\phi_{1}+i\xi_{g}\sin\phi_{1})}{\widehat{S}(k)^{1/2}}. \tag*{(29)}

with

S^(k)=4(sin⁡2ϕ1cos⁡2ϕ2+cos⁡2ϕ1sin⁡2ϕ2+23sin⁡2ϕ1sin⁡2ϕ2).(30)\hat{S}(\mathbf{k}) = 4\left(\sin^{2}\phi_{1}\cos^{2}\phi_{2}+\cos^{2}\phi_{1}\sin^{2}\phi_{2}+\frac{2}{3}\sin^{2}\phi_{1}\sin^{2}\phi_{2}\right). \tag*{(30)}

Summing the squared moduli of Equation (29) over the four Gauss points, with ξg2=ηg2=1/3\xi_g^2=\eta_g^2=1/3, gives 1, as it must.

By Equation (28), the dense 8N2×N28N^2 \times N^2 matrix V\mathbf{V} is replaced by N2N^2 unit vectors of length 8, one per wavenumber, each given in closed form. The circuit does not prepare these vectors one at a time: a single wavenumber-controlled unitary prepares V^(k)\hat{\mathbf{V}}(\mathbf{k}) for all k\mathbf{k} in superposition, computing it from the bits of k\mathbf{k} at a cost polylogarithmic in NN (§ 3.8); a method from a table of the N2N^2 vectors needs a circuit whose size grows as N2N^2. For a wavenumber along one axis, the vector reduces to the one-dimensional phase: at k=(1,0)\mathbf{k}=(1,0), the yy-gradients vanish, S^=4sin⁡2ϕ1\hat{S}=4\sin^2\phi_1, and

V^(1,0)=12ieiπ/N(1,0,1,0,1,0,1,0)T,\hat{\mathbf{V}}(1,0)=\frac{1}{2}i e^{i\pi/N}(1,0,1,0,1,0,1,0)^{T},

the phase of Equation (24) shared equally by the xx-gradients at the four Gauss points. For the tensor-product two-point Gauss rule in dd dimensions, the vector has length 2d2d.

Circuit for the Isometry

Equation (28) has the form of an FFT-based classical solver: a transform to wavenumbers, one small operation per wavenumber, and a transform back. We build the circuit UV\mathcal{U}_{\mathcal{V}} of Figure 3 with the same three stages. In this subsection, we define UV\mathcal{U}_{\mathcal{V}} and show that it block-encodes V\mathbf{V} with subnormalization 1. The argument does not depend on how the middle stage is synthesized; its synthesis, precision, and cost are given in § 3.8.

Quantum circuit mapping mesh nodes to wavenumbers and local states

Figure 3. The transform F\mathcal{F} maps mesh nodes to wavenumbers, the wavenumber-controlled unitary Q(k)Q(\boldsymbol{k}) maps the input local state ∣0⟩\lvert0\rangle to V^(k)\widehat{\boldsymbol{V}}(\boldsymbol{k}), and F†\mathcal{F}^{\dagger} maps back to mesh nodes. The output is read in local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle. As in Qiskit, the least significant register, here the local register, is drawn at the top.

Registers. The circuit must hold the input and the output of V\mathbf{V}. The input is a nodal vector u\mathbf{u}, with one value at each of the N2N^2 nodes. The output Vu\mathbf{V}\mathbf{u} is a gradient field, with eight values at each of the N2N^2 elements: two gradient components at each of four Gauss points. Each value is therefore identified by a position, a node or an element, and by a local index. At an element, the local index selects one of the 8 values stored there; at a node, it is 0. The circuit uses one register for each. The position register has m=log⁡2N2m=\log_2 N^2 qubits and holds the index jj of a node or an element. The local register holds the local index ℓ\ell. A nodal vector is stored in local state ∣0⟩\lvert0\rangle, with its N2N^2 values in the position register, and a gradient field in local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle, where ∣2g−2⟩\lvert2g-2\rangle holds the xx-gradient and ∣2g−1⟩\lvert2g-1\rangle the yy-gradient at Gauss point gg. Between the two Fourier transforms, the position register holds a wavenumber k\mathbf{k} instead of a position. There the local rotation of the second stage below maps local state ∣0⟩\lvert0\rangle to the eight entries of V(k)^\hat{\mathbf{V}(\mathbf{k})} in Equation (29), stored in local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle with the same labels. At k=0\mathbf{k}=0, V^(0)=0\hat{\mathbf{V}}(0)=0, but Q(0)\mathbf{Q}(0) is unitary and must map ∣0⟩\lvert0\rangle to some state; mapping it into ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle would add a gradient field that does not have. The circuit therefore needs local states outside the gradient values. They are provided by a fourth qubit: the local register has four qubits and 16 states, the states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle are not used by V\mathbf{V}, and they are used in § 3.6 to carry the constant field through UΣ\mathcal{U}_{\Sigma}. In one dimension, the local register is a single qubit: ∣0⟩\lvert0\rangle holds the value and ∣1⟩\lvert1\rangle the constant field.

The three stages.

  1. Transform: F\mathcal{F} on the position register maps the nodal values to one amplitude per wavenumber k\mathbf{k}.

  1. Local rotation: for each wavenumber, a 16×1616\times16 unitary Q(k)\mathbf{Q}(\mathbf{k}) acts on the local register. For k≠0\mathbf{k}\ne0, its first column is V^(k)\hat{\mathbf{V}}(\mathbf{k}) padded with eight zeros, that is, Q(k)∣0⟩=∑ℓ=07V^ℓ(k)∣ℓ⟩\mathbf{Q}(\mathbf{k})\lvert0\rangle=\sum_{\ell=0}^{7}\hat{V}_{\ell}(\mathbf{k})\lvert\ell\rangle with the entries of Equation (29), and it maps the states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle and the states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle each to themselves. Such a unitary exists because V^(k)\hat{\mathbf{V}}(\mathbf{k}) is a unit vector (§ 3.4). For k=0\mathbf{k}=0, where V^(0)=0\hat{\mathbf{V}}(0)=0, Q(0)\mathbf{Q}(0) maps ∣0⟩\lvert0\rangle into the unused states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle. In § 3.8, Q(k)\mathbf{Q}(\mathbf{k}) is built with fixed-point arithmetic on the bits of k\mathbf{k}.

  1. Inverse transform: F†\mathcal{F}^{\dagger} on the position register maps the wavenumbers back to elements. In one dimension, Q(k)\mathbf{Q}(k) multiplies ∣0⟩\lvert0\rangle by the phase ieiπk/Ni e^{i\pi k/N} of Equation (24) for k≠0k\ne0 and maps ∣0⟩\lvert0\rangle to ∣1⟩\lvert1\rangle for k=0k=0.

Block encoding. The three stages compose to the unitary

UV=(F†⊗I16)(∑k∣k⟩⟨k∣⊗Q(k))(F⊗I16).(31)\mathcal{U}_{V}=(\mathcal{F}^{\dagger}\otimes I_{16})\left(\sum_{\boldsymbol{k}}\lvert\boldsymbol{k}\rangle\langle\boldsymbol{k}\rvert\otimes Q(\boldsymbol{k})\right)(\mathcal{F}\otimes I_{16}). \tag*{(31)}

The transforms act on the position register only, and for every k\boldsymbol{k} the components of Q(k)∣0⟩Q(\boldsymbol{k})\lvert0\rangle in local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle are the entries of V^(k)\widehat{\boldsymbol{V}}(\boldsymbol{k}), including k=0\boldsymbol{k}=\boldsymbol{0}, where Q(0)∣0⟩Q(\boldsymbol{0})\lvert0\rangle lies in the states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle and V^(0)=0\widehat{\boldsymbol{V}}(\boldsymbol{0})=\boldsymbol{0}. In words: if a nodal vector u\boldsymbol{u} is placed in local state ∣0⟩\lvert0\rangle and UV\mathcal{U}_{V} is applied, the part of the output in local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle is the gradient field Vu\boldsymbol{V}\boldsymbol{u}. Written with the projectors onto these local states, Equation (28) gives

V=(I⊗Πout)UV(I⊗Πin),Πin=∣0⟩⟨0∣,Πout=∑ℓ=07∣ℓ⟩⟨ℓ∣,(32)\boldsymbol{V}=(I\otimes\Pi_{\mathrm{out}})\mathcal{U}_{V}(I\otimes\Pi_{\mathrm{in}}),\qquad\Pi_{\mathrm{in}}=\lvert0\rangle\langle0\rvert,\qquad\Pi_{\mathrm{out}}=\sum_{\ell=0}^{7}\lvert\ell\rangle\langle\ell\rvert, \tag*{(32)}

for every mesh size NN: UV\mathcal{U}_{V} block-encodes V\boldsymbol{V} with subnormalization 1. The constant field leaves the circuit in the local states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle, outside the block, which is used in § 3.6. One flag qubit converts the projectors to the ancilla form of Equation (11) [3], so the product rule of § 2.7 applies to the products formed below. Only the first column of Q(k)Q(\boldsymbol{k}) and the two invariant sets of local states are used in the argument. The gate-level circuit of § 3.8 computes that column with fixed-point arithmetic, to within an encoding error δ\delta defined there.

Relation to fast inversion. The circuit UV\mathcal{U}_{V} has the structure of the fast-inversion circuit of Tong et al. [30], Eq. (10): a unitary transform, an operation at each eigenvalue that computes a value by reversible arithmetic and uses it to control a rotation, and the inverse transform. The difference is the following. Tong et al. place an amplitude proportional to 1/Dii1/D_{ii} on a flag qubit, so their subnormalization is at least the norm of the encoded matrix; built the same way, (K+)1/2(K^{+})^{1/2} would have a subnormalization that grows as NN, which is the separately encoded preconditioner of Equation (17). Here S^(k)−1/2\widehat{S}(\boldsymbol{k})^{-1/2} is folded into the unit vector V^(k)\widehat{\boldsymbol{V}}(\boldsymbol{k}), so Q(k)Q(\boldsymbol{k}) is unitary and the subnormalization of V\boldsymbol{V} is 1.

Block Encoding of the Preconditioned Operator

With UV\mathcal{U}_{V} in hand, the remaining factor of Equation (20) is Σ~\widetilde{\Sigma}, and it is the only place where the microstructure enters. We encode it with the material reflection Rχ=I−2diag⁡(χ)R_{\chi}=I-2\operatorname{diag}(\chi) of § 2.5, applied to the element index and extended by the identity over the local register. The reflection −Rχ-R_{\chi} is +1+1 at the quadrature points of the inclusion and −1-1 at those of the matrix, while Σ~\widetilde{\Sigma} is 11 in the inclusion and 1/ρ1/\rho in the matrix. Hence

Σ~=β0I+β1(−Rχ),β0=12(1+1/ρ),β1=12(1−1/ρ),(33)\widetilde{\Sigma}=\beta_{0}I+\beta_{1}(-R_{\chi}),\qquad\beta_{0}=\frac{1}{2}(1+1/\rho),\qquad\beta_{1}=\frac{1}{2}(1-1/\rho), \tag*{(33)}

since β0+β1=1\beta_{0}+\beta_{1}=1 and β0−β1=1/ρ\beta_{0}-\beta_{1}=1/\rho. This is a linear combination of two unitaries with nonnegative coefficients that sum to 1. The standard circuit for such a combination [3] prepares one ancilla in β0∣0⟩+β1∣1⟩\sqrt{\beta_{0}}\lvert0\rangle+\sqrt{\beta_{1}}\lvert1\rangle, applies −Rχ-R_{\chi} controlled on ∣1⟩\lvert1\rangle, and undoes the preparation. The result is a block encoding UΣ\mathcal{U}_{\Sigma} of Σ~\widetilde{\Sigma} with subnormalization β0+β1=1\beta_{0}+\beta_{1}=1.

We now combine the two encodings into UM=UV†UΣUV\mathcal{U}_{M}=\mathcal{U}_{V}^{\dagger}\mathcal{U}_{\Sigma}\mathcal{U}_{V}, which uses two queries to UV\mathcal{U}_{V} and one controlled application of RχR_{\chi}. To find the matrix it block-encodes, apply it to a nodal vector u\boldsymbol{u} in local state ∣0⟩\lvert0\rangle, and split u\boldsymbol{u} into its constant part and the rest.

  1. The part orthogonal to the constant fields: UV\mathcal{U}_{V} maps it to the gradient field Vu\boldsymbol{V}\boldsymbol{u} in the local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle, UΣ\mathcal{U}_{\Sigma} multiplies each gradient value by the scaled conductivity of its element, and UV†\mathcal{U}_{V}^{\dagger} maps the result back to local state ∣0⟩\lvert0\rangle. The block of these three steps is V†Σ~V=M\mathcal{V}^{\dagger}\widetilde{\Sigma}\mathcal{V}=\boldsymbol{M} (Equation (20)), with subnormalization 1⋅1⋅1=11\cdot1\cdot1=1.

  1. The constant part: UV\mathcal{U}_V routes it into the unused local states ∣8⟩\lvert8\rangle to ∣15⟩\lvert15\rangle, UΣ~\mathcal{U}_{\widetilde{\Sigma}} multiplies it element by element by Σ~\widetilde{\Sigma}, and UV†\mathcal{U}_V^\dagger returns the constant component of the product to local state ∣0⟩\lvert0\rangle. That component is the constant field times σˉ=vf+(1−vf)/ρ\bar{\sigma}=v_f+(1-v_f)/\rho, the average of Σ~\widetilde{\Sigma} over the cell; for the square inclusion at ρ=10\rho=10, σˉ=0.325\bar{\sigma}=0.325. Therefore, the matrix that UM\mathcal{U}_M block encodes is

M~=M+σˉΠ0,(34)\widetilde{\mathbf{M}}=\mathbf{M}+\bar{\sigma}\Pi_0, \tag*{(34)}

with Π0\Pi_0 the projector onto the constant fields. Since 1/ρ≤σˉ≤11/\rho\le\bar{\sigma}\le1, every eigenvalue of M~\widetilde{\mathbf{M}} lies in [1/ρ,1][1/\rho,1], and the condition number seen by QSVT (Equation (15)) is

κ=1⋅∥M~−1∥2≤ρ(35)\kappa=1\cdot\left\lVert\widetilde{\mathbf{M}}^{-1}\right\rVert_2\le\rho \tag*{(35)}

for every mesh size NN and every phase arrangement χ\chi.

Block Encoding of the Inverse

QSVT applied to UM\mathcal{U}_M therefore needs a polynomial that approximates 1/x1/x only on 1/ρ≤∣x∣≤11/\rho\le\lvert x\rvert\le1, and we use the odd polynomial qtq_t of Section 2.4 at κ=ρ\kappa=\rho. Gribling et al. [26] bound the error of qtq_t with a Chebyshev estimate, and the same estimate gives the residual ∣xqt(x)−1∣≤2e−(dt+1)/ρ\lvert xq_t(x)-1\rvert\le2e^{-(d_t+1)/\rho} on that interval, where dtd_t is the degree, so a residual tolerance ϵp\epsilon_p is met with

dt≤ρln⁡(2/ϵp)+1(36)d_t\le\rho\ln(2/\epsilon_p)+1 \tag*{(36)}

queries to UM\mathcal{U}_M [3]. The subnormalization C=max⁡−1≤x≤1∣qt(x)∣C=\max_{-1\le x\le1}\lvert q_t(x)\rvert grows linearly in dtd_t [26]. At ρ=10\rho=10, dt=77d_t=77 and C=13.2C=13.2 for ϵp=10−3\epsilon_p=10^{-3}, and dt=145d_t=145 and C=17.6C=17.6 for ϵp=10−6\epsilon_p=10^{-6}. Neither number depends on NN.

There are two sources of approximation errors: qtq_t matches 1/x1/x only to the tolerance ϵp\epsilon_p, and UV\mathcal{U}_V differs from an exact one by the encoding error δ\delta of Section 3.8. Each of the dtd_t queries applies UV\mathcal{U}_V and UV†\mathcal{U}_V^\dagger once, so the circuit block-encodes a matrix within 2dtCδ2d_tC\delta. For a heat source f\mathbf{f} orthogonal to the constant fields, the computed solution uQ\mathbf{u}_Q differs from the exact u=(Kχ)+f\mathbf{u}=(\mathbf{K}^{\chi})^+\mathbf{f} by

∥uQ−u∥Kχ∥u∥Kχ≤ϵp+2dtCδ.(37)\frac{\left\lVert\mathbf{u}_Q-\mathbf{u}\right\rVert_{\mathbf{K}^{\chi}}}{\left\lVert\mathbf{u}\right\rVert_{\mathbf{K}^{\chi}}}\le\epsilon_p+2d_tC\delta. \tag*{(37)}

Gate-Level Circuit, Precision, and Cost

The construction so far holds for any unitary Q(k)Q(\mathbf{k}) whose first column is V^(k)\widehat{\mathbf{V}}(\mathbf{k}) (see § 3.5). A circuit must compute that column from the bits of k\mathbf{k}, coherently for all wavenumbers, and this computation, not the Fourier transforms, sets the cost of the proposed method. In this subsection, we reduce V^(k)\widehat{\mathbf{V}}(\mathbf{k}) to a real vector of length 4, state the circuit that prepares it, which is constructed in a companion paper [13], and then choose its precision and state its cost.

A real vector of length 4. With the abbreviations

a=sin⁡ϕ1cos⁡ϕ2,b=cos⁡ϕ1sin⁡ϕ2,ζ=sin⁡ϕ1sin⁡ϕ2,(38)a=\sin\phi_1\cos\phi_2,\qquad b=\cos\phi_1\sin\phi_2,\qquad\zeta=\sin\phi_1\sin\phi_2, \tag*{(38)}

the entries of Equation (29) at Gauss point gg are a+iηgζa+i\eta_g\zeta and b+iξgζb+i\xi_g\zeta, times the common factor iei(ϕ1+ϕ2)/S^(k)1/2ie^{i(\phi_1+\phi_2)}/\widehat{S}(\mathbf{k})^{1/2}, and Equation (30) reads S^(k)=4(a2+b2+23ζ2)\widehat{S}(\mathbf{k})=4(a^2+b^2+\frac{2}{3}\zeta^2). Each entry is the sum of a part that is the same at the four Gauss points, aa or bb, and a part proportional to ηg\eta_g or ξg\xi_g. We collect these parts in four vectors of length 8, written in the local states ∣0⟩\lvert0\rangle to ∣7⟩\lvert7\rangle:

t0=i2∑g=14∣2g−2⟩,t1=i2∑g=14∣2g−1⟩,t2=−32∑g=14ηg∣2g−2⟩,t3=−32∑g=14ξg∣2g−1⟩,(39)t_0=\frac{i}{2}\sum_{g=1}^{4}\lvert2g-2\rangle,\qquad t_1=\frac{i}{2}\sum_{g=1}^{4}\lvert2g-1\rangle,\qquad t_2=-\frac{\sqrt{3}}{2}\sum_{g=1}^{4}\eta_g\lvert2g-2\rangle,\qquad t_3=-\frac{\sqrt{3}}{2}\sum_{g=1}^{4}\xi_g\lvert2g-1\rangle, \tag*{(39)}

the mean xx- and yy-gradients and the two hourglass patterns. They are orthonormal, since ξg2=ηg2=1/3\xi_g^2=\eta_g^2=1/3 and ∑gξg=∑gηg=0\sum_g\xi_g=\sum_g\eta_g=0, and substituting Equation (38) gives

V^(k)=ei(ϕ1+ϕ2)Tc(k)∥c(k)∥2,c=(a, b, ζ3, ζ3),∥c(k)∥2=12S^(k)1/2,(40)\widehat{\mathbf{V}}(\mathbf{k})=e^{i(\phi_1+\phi_2)}\mathbf{T}\frac{c(\mathbf{k})}{\lVert c(\mathbf{k})\rVert_2},\qquad c=\left(a,\ b,\ \frac{\zeta}{\sqrt{3}},\ \frac{\zeta}{\sqrt{3}}\right),\qquad \lVert c(\mathbf{k})\rVert_2=\frac{1}{2}\widehat{S}(\mathbf{k})^{1/2}, \tag*{(40)}

where T\mathbf{T} is a fixed 16×1616 \times16 unitary with T∣ℓ⟩=tℓ\mathbf{T}|\ell\rangle= \mathbf{t}_{\ell} for ℓ=0,…,3\ell= 0, \ldots, 3, completed to a unitary on the states ∣0⟩|0\rangle to ∣7⟩|7\rangle, and equal to the identity on ∣8⟩|8\rangle to ∣15⟩|15\rangle. The phase is 2n2n phase gates on the bits of k\mathbf{k}, with n=log⁡2Nn = \log_{2} N, and T\mathbf{T} is a fixed circuit on three qubits of the local register.

The wavenumber-controlled preparation. What remains is a different real unit vector c(k)/∥c(k)∥2\mathbf{c}(\mathbf{k})/\|\mathbf{c}(\mathbf{k})\|_{2} for each of the N2N^{2} wavenumbers, a multiplexed state preparation. The companion paper [13] constructs it in fixed-point arithmetic, each real number held in a register as an integer ZZ and read as Z/2FZ/2^{F}, so that the number FF of fractional bits sets the resolution 2−F2^{-F} of every computed value, and compares it there with standard state preparation multiplexed over k\mathbf{k} [33] and with a table lookup in a quantum read-only memory [34, 35, 36]. Both alternatives need O(N2)O(N^{2}) classical operations and a circuit whose description grows as N2N^{2} or NN; the arithmetic is the only method whose cost depends on NN only through FF, and it is the one used here. Below N=4096N = 4096 a table lookup needs fewer T gates [13].

We use the main result of the companion paper [13]: for N=2n≥4N = 2^{n} \ge4 and F≥nF \ge n fractional bits, there is a circuit that prepares c(k)/∥c(k)∥2\mathbf{c}(\mathbf{k})/\|\mathbf{c}(\mathbf{k})\|_{2} for all wavenumbers at once, with a number of Toffoli gates that grows as F2F^{2} and 2F+32F + 3 single-qubit rotations, independent of NN except through FF, on a work register of 2F2+35F+472F^{2} + 35F + 47 qubits that returns to ∣0⟩|0\rangle at every wavenumber, and with an error δ(k)\delta(\mathbf{k}) proportional to N2−FN2^{-F}. With the phase ei(ϕ1+ϕ2)e^{i(\phi_{1}+\phi_{2})} and the fixed unitary T\mathbf{T} of Equation (40), this circuit gives the gate-level Q~(k)\widetilde{Q}(\mathbf{k}). At k=0\mathbf{k} = \mathbf{0}, one XX gate on the most significant local qubit, controlled on k=0\mathbf{k} = \mathbf{0} at a cost of 2(2n−1)2(2n - 1) Toffoli gates, sends ∣0⟩|0\rangle into the unused states ∣8⟩|8\rangle to ∣15⟩|15\rangle; for k≠0\mathbf{k} \ne\mathbf{0}, Q~(k)\widetilde{Q}(\mathbf{k}) keeps the states ∣0⟩|0\rangle to ∣7⟩|7\rangle and ∣8⟩|8\rangle to ∣15⟩|15\rangle apart, as § 3.5 requires. Since T\mathbf{T} is unitary, Q~(k)∣0⟩\widetilde{Q}(\mathbf{k})|0\rangle differs from V^(k)\widehat{V}(\mathbf{k}) by the same δ(k)\delta(\mathbf{k}). The two are unit vectors, so a rotation in their plane maps one onto the other and differs from the identity by δ(k)\delta(\mathbf{k}); composing it with Q~(k)\widetilde{Q}(\mathbf{k}) gives an exact Q(k)Q(\mathbf{k}) of § 3.5. The gate-level UV\mathcal{U}_{V} therefore lies within δ=max⁡kδ(k)\delta= \max_{\mathbf{k}}\delta(\mathbf{k}), in the spectral norm, of a circuit that block-encodes V\mathbf{V} exactly. We call δ\delta the encoding error of UV\mathcal{U}_{V}.

Precision. The encoding error is linear in NN because the vector c(k)\mathbf{c}(\mathbf{k}) is short near k=0\mathbf{k} = \mathbf{0}: ∥c(k)∥2≥sin⁡(π/N)\|\mathbf{c}(\mathbf{k})\|_{2} \ge\sin(\pi/N) for k≠0\mathbf{k} \ne\mathbf{0}, the arithmetic computes the entries of c(k)\mathbf{c}(\mathbf{k}) to an absolute error of order 2−F2^{-F}, and the normalization divides that error by ∥c(k)∥2\|\mathbf{c}(\mathbf{k})\|_{2} [13]. The proven bound of [13] has a large constant, 2.7×1032.7 \times10^{3} at F=45F = 45, so we choose FF from the measured bound,

δ≤6N2−F,(41)\delta\le6N2^{-F}, \tag*{(41)}

an observation, not a theorem. By Equation (37), the error of the inverse stays within 2ϵp2\epsilon_{p} if 2dtCδ≤ϵp2d_{t}C\delta\le\epsilon_{p}, and requiring 6N2−F≤ϵp/(2dtC)6N2^{-F} \le\epsilon_{p}/(2d_{t}C) gives

F=⌈log⁡212NdtCϵp⌉.(42)F = \left\lceil\log_{2}\frac{12Nd_{t}C}{\epsilon_{p}} \right\rceil. \tag*{(42)}

For the square at N=1024N = 1024, ρ=10\rho= 10, and ϵp=10−6\epsilon_{p} = 10^{-6}, this gives F=45F = 45: the mesh, the polynomial, and the tolerance contribute about 10, 11.3, and 19.9 bits, and the constant 12 another 3.6. At ϵp=10−3\epsilon_{p} = 10^{-3}, it gives F=34F = 34.

Cost. With FF fixed, we count the gates that are expensive on a fault-tolerant quantum computer: Toffoli gates, and rotations of a single qubit by an arbitrary angle, which we count as they appear in the circuit, before they are compiled into Clifford and T gates. The Fourier transforms use no Toffoli gates, so all of them are in the arithmetic of the companion paper, 96 percent in its four CORDIC runs, and their number grows as F2F^{2}, that is, as (log⁡N+log⁡(1/δ))2(\log N + \log(1/\delta))^{2}. For the square at N=1024N = 1024 and F=45F = 45:

  • One application of UV\mathcal{U}_{V}: 44,462 Toffoli gates on 5,696 qubits: the 20 qubits of the position register, the 4 of the local register, and a work register of 5,672 qubits, which holds the intermediate values of the arithmetic and returns to ∣0⟩|0\rangle.

  • One query to UV\mathcal{U}_{V}: 88,926 Toffoli gates and 588 rotations on 5,699 qubits. A query applies UV\mathcal{U}_{V} twice and the controlled material reflection once, and adds three single ancillas, for UΣ\mathcal{U}_{\Sigma}, the flag of § 3.5, and QSVT. Its rotations are, for each UV\mathcal{U}_{V}, the 2F+3=932F + 3 = 93 of the arithmetic, the 2n=202n = 20 phase gates, and the 180 controlled phase gates of the two Fourier transforms, which apply the one-dimensional quantum Fourier transform to each coordinate register with n(n−1)/2n(n - 1)/2 controlled phases each [23]; and the 2 rotations of UΣ\mathcal{U}_{\Sigma}.

One application of the inverse therefore costs O(ρlog⁡(1/ϵp)(log⁡N+log⁡(1/δ))2)O\left(\rho\log(1/\epsilon_{p})\left(\log N + \log(1/\delta)\right)^{2}\right) Toffoli gates, the dtd_{t} queries of Equation (36) at the cost per query above; § 5.6 gives the count at $N = 1024`.

Implementation

The constructions of this paper are implemented in QuantumPoissonHomogenization, an open-source repository available at https://github.com/UW-ERSL/QuantumPoissonHomogenization, which also holds the code of the companion paper [13]. It requires NumPy, SciPy, Matplotlib for the figures, and Qiskit [37] and pyqsp for the circuit of Listing 3. The repository has three layers.

  • The package quantumpoissonhomogenization: fourier_symbol.py holds the closed-form eigenvalues of K\mathbf{K}, functions of K\mathbf{K} by the FFT, and K\mathbf{K} assembled element by element; isometry.py holds V^(k)\widehat{\mathbf{V}}(\mathbf{k}) in closed form, V\mathbf{V} assembled element by element, the unitary T\mathbf{T} of Equation (40), and the gate-level circuit UV\mathcal{U}_{V} of § 3.8, whose arithmetic is in the subpackage arithmetic of the companion paper.

  • The test cells and the inverse: cells.py holds the three cells of § 5.1, their material oracles, and the operators applied without dense matrices; inversion.py holds the inverse, the choice of FF, and the resource counts.

  • Scripts: in the folder papers/inversion, makeTables.py and makeFigures.py write every table and figure of the paper, after asserting every number the text quotes about them.

The simplest use of the package is on the square inclusion of the preceding sections. In Listing 1, we build the square cell at N=256N = 256 and ρ=10\rho= 10, compute the extreme eigenvalues of M~\widetilde{\mathbf{M}}, apply the inverse of § 3.7 at ϵp=10−6\epsilon_{\mathrm{p}} = 10^{-6} to the source of the cell problem for the macroscopic gradient (1,0)(1, 0), and then compute the resources of the inverse at N=1024N = 1024. Each quantity is a single function call in the package.

Listing 1: The inverse on the square at N=256N = 256, and its resources at N=1024N = 1024.

from quantumpoissonhomogenization import (Cell, extreme_eigs, inverse_error,
                                          inverse_resources)

cell = Cell("square", N=256, rho=10.0)             # 65,536 unknowns
lo, hi = extreme_eigs(cell)                       # extreme eigenvalues of Mtilde
err, d = inverse_error(cell, eps_p=1e-6)           # q_t(Mtilde), matrix-free
print(f"kappa(Mtilde)    = {hi / lo:.6f}")
print(f"degree d_t        = {d}")
print(f"energy error      = {err:.2e}")

v = inverse_resources("square", N=1024, rho=10.0, eps_p=1e-6)
print(f"F                 = {v['F']}")
print(f"Toffoli / query    = {v['toffoli_per_query']:,}")
print(f"Toffoli, inverse   = {v['toffoli_total']:.2e}")
print(f"qubits             = {v['qubits']:,}")
----- output -------------
kappa(Mtilde)      = 10.000000
degree d_t         = 145
energy error       = 5.03e-07
F                  = 45
Toffoli / query    = 88,926
Toffoli, inverse   = 1.29e+07
qubits             = 5,699

The condition number equals ρ\rho, and the inverse at dt=145d_t = 145 meets ϵp=10−6\epsilon_{\mathrm{p}} = 10^{-6}. These computations are repeated in § 5 for three cells and meshes up to $N = 1024 ({xref}Figure 5), and the resources are those of {xref}Table 6`. With "cross" or "laminate" in place of "square", the same computations are run on the other two cells.

In Listing 1, qt(M~)q_t(\widetilde{\mathbf{M}}) is applied without gates. In Listing 2, we check the gate-level circuit itself: we build UV\mathcal{U}_{V} at N=16N = 16 and F=24F = 24, simulate it gate by gate for all 256 wavenumbers, and compare the vector that Q(k)Q(\mathbf{k}) prepares with V^(k)\widehat{\mathbf{V}}(\mathbf{k}) of Equation (28).

Listing 2: The gate-level UV\mathcal{U}_{V} at N=16N = 16 and F=24F = 24, checked against V^(k)\widehat{\mathbf{V}}(\mathbf{k}) at every wavenumber.

import numpy as np
from quantumpoissonhomogenization import IsometryCircuit, vhat_exact

circ = IsometryCircuit(n=4, F=24)                 # N = 16, F = 24 fractional bits
Q, checks = circ.simulate()                       # Q(k)|0>, gate by gate, every k
N = circ.N
err = max(np.linalg.norm(Q[k1 * N + k2, :8, 0] - vhat_exact(N, k1, k2))
          for k1 in range(N) for k2 in range(N))
r = circ.resources()

print(f"wavenumbers       = {N * N}")
print(f"work register     = {checks['work_bits_left_set']} bits left set")
print(f"inputs restored   = {checks['inputs_restored']}")
print(f"max |error|       = {err:.1e}")
print(f"Toffoli gates     = {r['toffoli_total']:,}")
print(f"qubits            = {r['wires']:,}")

----- output --------------
wavenumbers        = 256
work register      = 0 bits left set
inputs restored    = True
max |error|        = 1.1e-06
Toffoli gates      = 13,349
qubits             = 2,051

The work register returns to ∣0⟩\lvert0\rangle at every wavenumber, and the prepared vectors agree with V^(k)\hat{\mathbf{V}}(\mathbf{k}) to 1.1×10−61.1 \times10^{-6}, below the bound 6N2−F=5.7×10−66N^{2-F} = 5.7 \times10^{-6} of Equation (41).

In Listings 1 and 2, the inverse is applied as a matrix polynomial, and the gate-level circuit is checked one stage at a time. In Listing 3, we build the entire inverse, from the right-hand side to the output state, as one Qiskit circuit for the square at N=4N = 4, ρ=10\rho= 10, and ϵp=10−3\epsilon_p = 10^{-3}. We then simulate it by state vector and compare the output state with the finite element solution. The circuit is described in § 5.5.

Listing 3: The entire inverse as one Qiskit circuit at N=4N = 4, simulated by state vector.

from quantumpoissonhomogenization.inversion import qiskit_inverse

r = qiskit_inverse(N=4, rho=10.0, eps_p=1e-3)  # square cell, 16 unknowns
print(f"degree d_t       = {r['d']}")
print(f"qubits            = {r['qubits']}")
print(f"CX gates          = {r['inverse'][1]:,}")
print(f"block of U_M      = {r['err_M']:.1e}")
print(f"energy error      = {r['energy']:.2e}")
print(f"P(success)        = {r['p_success']:.2e}")

----- output --------------
degree d_t          = 77
qubits              = 13
CX gates            = 25,938
block of U_M        = 2.9e-14
energy error        = 6.40e-04
P(success)          = 2.44e-03

The circuit uses 13 qubits, its block of UM\mathcal{U}_M equals M~\widetilde{\mathbf{M}} to machine precision, and the energy-norm error of its output is below ϵp=10−3\epsilon_p = 10^{-3}.

Listings 1 and 2 run from the folder papers/inversion in a few seconds, and Listing 3 in about 15 seconds. The two scripts regenerate every table and figure of the paper: python makeTables.py in about 3 minutes and python makeFigures.py in about 10 minutes. These results are reported in § 5.

Numerical Experiments

We now check the claims of § 3 on three periodic cells, for meshes up to N=1024N = 1024, that is, Ndof≈1.05×106N_{\mathrm{dof}} \approx1.05 \times10^{6} unknowns. We address four questions.

  1. Geometry: is the condition number of M~\widetilde{\mathbf{M}} equal to ρ\rho for cells of different topology (§ 5.1)?

  2. Mesh: does it stay at ρ\rho under refinement, and does the inverse keep its accuracy at a fixed degree (§ 5.2)?

  3. Gates: does the gate-level circuit encode M~\widetilde{\mathbf{M}} and its inverse to the accuracy that the encoding error predicts (§ 5.3 and § 5.4)?

  1. End to end: does the entire circuit, from the right-hand side to the output state, deliver the finite element solution (§ 5.5)?

The logical cost of the inverse on the finest mesh is then given in § 5.6.

Every table and figure of this section is written by the two scripts of § 4. No dense matrix of size NdofN_{\mathrm{dof}} is formed on the large meshes. The quantities are computed as follows.

  • Operators: functions of K\mathbf{K} are applied by the FFT, and W1/2G\mathbf{W}^{1/2}\mathbf{G} as a sparse matrix.

  • Inverse: qt(M~)q_t(\widetilde{\mathbf{M}}) is applied by the Clenshaw recurrence on the Chebyshev coefficients of qtq_t, which uses dtd_t applications of M~\widetilde{\mathbf{M}}.

  • Eigenvalues: the extreme eigenvalues are computed by Lanczos iteration.

  • Reference solutions: the two-phase problem is solved by preconditioned conjugate gradients to a relative residual of 10−1310^{-13}.

  • Gate counts: these come from the gate-level circuit of § 3.8 and from the material oracles of § 5.1.

  • Dense checks: on meshes up to N=64N = 64, the encoding and the inverse are also compared with dense matrices and a sparse direct solve.

  • Qiskit circuit: at N=4N = 4 and 88, the entire inverse is built from Qiskit gates and simulated by state vector.

Test Cells

We use the three cells of Figure 4, chosen to differ in topology. The square inclusion of the preceding sections is an isolated conductor. The cross, of nearly the same volume fraction vf=15/64v_f = 15/64, is a conductor connected across the cell in both directions. The laminate, with layers normal to xx, is anisotropic. All three cells are dyadic: the phase indicator χ\chi is a Boolean function of the two (square), four (cross), or one (laminate) leading bits of each coordinate. The controlled material reflection of § 3.6 therefore costs 2, 9, and 0 Toffoli gates, independent of NN. We check each of these circuits on every element for N=16N = 16 to 256256: it reproduces 2χ−12\chi- 1 in every case.

Figure 4. The three test cells, drawn at N=16N = 16; the inclusion phase is dark. The square is an isolated conductor, the cross a connected one, and the laminate an anisotropic cell.

For these three cells, Table 3 reports the extreme eigenvalues of M~\widetilde{\mathbf{M}} at N=256N = 256, for ρ=10\rho= 10 and ρ=104\rho= 10^{4}. In all six cases, λmin⁡=1/ρ\lambda_{\min} = 1/\rho and λmax⁡=1\lambda_{\max} = 1 to six digits, so κ(M~)=ρ\kappa(\widetilde{\mathbf{M}}) = \rho. The bound of Equation (35) is therefore attained for an isolated, a connected, and a layered conductor alike. This is the behavior predicted in § 2.2: a field whose gradient vanishes in every inclusion element gives the eigenvalue 1/ρ1/\rho, and a field whose gradient vanishes in every matrix element gives the eigenvalue 1.

geometryvfv_fRχR_\chiToffoliρ\rhoρλmin⁡\rho\lambda_{\min}λmax⁡\lambda_{\max}κ(M~)/ρ\kappa(\widetilde{\mathbf{M}})/\rho
square0.252101.0000001.0000001.0000001.000000
10410^41.0000001.0000001.0000001.000000
cross0.2349101.0000001.0000001.0000001.000000
10410^41.0000001.0000001.0000001.000000
laminate0.50101.0000001.0000001.0000001.000000
10410^41.0000001.0000001.0000001.000000

Table 3. Extreme eigenvalues of M~\widetilde{\mathbf{M}} for the three cells at N=256N = 256. “RχR_\chi Toffoli” is the number of Toffoli gates of the controlled material reflection; ρλmin⁡=λmax⁡=1\rho\lambda_{\min} = \lambda_{\max} = 1 means that the bound κ(M~)≤ρ\kappa(\widetilde{\mathbf{M}}) \le\rho of Equation (35) is attained.

Mesh Independence

In Figure 5, the mesh is refined from N=16N = 16 to 10241024 at ρ=10\rho= 10 to test three predictions of § 2 and § 3, one per panel.

Figure 5. Mesh refinement at ρ=10\rho= 10. (a) Condition number seen by QSVT for the two-phase operator (α=16/3\alpha= 16/3) of the three cells, and κ(M~)\kappa(\widetilde{\mathbf{M}}), which is the same for all three cells. (b) Relative energy-norm error of the inverse at the fixed degree dt=145d_t = 145 (ϵp=10−6\epsilon_p = 10^{-6}), for the cell-problem source of each cell, with the exact Q(k)\mathcal{Q}(\mathbf{k}). (c) Toffoli gates of one application of UV\mathcal{U}_V, with FF set by Equation (42); rotations are counted in Table 6.

(a) Condition number. For the two-phase operator, the condition number that QSVT sees is α∥(Kχ/σmax⁡)+∥2\alpha\lVert(\mathbf{K}^\chi/\sigma_{\max})^+\rVert_2 with α=16/3\alpha= 16/3. It grows by a factor of 4.00 per doubling of NN on the finest meshes and reaches 1.1×1061.1 \times10^6 for the square at N=1024N = 1024, the Θ(N2)\Theta(N^2) growth of § 2.6. The condition number of M~\widetilde{\mathbf{M}} equals ρ=10\rho= 10 to ten digits for every NN and every cell.

(b) Accuracy of the inverse. Because κ(M~)\kappa(\widetilde{\mathbf{M}}) does not change with NN, we fix the degree at dt=145d_t = 145, the degree of § 3.7 for ϵp=10−6\epsilon_p = 10^{-6}, and apply the inverse to the cell-problem source of § 5.4. The relative energy-norm error stays between 4.1×10−74.1 \times10^{-7} and 8.6×10−78.6 \times10^{-7} for all three cells and all meshes, below ϵp\epsilon_p as Equation (37) requires. The error does not grow with NN, so the degree does not need to grow either.

(c) Cost of one application of UV\mathcal{U}_V. What grows with NN is the cost of UV\mathcal{U}_V. By Equation (42), FF grows by one bit per doubling of NN, from F=39F = 39 at N=16N = 16 to F=45F = 45 at N=1024N = 1024, and the Toffoli count grows quadratically in FF (§ 3.8), from 33,680 to 44,462. The cost per query therefore grows with NN only through FF, which grows as log⁡2N\log_2 N, while the number of queries stays fixed.

Gate-Level Encoding

The block of UM=UV†UΣUV\mathcal{U}_M = \mathcal{U}_V^\dagger\mathcal{U}_\Sigma\mathcal{U}_V was derived in § 3.6 with the exact Q(k)\mathcal{Q}(\mathbf{k}). We now form that block from the simulated gate-level circuit,

(I⊗Πin)UV†UΣUV(I⊗Πin),(I \otimes\Pi_{\mathrm{in}})\mathcal{U}_V^\dagger\mathcal{U}_\Sigma\mathcal{U}_V(I \otimes\Pi_{\mathrm{in}}),
endsmid=1{ends_mid=1}

including the routing of k=0\mathbf{k}=0 into the unused local states, and compare it with M~\widetilde{\mathbf{M}} for the square at ρ=10\rho=10. Table 4 reports the spectral-norm difference for N=8N=8 and 1616 and F=24F=24 and 3232. In every case the difference lies below 2δ2\delta, as two applications of UV\mathcal{U}_{V} allow, and it falls with FF. The smallest and largest eigenvalues of the block equal 1/ρ1/\rho and 11 to 13 digits, and the constant field appears as the eigenvalue σˉ=0.325\bar{\sigma}=0.325, inside that interval.

NNFFdifference2δ2\delta
8241.8×10−71.8 \times10^{-7}2.2×10−62.2 \times10^{-6}
8326.7×10−106.7 \times10^{-10}7.4×10−97.4 \times10^{-9}
16242.1×10−72.1 \times10^{-7}2.2×10−62.2 \times10^{-6}
16328.0×10−108.0 \times10^{-10}1.0×10−81.0 \times10^{-8}

Table 4. Spectral-norm difference between the block of UV†UΣUV\mathcal{U}_V^\dagger\mathcal{U}_\Sigma\mathcal{U}_V on the input subspace, computed from the gate-level circuit with FF fractional bits, and M~\widetilde{\mathbf{M}}, for the square at ρ=10\rho= 10. The difference is the encoding error of the circuit, not a discretization error; it falls with FF and lies below 2δ2\delta, twice the encoding error of UV\mathcal{U}_V at the same NN and FF.

The Inverse on Four Heat Sources

We apply the inverse of § 3.7, with ρ=10\rho=10 and ϵp=10−6\epsilon_p=10^{-6}, to four heat sources on the square cell, each with its mean removed.

  • Smooth: the nodal source sin⁡2πxcos⁡2πy\sin2\pi x\cos2\pi y.

  • Random: a source with independent standard normal entries.

  • Cell problem: the source f=−GTWΣ eˉ\mathbf{f}=-\mathbf{G}^{\mathsf{T}}\mathbf{W}\boldsymbol{\Sigma}\,\bar{\mathbf{e}}, with eˉ\bar{\mathbf{e}} the gradient (1,0)(1,0) at every quadrature point. This is the source of the cell problem of homogenization for the macroscopic gradient (1,0)(1,0); it is concentrated at the interface between the phases and orthogonal to the constant fields, since G\mathbf{G} maps them to zero.

  • Worst case: K1/2v\mathbf{K}^{1/2}\mathbf{v}, with v\mathbf{v} an eigenvector of M\mathbf{M} at 1/ρ1/\rho. For this source the polynomial part of Equation (37) is attained.

For each source, the reference is the finite element solution from a sparse direct solve. Table 5 reports the relative error in the energy norm. It is at most ϵp\epsilon_p in every case and does not grow with NN, and for the worst-case source it equals the residual 8.69×10−78.69\times10^{-7} of qtq_t. We then replace M~\widetilde{\mathbf{M}} by the block of the gate-level circuit at N=8N=8 and 1616. The errors change by at most 1.2×10−71.2\times10^{-7} for F=24F=24 and 2.7×10−92.7\times10^{-9} for F=32F=32, within the encoding term of Equation (37).

NNdtd_tsmoothrandomcellworst
81458.4×10−78.4 \times10^{-7}8.4×10−78.4 \times10^{-7}4.7×10−74.7 \times10^{-7}8.7×10−78.7 \times10^{-7}
161458.4×10−78.4 \times10^{-7}8.6×10−78.6 \times10^{-7}4.1×10−74.1 \times10^{-7}8.7×10−78.7 \times10^{-7}
321458.5×10−78.5 \times10^{-7}8.6×10−78.6 \times10^{-7}5.0×10−75.0 \times10^{-7}8.7×10−78.7 \times10^{-7}
641458.5×10−78.5 \times10^{-7}8.6×10−78.6 \times10^{-7}4.5×10−74.5 \times10^{-7}8.7×10−78.7 \times10^{-7}

Table 5. Relative energy-norm error of the inverse with ρ=10\rho= 10 and ϵp=10−6\epsilon_p = 10^{-6} for four heat sources on the square cell, with the degree dtd_t. The errors are those of the polynomial applied to the exact M~\widetilde{\mathbf{M}}; they do not include the encoding error of the circuit.

The Inverse as One Qiskit Circuit

In § 5.3 and § 5.4, the encoding and the inverse are checked separately, and the inverse is applied as a matrix polynomial. We now build the entire inverse, from the right-hand side to the output state, as one circuit of Qiskit gates [37] and simulate it by state vector. The fixed-point arithmetic of § 3.8 cannot be part of such a simulation: its work register alone has 2F2+35F+47=7552F^2+35F+47=755 qubits at F=12F=12. We therefore build Q(k)\mathcal{Q}(\mathbf{k}) as the multiplexor of § 3.8, whose angles are computed classically for all N2N^2 wavenumbers and which needs no work register; the arithmetic is checked separately (Listing 2 and Table 4). The settings are those of § 3.7: the square at ρ=10\rho=10 and ϵp=10−3\epsilon_p=10^{-3}, so that dt=77d_t=77 and C=13.2C=13.2, on meshes with N=4N=4 and N=8N=8. The construction is Listing 3, and the circuits are built in inversion.py of the repository.

The same circuits prepare the right-hand side, with no classical preprocessing. The cell-problem source of § 5.4 is f=−GTWΣ eˉ\mathbf{f}=-\mathbf{G}^{\mathsf{T}}\mathbf{W}\boldsymbol{\Sigma}\,\bar{\mathbf{e}}; splitting W=W1/2W1/2\mathbf{W}=\mathbf{W}^{1/2}\mathbf{W}^{1/2} and using Equation (19), the preconditioned right-hand side is

ψ=(K+)1/2f=−[(K+)1/2GTW1/2]W1/2Σ eˉ=−wˉ σmax⁡ VTΣ eˉ,(43)\boldsymbol{\psi}=(\mathbf{K}^{+})^{1/2}\mathbf{f}=-\left[(\mathbf{K}^{+})^{1/2}\mathbf{G}^{\mathsf{T}}\mathbf{W}^{1/2}\right]\mathbf{W}^{1/2}\boldsymbol{\Sigma}\,\bar{\mathbf{e}}=-\sqrt{\bar{w}}\,\sigma_{\max}\,\mathbf{V}^{\mathsf{T}}\boldsymbol{\Sigma}\,\bar{\mathbf{e}}, \tag*{(43)}

so that Hadamard gates, one application of UΣ\mathcal{U}_{\Sigma} and one of UV†\mathcal{U}_{V}^{\dagger} deliver ψ\boldsymbol{\psi}, flagged on two ancillas. QSVT then applies qtq_t to UM\mathcal{U}_{M} with the phases of Dong et al. [38], and the whole circuit uses 13 qubits at N=4N=4 and 15 at N=8N=8: 2n2n position qubits, 4 local qubits, and 5 ancillas.

Before transpiling, each stage is compared with its matrix at every wavenumber and every input: Q(k)∣0⟩\mathcal{Q}(\mathbf{k})|0\rangle equals V^(k)\widehat{\mathbf{V}}(\mathbf{k}) to 1.9×10−141.9\times10^{-14}, the block of UM\mathcal{U}_{M} equals M~\widetilde{\mathbf{M}} to 3.0×10−143.0\times10^{-14}, the prepared right-hand side is parallel to ψ\boldsymbol{\psi} to 2.0×10−152.0\times10^{-15}, and the output equals qt(M~)ψ/Cq_t(\widetilde{\mathbf{M}})\boldsymbol{\psi}/C, up to the normalization of the right-hand side, to 5.1×10−145.1\times10^{-14}. Against the finite element solution from a sparse direct solve, the energy-norm error of the output is 6.4×10−46.4\times10^{-4} at N=4N=4 and 7.0×10−47.0\times10^{-4} at N=8N=8, below ϵp=10−3\epsilon_p=10^{-3}, as Equation (37) requires with δ=0\delta=0.

The success probability is 2.4×10−32.4\times10^{-3} at both meshes, the product of the probability of preparing the right-hand side, 0.0700.070 at N=4N=4 and 0.0740.074 at N=8N=8, and the probability of the inverse, which is limited by the subnormalization C=13.2C=13.2 of qtq_t; the latter factor is the expected cost of QSVT inversion and is removed by O(C)O(C) rounds of amplitude amplification [39]. The circuit size, in contrast, grows with NN: the CX count of one application of UV\mathcal{U}_{V} grows from 138 to 310 when NN doubles, most of the increase coming from the two uniformly controlled rotations, whose 3N23N^2 angles make the multiplexer grow as N2N^2 (§ 3.8). The simulation is therefore a check that the gates compose into the inverse, not evidence that this realization scales; the arithmetic of the companion paper grows only with FF, and its logical cost is given next.

Resources

Table 6 gives the logical cost of one application of the inverse for the square at N=1024N = 1024 and ρ=10\rho= 10. Each of the dtd_t queries to UM\mathcal{U}_M applies UV\mathcal{U}_V twice and the controlled material reflection once, so the total is dtd_t times the cost of a query in § 3.8.

ϵp\epsilon_pdtd_tCCFFToffoli/UV\mathcal{U}_VToffoli/queryrotations/queryToffoliqubits
10−310^{-3}7713.23425,92551,8525444.0×1064.0 \times10^63,576
10−610^{-6}14517.64544,46288,9265881.3×1071.3 \times10^75,699

Table 6. Logical resources of one application of the inverse qt(M~)q_t(\widetilde{\mathbf{M}}) for the square at N=1024N = 1024 and ρ=10\rho= 10: polynomial tolerance ϵp\epsilon_p, degree dtd_t (queries to UM\mathcal{U}_{M}), subnormalization CC, fractional bits FF from Equation (42), Toffoli gates of one application of UV\mathcal{U}_{V} and of one query, single-qubit rotations per query, total Toffoli gates, and logical qubits. Rotations are counted before synthesis into Clifford and T gates.

  • ϵp=10−6\epsilon_p = 10^{-6}: dt=145d_t = 145 queries and F=45F = 45, with 88,926 Toffoli gates and 588 rotations per query, give 1.3×1071.3 \times10^7 Toffoli gates on 5,699 logical qubits.

  • ϵp=10−3\epsilon_p = 10^{-3}: dt=77d_t = 77 queries and F=34F = 34 give 4.0×1064.0 \times10^6 Toffoli gates on 3,576 logical qubits.

Nearly all of the qubits are in the work register of the arithmetic (§ 3.8).

Costs not included. Three costs are not included in these counts.

  1. Rotation synthesis: the single-qubit rotations of Table 6 are counted before synthesis into Clifford and T gates.

  1. Phase rotations of QSVT: the dt+1d_t + 1 rotations about the input subspace each mark a subspace of a few qubits, at a number of Toffoli gates that does not depend on NN or FF.

  1. Microstructure loading: the three cells are dyadic, so their material reflections cost at most 9 Toffoli gates (§ 5.1); a microstructure without a compact description requires a material oracle whose cost grows with the number of elements.

Conclusions

Placing the closed-form inverse square root of the homogeneous operator inside the factors of the periodic two-phase operator gives a block encoding of the preconditioned operator with subnormalization 1 and condition number at most ρ\rho for every NN. The mesh enters the cost only through the quantum Fourier transforms and the wavenumber-controlled stage, both polylogarithmic in NN, and the condition number, which is the quantity that sets the number of queries, is a material constant. This is the property that classical FFT-preconditioned solvers rely on, and it does not survive a separately encoded preconditioner.

The construction is limited to what makes K\mathbf{K} fast-invertible: a uniform periodic mesh, a homogeneous reference operator with closed-form eigenvalues, and isotropic phases, whose conductivities are scalar multiples of that of the reference; Dirichlet boundaries and general coefficients require the multilevel construction compared in § 3.6.

For isotropic phases of contrast ρ\rho, the degree of the inverse grows linearly in ρ\rho: at ϵp=10−6\epsilon_p = 10^{-6}, Equation (36) gives dt=145d_t = 145 at ρ=10\rho= 10 and dt≤1.5×105d_t \le1.5 \times10^5 at ρ=104\rho= 10^4, although dtd_t does not grow with NN. The cost of each of these queries is that of the fixed-point arithmetic that prepares the vector at each wavenumber, and the precision it needs grows with NN, with dtd_t, and with the subnormalization CC (Equation (42)): at N=1024N = 1024 and ϵp=10−6\epsilon_p = 10^{-6}, F=45F = 45 fractional bits and 1.3×1071.3 \times10^7 Toffoli gates for one application of the inverse. Up to N=2048N = 2048 in two dimensions, a table lookup of classically computed angles prepares the same vectors with fewer T gates; the arithmetic is the method whose cost grows with NN only through FF. The arithmetic needs too many qubits for a state-vector simulation, so the simulation of § 5.5 builds the rotation at each wavenumber as a multiplexor, whose size grows as N2N^2; it confirms that the stages compose into the inverse, and the arithmetic is verified separately, one stage at a time. The circuit cost reported here excludes the synthesis of its rotations into Clifford and T gates and leaves the qubit count of the reversible arithmetic unoptimized. Finally, we provide the operator and its inverse as block encodings: the inverse prepares a state proportional to the solution, and extracting the field from it is not addressed. The effective conductivity is a quadratic form that does not require the field, and its readout is the subject of the companion paper. Even with that readout, classical solvers are vastly superior for problems of practical interest.

Acknowledgments

The author acknowledges the Vilas Associate Grant from the University of Wisconsin Graduate School.

Conflicts of Interest

The author declares no conflicts of interest.

Data Availability Statement

The code developed in this work is available as an open-source repository at https://github.com/UW-ERSL/QuantumPoissonHomogenization.

Use of AI Tools

The author used generative AI assistants, specifically, Claude Opus 5 (Anthropic) during the preparation of this manuscript. The tools were used for code development and drafting of text. All content was reviewed, verified, and edited by the author, who takes full responsibility for the accuracy and integrity of the work.

References

  1. [1]Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009.pubmed.ncbi.nlm.nih.gov/19905613
  2. [2]Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017.DOI
  3. [3]András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 193–204, 2019.DOI
  4. [4]John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX quantum, 2(4):040203, 2021.DOI
  5. [5]Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, and Dominic W Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3(4):040303, 2022.arxiv.org/abs/2111.08152
  6. [6]Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Marc Gerritsma, and Roeland De Breuker. Review and perspectives in quantum computing for partial differential equations in structural mechanics. Frontiers in Mechanical Engineering, page 75, 2022.DOI
  7. [7]Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. Physical Review A, 93(3):032324, 2016.DOI
  8. [8]Burigele Liu, Michael Ortiz, and Fehmi Cirak. Towards quantum computational mechanics. Computer Methods in Applied Mechanics and Engineering, 432:117403, 2024.
  9. [9]Scott Aaronson. Read the fine print. Nature Physics, 11(4):291–293, 2015.DOI
  10. [10]John Golden, Daniel O’Malley, and Hari Viswanathan. Quantum preconditioners and hydrological linear systems. arXiv preprint arXiv:2205.06379, 2022.DOI
  11. [11]Leigh Lapworth and Christoph Sünderhauf. Preconditioned block encodings for quantum linear systems. Quantum Science and Technology, 10(4):045064, 2025.DOI
  12. [12]Austin Pechan, John Golden, and Daniel O’Malley. Block encoding of the three-dimensional heterogeneous Poisson equation with application to fracture flow. Physical Review Applied, 25(4):044038, 2026.DOI
  13. [13]Krishnan Suresh. Multilevel state preparation by CORDIC arithmetic for the periodic Poisson isometry. Companion paper, in preparation, 2026.
  14. [14]Behrooz Hassani and Ernest Hinton. A review of homogenization and topology optimization I—homogenization theory for media with periodic structure. Computers & Structures, 69(6):707–717, 1998.DOI
  15. [15]Sergio Lucarini, Manas V Upadhyay, and Javier Segurado. FFT based approaches in micromechanics: fundamentals, methods and applications. Modelling and Simulation in Materials Science and Engineering, 30(2):023002, 2021.DOI
  16. [16]Erik Andreassen and Casper Schousboe Andreasen. How to determine composite material properties using numerical homogenization. Computational Materials Science, 83:488–495, 2014.DOI
  17. [17]Krishnan Suresh. Quantum block encodings for periodic two-phase finite element operators: 2d Poisson and 2d elasticity. arXiv preprint arXiv:2609.17796, 2026.arxiv.org/abs/2609.17796
  18. [18]H Moulinec and P Suquet. A numerical method for computing the overall response of nonlinear composites with complex microstructure. Computer Methods in Applied Mechanics and Engineering, 157(1–2):69–94, 1998.DOI
  19. [19]Bjørn Fredrik Nielsen, Aslak Tveito, and Wolfgang Hackbusch. Preconditioning by inverting the Laplacian: an analysis of the eigenvalues. IMA journal of numerical analysis, 29(1):24–42, 2009.DOI
  20. [20]Martin Ladecký, Richard J Leute, Ali Falsafi, Ivana Pultarová, Lars Pastewka, Till Junge, and Jan Zeman. An optimal preconditioned FFT-accelerated finite element solver for homogenization. Applied Mathematics and Computation, 446:127835, 2023.DOI
  21. [21]George J Fix and Gilbert Strang. An analysis of the finite element method, volume 2. Wellesley-Cambridge Press, 2008.
  22. [22]Matthias Leuschner and Felix Fritzen. Fourier-accelerated nodal solvers (FANS) for homogenization problems. Computational Mechanics, 62(3):359–392, 2018.DOI
  23. [23]Krishnan Suresh. Applied Quantum Computing for Engineers: Linear Solvers and Optimization. Independently published, first edition, 2026. ISBN-13: 979-8244366846.
  24. [24]Tomas Gergelits, Kent-André Mardal, Bjørn Fredrik Nielsen, and Zdenek Strakos. Laplacian preconditioning of elliptic PDEs: Localization of the eigenvalues of the discretized operator. SIAM Journal on Numerical Analysis, 57(3):1369–1394, 2019.arxiv.org/abs/1809.03790
  25. [25]Matti Schneider, Dennis Merkert, and Matthias Kabel. FFT-based homogenization for microstructures discretized by linear hexahedral elements. International journal for numerical methods in engineering, 109(10):1461–1489, 2017.DOI
  26. [26]Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi. Improving quantum linear system solvers via a gradient descent perspective. arXiv preprint arXiv:2109.04248, 2021.arxiv.org/abs/2109.04248
  27. [27]Mohsen Bagherimehrab, Kouhei Nakaji, Nathan Wiebe, Gavin K Brennen, Barry C Sanders, and Alán Aspuru-Guzik. Fast quantum algorithm for differential equations. arXiv preprint arXiv:2306.11802, 2023.arxiv.org/abs/2306.11802
  28. [28]Rakshit M Gharat, Gopikrishnan Muraleedharan, Dominic W Berry, and Gavin K Brennen. Quantum algorithm for solving differential equations using SLAC derivatives. arXiv preprint arXiv:2605.04861, 2026.arxiv.org/abs/2605.04861
  29. [29]Matthias Deiml and Daniel Peterseim. Quantum realization of the finite element method. Mathematics of Computation, 95:2637–2668, 2026. arXiv:2403.19512.DOI
  30. [30]Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, fast Green’s-function computation, and fast evaluation of matrix functions. Physical Review A, 104(3):032422, 2021.DOI
  31. [31]Adi Ben-Israel and Thomas NE Greville. Generalized inverses: theory and applications. Springer, 2003.
  32. [32]Philip J Davis. Circulant matrices, volume 120. Wiley New York, 1979.
  33. [33]Mikko Möttönen, Juha J Vartiainen, Ville Bergholm, and Martti M Salomaa. Transformation of quantum states using uniformly controlled rotations. arXiv preprint quant-ph/0407010, 2004.arxiv.org/abs/quant-ph/0407010
  34. [34]Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandra Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X, 8(4):041015, 2018.DOI
  35. [35]Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis. Quantum, 8:1375, 2024.DOI
  36. [36]Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean, and Ryan Babbush. Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum, 3:208, 2019.DOI
  37. [37]Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D Nation, Lev S Bishop, Andrew W Cross, et al. Quantum computing with qiskit. arXiv preprint arXiv:2405.08810, 2024.
  38. [38]Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103(4):042419, 2021.DOI
  39. [39]Leigh Lapworth. The probability of success in solving linear systems of equations using quantum singular value transformation. Acta Mechanica Sinica, 42(6):725776, 2026.DOI

Paper details

vlnc:W_ukwt56f7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5 (bare)

View statement
Looking for related papers…
Contents