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 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 and 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 . 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 as one of its blocks, and the quantum singular value transformation (QSVT) applies a polynomial approximation of to it. If the condition number of 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 elements per side, the condition number grows as . The number of queries to the block encoding grows at least linearly with the condition number, so it grows at least in proportion to . 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 . 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 , 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 , with every factor of norm one, and derive the Fourier structure of 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 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 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.
| Symbol | Meaning | Symbol | Meaning |
| conductivities of matrix and inclusion | two-dimensional discrete Fourier transform, | ||
| contrast | wavenumber | ||
| inclusion volume fraction | eigenvalue of at wavenumber | ||
| phase indicator, 1 in the inclusion | partial isometry , | ||
| elements per side; | unit vector of length 8 that forms | ||
| unknowns ; qubits | unitary with first column | ||
| spatial dimension | |||
| heat source, orthogonal to the constant fields | subnormalization of an encoding of | ||
| two-phase and unit-conductivity stiffness matrices | condition number seen by QSVT | ||
| nodal values to gradients at quadrature points, | material reflection | ||
| quadrature weights | block encodings of | ||
| conductivity at quadrature points; | odd QSVT polynomial that approximates | ||
| average of over the cell, equal to | degree of (queries to ); its subnormalization | ||
| preconditioned operator; its encoded form | residual tolerance of | ||
| projectors onto the complement of the constant fields, and onto them | fractional bits; encoding error of |
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 on the cell (Figure 1(a)). In engineering, this equation models steady heat conduction, with the temperature, the thermal conductivity, and the heat source. The phases have conductivities (inclusion) and (matrix), with contrast ; 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 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 mesh of bilinear Q4 elements; each element is assigned to the inclusion or the matrix by the phase indicator , and all elements share one element matrix up to the scale or .
A standard approach to solving the two-phase problem is to discretize the cell with a structured 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 degrees of freedom; with a power of two, these are represented on qubits. We denote the periodic two-phase finite-element stiffness matrix by .
Classical Preconditioning
The two-phase stiffness matrix is ill-conditioned under mesh refinement. On a mesh of width in dimensions, the largest eigenvalue of on the complement of the constant fields is and the smallest is . The condition number of therefore grows as in every dimension. The conductivity contrast contributes a further factor of up to . One remedy is to precondition by the stiffness matrix of the homogeneous cell with unit conductivity [18, 19, 20]. is the natural choice because of two properties, discussed next.
is diagonalizable by the Fourier transform
First, unlike , the matrix is circulant. It is therefore diagonalized by the unitary two-dimensional discrete Fourier transform , with entries for the mesh nodes and the wavenumbers in :
where , the eigenvalue of at wavenumber , is a trigonometric function of known in closed form [21, 22, 20]. Equation (1) is worked out on the smallest mesh in Example 1.
Example 1. For in two dimensions, order the four nodes and the four wavenumbers as , , , . The assembled stiffness matrix and the transform are
since . The columns of are the constant field, the fields that alternate in and in , and the checkerboard. Multiplying each by gives the eigenvalues and , and
The zero belongs to the constant field, which maps to zero. The pseudo-inverse, denoted , inverts the three nonzero entries and keeps the zero:
and is formed in the same way from .
The same construction, including the zero eigenvalue, holds for every . The constant fields form the null space of both and and carry the zero eigenvalue of ; the smallest nonzero eigenvalue decreases as [21], so . By Equation (1), any function of is , with replaced by [23]. In particular, and , the matrix used in the preconditioner below, are applied to a vector with two fast Fourier transforms, at a cost of operations.
On a quantum computer, the two transforms are quantum Fourier transforms, and the cost lies in the diagonal factor. For , the eigenvalues are rational and their reciprocals are exact. For general , is a trigonometric function of , and applying or requires evaluating its reciprocal or square root coherently for all wavenumbers. This fixed-point arithmetic dominates the gate count of the method (§ 3.8).
and are spectrally equivalent
The second property is that and are assembled from the same element matrix and differ only in the conductivity assigned to each element, so has the same mesh-dependent spectrum as , and preconditioning by removes it. To establish this, observe that both admit the factored form [20]
where maps nodal values to gradients at the quadrature points, is the common quadrature weight , and is diagonal with entry or 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 elements, is , and and are .
For a single element, with corners ordered , , , and local coordinates , the gradients of the four bilinear shape functions at a point form the matrix
The element block of stacks at the four Gauss points , ordered as , , , , into an matrix , with the - and -gradients at point in rows and , and places these blocks in the rows of each element and the columns of its four nodes. With , the element stiffness matrix is
independent of , and Equation (5) is the usual assembly of these element matrices, each scaled by the conductivity of its element.
Since acts as a scalar at each quadrature point, is a weighted sum over quadrature points of of the unit-conductivity cell, and every nodal vector satisfies
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
remains symmetric positive semidefinite. For orthogonal to the constant fields, set . Then and , and Equation (8) becomes
The Rayleigh quotient of is thus bounded by the contrast alone, so the nonzero spectrum of lies in for every mesh size and every phase arrangement . Classically, preconditioning removes the mesh dependence.
Figure 2 shows both spectra for the square inclusion at . Relative to the largest eigenvalue, the smallest eigenvalue of falls by a factor of about 4 each time doubles, whereas every eigenvalue of stays in . The bound of Equation (10) is attained at both ends, which matters for the lower bound of § 2.7. Reversing the substitution above, take with . If the gradient of vanishes in every inclusion element, those elements contribute nothing to either or , the remaining terms of the assembly differ only by the factor , and ; then is an eigenvector of with eigenvalue . 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 or 1.
Figure 2. Sorted nonzero eigenvalues of (a) the two-phase operator , scaled by its largest eigenvalue, and (b) the preconditioned operator , for the square inclusion at . In (a), the smallest eigenvalue falls by a factor of about 4 per doubling of , which is the growth of the condition number; in (b), every eigenvalue lies in at every , and all but of them equal 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 iterations independent of , each costing 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 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 acting on ancilla qubits and the system qubits is a block encoding of a matrix with subnormalization [3] if
that is,
where the blocks marked are whatever is needed to make unitary. For example, a scalar with is the leading block of the rotation
which block-encodes with one ancilla and subnormalization 1; a scalar with requires , so that can appear as an entry of a unitary.
Operationally, preparing the ancillas in and the system in a state , applying , and measuring the ancillas in leaves the system in the state proportional to , with success probability [23]. Two consequences follow. First, since every block of a unitary has spectral norm at most 1, the subnormalization satisfies for every block encoding, however it is built. Second, is a cost: a larger 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 and a subnormalization close to .
For the periodic two-phase operator, an encoding that meets both requirements follows the construction of [17]: is written as a linear combination of unitaries built from cyclic shifts of the position register and the material reflection , which multiplies each inclusion element by and each matrix element by . The number of terms is fixed by the Q4 stencil, and the subnormalization of this encoding of , the meaning of hereafter, is independent of and bounded uniformly in ; the cell geometry enters only through , which for a square inclusion with dyadic side length costs 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 of a symmetric matrix with subnormalization , and a polynomial with on , QSVT uses a number of queries to equal to the degree of to block-encode
where and are the eigenvalues and eigenvectors of . For , the polynomial must follow down to the smallest eigenvalue of , so the degree is set by the condition number seen by the circuit,
as for accuracy [2, 3]. We use the odd Chebyshev-iteration polynomial of degree of Gribling et al. [26 Cor. 12], which minimizes the relative residual among odd polynomials of that degree.
For , (§ 2.5), so is at least the condition number of , which grows as (§ 2.2). For the encoding of [17], exceeds by a factor bounded in , so , and with it , grows as .
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, must itself be encoded as the leading block of a unitary, with a subnormalization (§ 2.5), which grows as . 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 and block-encode and with subnormalizations and . The product block-encodes ((9)) with subnormalization [3], so the condition number seen by QSVT ((15)) is . On the complement of the constant fields, , so . Hence
the preconditioned solve is never cheaper than the unpreconditioned one of § 2.6, and grows at least as . Pechan et al. [12] prove the same inequality for every preconditioner encoded as separate factors.
An explicit bound. The lower bound on 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 of (§ 2.2). Then , and
For all three cells of § 5.2 at and , with the subnormalization of the encoding of [17], this bound is ; 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.
Preconditioned block encodings: Lapworth et al. [11] report it numerically for preconditioned quantum linear solvers.
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.
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 steps as a separate non-unitary map. The steps form a polynomial of degree in the preconditioned operator, composing them multiplies their subnormalizations, and the success probability of the composed circuit is not analyzed.
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 . 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 , not multiplied onto an encoding of ; 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: and (Equation (5)), where maps nodal values to gradients at the quadrature points.
Fourier diagonalization: (Equation (1)), so functions of , such as , are diagonal in the Fourier basis.
Preconditioned operator: of Equation (9), whose nonzero eigenvalues lie in for every (Equation (10)).
Cost of QSVT: the number of queries grows with the condition number seen by the circuit, (Equation (15)), which includes the subnormalization; encoding as a separate factor makes it grow as (Equation (17)).
The aim of this section is a block encoding of with subnormalization 1, so that the condition number seen by QSVT is at most for every , 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 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.
| Step | FFT-based solver | Circuit (this paper) |
| Preconditioner | applied to a vector by two FFTs | absorbed into the gradient operator ; never encoded on its own |
| To wavenumbers | FFT, operations | quantum Fourier transform, gates |
| At each wavenumber | multiply by | rotate the local register to the unit vector |
| Back to the mesh | inverse FFT | inverse quantum Fourier transform |
| Conductivity | multiply by at each quadrature point | , one controlled material reflection |
| Condition number | at most , every | at most , every |
| Solve | conjugate gradients, iterations | QSVT, 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 , and explain why it does not apply directly to the two-phase operator. In § 3.2, we write as a product of three factors of norm 1, . We derive the Fourier structure of in one and two dimensions in § 3.3 and § 3.4, and build its circuit in § 3.5.
We encode and 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 is of this kind (§ 2.2). For an operator with fast-invertible, Tong et al. apply QSVT to the preconditioned operator , with a number of queries that grows with the product of the subnormalizations of and [30 Thm. 1]. This product does not grow with the mesh when 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, is the operator of a cell made entirely of the soft matrix, and is the additional stiffness contributed by the inclusion. Unlike that of a potential, the norm of is proportional to the largest eigenvalue of , while the norm of is set by the smallest nonzero eigenvalue of . Their product grows as , and the query count of [30 Thm. 1] grows at least in proportion to , as in Equation (16).
In this paper, we use fast inversion for in a different way. Instead of preconditioning from the left, we apply on both sides and absorb it into the factors of (§ 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 of Equation (9) with subnormalization 1. We first rewrite 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 of Equation (5). Substituting it into Equation (9) gives
Two steps put this product in a symmetric form. First, we write for the scaled conductivity, a diagonal matrix whose entries are 1 at the quadrature points of the inclusion and at those of the matrix. Second, we split and move one factor to the right of , which is allowed because commutes with every matrix. The result is
We denote the bracketed matrix by
so that the preconditioned operator becomes
Reading Equation (19) from right to left, maps the nodal values to nodal values, maps nodal values to the 8 gradient values of each element, and multiplies each gradient value by . The matrix therefore has the size of , . Its key property is that it preserves length.
Proposition 1 (Unit-norm factorization). For every mesh size and every phase arrangement ,
where is the orthogonal projector onto the complement of the constant fields.
Proof. From Equation (5), , which is the projector onto the range of . Since is symmetric, this range is the orthogonal complement of its kernel, the constant fields. Finally, means that the singular values of are the square roots of the eigenvalues of , which are 0 and 1, so .
In words, 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 .
By Equation (20), is thus a product of three factors of norm 1. The two copies of depend on the mesh but not on the microstructure. The diagonal factor is the only factor that depends on , and its entries are 1 and . The subnormalization of a product of block encodings is the product of their subnormalizations, so block encodings of and with subnormalization 1 give a block encoding of with subnormalization 1. The encoding of is constructed in Sections 3.3 to 3.5, those of and 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 is a dense matrix, 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 cheap is not sparsity but periodicity: is circulant, so the Fourier transform diagonalizes it, and the entire matrix is carried by one number per wavenumber,
This subsection derives 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 linear elements of length and nodes taken modulo , with one quadrature point per element of weight . The gradient matrix is then , with , so every row has the same two entries shifted by one column from the row above. This is where the periodicity enters: is circulant, and so is every factor of . Applying to the plane wave , with , multiplies it by
The same plane wave is an eigenvector of , with eigenvalue , and of . The three factors of are therefore diagonal in the same basis, and multiply wavenumber by wavenumber:
since for these , and at the constant field. Two things cancel: the element length , so the result does not depend on the mesh, and the magnitude, so every nonzero has modulus 1. The second is Proposition 1 in this setting, and it is what makes the subnormalization 1: the inverse square root , which alone grows as , is absorbed exactly by the growth of .
The remaining structure is in the phase itself, which is linear in 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 . The one-dimensional is thus Equation (22) read as a circuit, a quantum Fourier transform, phase gates with , and the inverse transform, together with one gate, controlled on , 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 becomes a unit vector in eight dimensions and the diagonal becomes block diagonal; and its entries depend on through sines and cosines of and that do not factor over the bits of . We derive 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 has the nodes for the four corner offsets . The 8 gradient values of element , two components at each of four Gauss points, are linear combinations of the four nodal values , 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],
where is the identity matrix.
The block is found as in one dimension, by applying to the plane wave : each nodal value equals times , and the eight gradient values of element equal times . With the half angles and the Gauss points , this gives the vector of length 8
where the subscript denotes the four blocks, one per Gauss point, stacked into a vector of length 8. The first entry of each block is the -gradient and the second the -gradient. Both vanish at , since a constant field has no gradient. The one-dimensional result of Equation (23) has the same factor .
The other two factors of V are already diagonal in the Fourier basis. The weight , with , has the block
and by § 2.2, with the entry for set to 0. In the product , the transforms in the middle cancel, since , and the block-diagonal matrices multiply block by block. For every mesh size , this gives
with , the two-dimensional counterpart of Equation (24). In one dimension, is a phase; here it is a vector of length 8, and it has unit length for every . To see this, note that Equation (28) gives , since V is real. By Proposition 1, this equals , the same product with 1 on the diagonal except at the constant field . Hence for every : the isometry is a unit vector at each wavenumber.
In explicit form, cancels the factor of Equation (26), and by Equation (5). For and each Gauss point , the - and -entries of , in local states and , are
with
Summing the squared moduli of Equation (29) over the four Gauss points, with , gives 1, as it must.
By Equation (28), the dense matrix is replaced by 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 for all in superposition, computing it from the bits of at a cost polylogarithmic in (§ 3.8); a method from a table of the vectors needs a circuit whose size grows as . For a wavenumber along one axis, the vector reduces to the one-dimensional phase: at , the -gradients vanish, , and
the phase of Equation (24) shared equally by the -gradients at the four Gauss points. For the tensor-product two-point Gauss rule in dimensions, the vector has length .
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 of Figure 3 with the same three stages. In this subsection, we define and show that it block-encodes 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.

Figure 3. The transform maps mesh nodes to wavenumbers, the wavenumber-controlled unitary maps the input local state to , and maps back to mesh nodes. The output is read in local states to . 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 . The input is a nodal vector , with one value at each of the nodes. The output is a gradient field, with eight values at each of the 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 qubits and holds the index of a node or an element. The local register holds the local index . A nodal vector is stored in local state , with its values in the position register, and a gradient field in local states to , where holds the -gradient and the -gradient at Gauss point . Between the two Fourier transforms, the position register holds a wavenumber instead of a position. There the local rotation of the second stage below maps local state to the eight entries of in Equation (29), stored in local states to with the same labels. At , , but is unitary and must map to some state; mapping it into to 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 to are not used by , and they are used in § 3.6 to carry the constant field through . In one dimension, the local register is a single qubit: holds the value and the constant field.
The three stages.
Transform: on the position register maps the nodal values to one amplitude per wavenumber .
Local rotation: for each wavenumber, a unitary acts on the local register. For , its first column is padded with eight zeros, that is, with the entries of Equation (29), and it maps the states to and the states to each to themselves. Such a unitary exists because is a unit vector (§ 3.4). For , where , maps into the unused states to . In § 3.8, is built with fixed-point arithmetic on the bits of .
Inverse transform: on the position register maps the wavenumbers back to elements. In one dimension, multiplies by the phase of Equation (24) for and maps to for .
Block encoding. The three stages compose to the unitary
The transforms act on the position register only, and for every the components of in local states to are the entries of , including , where lies in the states to and . In words: if a nodal vector is placed in local state and is applied, the part of the output in local states to is the gradient field . Written with the projectors onto these local states, Equation (28) gives
for every mesh size : block-encodes with subnormalization 1. The constant field leaves the circuit in the local states to , 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 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 defined there.
Relation to fast inversion. The circuit 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 on a flag qubit, so their subnormalization is at least the norm of the encoded matrix; built the same way, would have a subnormalization that grows as , which is the separately encoded preconditioner of Equation (17). Here is folded into the unit vector , so is unitary and the subnormalization of is 1.
Block Encoding of the Preconditioned Operator
With in hand, the remaining factor of Equation (20) is , and it is the only place where the microstructure enters. We encode it with the material reflection of § 2.5, applied to the element index and extended by the identity over the local register. The reflection is at the quadrature points of the inclusion and at those of the matrix, while is in the inclusion and in the matrix. Hence
since and . 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 , applies controlled on , and undoes the preparation. The result is a block encoding of with subnormalization .
We now combine the two encodings into , which uses two queries to and one controlled application of . To find the matrix it block-encodes, apply it to a nodal vector in local state , and split into its constant part and the rest.
The part orthogonal to the constant fields: maps it to the gradient field in the local states to , multiplies each gradient value by the scaled conductivity of its element, and maps the result back to local state . The block of these three steps is (Equation (20)), with subnormalization .
The constant part: routes it into the unused local states to , multiplies it element by element by , and returns the constant component of the product to local state . That component is the constant field times , the average of over the cell; for the square inclusion at , . Therefore, the matrix that block encodes is
with the projector onto the constant fields. Since , every eigenvalue of lies in , and the condition number seen by QSVT (Equation (15)) is
for every mesh size and every phase arrangement .
Block Encoding of the Inverse
QSVT applied to therefore needs a polynomial that approximates only on , and we use the odd polynomial of Section 2.4 at . Gribling et al. [26] bound the error of with a Chebyshev estimate, and the same estimate gives the residual on that interval, where is the degree, so a residual tolerance is met with
queries to [3]. The subnormalization grows linearly in [26]. At , and for , and and for . Neither number depends on .
There are two sources of approximation errors: matches only to the tolerance , and differs from an exact one by the encoding error of Section 3.8. Each of the queries applies and once, so the circuit block-encodes a matrix within . For a heat source orthogonal to the constant fields, the computed solution differs from the exact by
Gate-Level Circuit, Precision, and Cost
The construction so far holds for any unitary whose first column is (see § 3.5). A circuit must compute that column from the bits of , coherently for all wavenumbers, and this computation, not the Fourier transforms, sets the cost of the proposed method. In this subsection, we reduce 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
the entries of Equation (29) at Gauss point are and , times the common factor , and Equation (30) reads . Each entry is the sum of a part that is the same at the four Gauss points, or , and a part proportional to or . We collect these parts in four vectors of length 8, written in the local states to :
the mean - and -gradients and the two hourglass patterns. They are orthonormal, since and , and substituting Equation (38) gives
where is a fixed unitary with for , completed to a unitary on the states to , and equal to the identity on to . The phase is phase gates on the bits of , with , and is a fixed circuit on three qubits of the local register.
The wavenumber-controlled preparation. What remains is a different real unit vector for each of the 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 and read as , so that the number of fractional bits sets the resolution of every computed value, and compares it there with standard state preparation multiplexed over [33] and with a table lookup in a quantum read-only memory [34, 35, 36]. Both alternatives need classical operations and a circuit whose description grows as or ; the arithmetic is the only method whose cost depends on only through , and it is the one used here. Below a table lookup needs fewer T gates [13].
We use the main result of the companion paper [13]: for and fractional bits, there is a circuit that prepares for all wavenumbers at once, with a number of Toffoli gates that grows as and single-qubit rotations, independent of except through , on a work register of qubits that returns to at every wavenumber, and with an error proportional to . With the phase and the fixed unitary of Equation (40), this circuit gives the gate-level . At , one gate on the most significant local qubit, controlled on at a cost of Toffoli gates, sends into the unused states to ; for , keeps the states to and to apart, as § 3.5 requires. Since is unitary, differs from by the same . The two are unit vectors, so a rotation in their plane maps one onto the other and differs from the identity by ; composing it with gives an exact of § 3.5. The gate-level therefore lies within , in the spectral norm, of a circuit that block-encodes exactly. We call the encoding error of .
Precision. The encoding error is linear in because the vector is short near : for , the arithmetic computes the entries of to an absolute error of order , and the normalization divides that error by [13]. The proven bound of [13] has a large constant, at , so we choose from the measured bound,
an observation, not a theorem. By Equation (37), the error of the inverse stays within if , and requiring gives
For the square at , , and , this gives : the mesh, the polynomial, and the tolerance contribute about 10, 11.3, and 19.9 bits, and the constant 12 another 3.6. At , it gives .
Cost. With 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 , that is, as . For the square at and :
One application of : 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 .
One query to : 88,926 Toffoli gates and 588 rotations on 5,699 qubits. A query applies twice and the controlled material reflection once, and adds three single ancillas, for , the flag of § 3.5, and QSVT. Its rotations are, for each , the of the arithmetic, the 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 controlled phases each [23]; and the 2 rotations of .
One application of the inverse therefore costs Toffoli gates, the 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.pyholds the closed-form eigenvalues of , functions of by the FFT, and assembled element by element;isometry.pyholds in closed form, assembled element by element, the unitary of Equation (40), and the gate-level circuit of § 3.8, whose arithmetic is in the subpackagearithmeticof the companion paper.
The test cells and the inverse:
cells.pyholds the three cells of § 5.1, their material oracles, and the operators applied without dense matrices;inversion.pyholds the inverse, the choice of , and the resource counts.
Scripts: in the folder
papers/inversion,makeTables.pyandmakeFigures.pywrite 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 and , compute the extreme eigenvalues of , apply the inverse of § 3.7 at to the source of the cell problem for the macroscopic gradient , and then compute the resources of the inverse at . Each quantity is a single function call in the package.
Listing 1: The inverse on the square at , and its resources at .
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 , and the inverse at meets . 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, is applied without gates. In Listing 2, we check the gate-level circuit itself: we build at and , simulate it gate by gate for all 256 wavenumbers, and compare the vector that prepares with of Equation (28).
Listing 2: The gate-level at and , checked against 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 at every wavenumber, and the prepared vectors agree with to , below the bound 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 , , and . 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 , 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 equals to machine precision, and the energy-norm error of its output is below .
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 , that is, unknowns. We address four questions.
Geometry: is the condition number of equal to for cells of different topology (§ 5.1)?
Mesh: does it stay at under refinement, and does the inverse keep its accuracy at a fixed degree (§ 5.2)?
Gates: does the gate-level circuit encode and its inverse to the accuracy that the encoding error predicts (§ 5.3 and § 5.4)?
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 is formed on the large meshes. The quantities are computed as follows.
Operators: functions of are applied by the FFT, and as a sparse matrix.
Inverse: is applied by the Clenshaw recurrence on the Chebyshev coefficients of , which uses applications of .
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 .
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 , the encoding and the inverse are also compared with dense matrices and a sparse direct solve.
Qiskit circuit: at and , 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 , is a conductor connected across the cell in both directions. The laminate, with layers normal to , is anisotropic. All three cells are dyadic: the phase indicator 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 . We check each of these circuits on every element for to : it reproduces in every case.
Figure 4. The three test cells, drawn at ; 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 at , for and . In all six cases, and to six digits, so . 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 , and a field whose gradient vanishes in every matrix element gives the eigenvalue 1.
| geometry | Toffoli | ||||||
| square | 0.25 | 2 | 10 | 1.000000 | 1.000000 | 1.000000 | 1.000000 |
| 1.000000 | 1.000000 | 1.000000 | 1.000000 | ||||
| cross | 0.234 | 9 | 10 | 1.000000 | 1.000000 | 1.000000 | 1.000000 |
| 1.000000 | 1.000000 | 1.000000 | 1.000000 | ||||
| laminate | 0.5 | 0 | 10 | 1.000000 | 1.000000 | 1.000000 | 1.000000 |
| 1.000000 | 1.000000 | 1.000000 | 1.000000 |
Table 3. Extreme eigenvalues of for the three cells at . “ Toffoli” is the number of Toffoli gates of the controlled material reflection; means that the bound of Equation (35) is attained.
Mesh Independence
In Figure 5, the mesh is refined from to at to test three predictions of § 2 and § 3, one per panel.
Figure 5. Mesh refinement at . (a) Condition number seen by QSVT for the two-phase operator () of the three cells, and , which is the same for all three cells. (b) Relative energy-norm error of the inverse at the fixed degree (), for the cell-problem source of each cell, with the exact . (c) Toffoli gates of one application of , with 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 with . It grows by a factor of 4.00 per doubling of on the finest meshes and reaches for the square at , the growth of § 2.6. The condition number of equals to ten digits for every and every cell.
(b) Accuracy of the inverse. Because does not change with , we fix the degree at , the degree of § 3.7 for , and apply the inverse to the cell-problem source of § 5.4. The relative energy-norm error stays between and for all three cells and all meshes, below as Equation (37) requires. The error does not grow with , so the degree does not need to grow either.
(c) Cost of one application of . What grows with is the cost of . By Equation (42), grows by one bit per doubling of , from at to at , and the Toffoli count grows quadratically in (§ 3.8), from 33,680 to 44,462. The cost per query therefore grows with only through , which grows as , while the number of queries stays fixed.
Gate-Level Encoding
The block of was derived in § 3.6 with the exact . We now form that block from the simulated gate-level circuit,
including the routing of into the unused local states, and compare it with for the square at . Table 4 reports the spectral-norm difference for and and and . In every case the difference lies below , as two applications of allow, and it falls with . The smallest and largest eigenvalues of the block equal and to 13 digits, and the constant field appears as the eigenvalue , inside that interval.
| difference | |||
| 8 | 24 | ||
| 8 | 32 | ||
| 16 | 24 | ||
| 16 | 32 |
Table 4. Spectral-norm difference between the block of on the input subspace, computed from the gate-level circuit with fractional bits, and , for the square at . The difference is the encoding error of the circuit, not a discretization error; it falls with and lies below , twice the encoding error of at the same and .
The Inverse on Four Heat Sources
We apply the inverse of § 3.7, with and , to four heat sources on the square cell, each with its mean removed.
Smooth: the nodal source .
Random: a source with independent standard normal entries.
Cell problem: the source , with the gradient at every quadrature point. This is the source of the cell problem of homogenization for the macroscopic gradient ; it is concentrated at the interface between the phases and orthogonal to the constant fields, since maps them to zero.
Worst case: , with an eigenvector of at . 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 in every case and does not grow with , and for the worst-case source it equals the residual of . We then replace by the block of the gate-level circuit at and . The errors change by at most for and for , within the encoding term of Equation (37).
| smooth | random | cell | worst | ||
| 8 | 145 | ||||
| 16 | 145 | ||||
| 32 | 145 | ||||
| 64 | 145 |
Table 5. Relative energy-norm error of the inverse with and for four heat sources on the square cell, with the degree . The errors are those of the polynomial applied to the exact ; 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 qubits at . We therefore build as the multiplexor of § 3.8, whose angles are computed classically for all 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 and , so that and , on meshes with and . 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 ; splitting and using Equation (19), the preconditioned right-hand side is
so that Hadamard gates, one application of and one of deliver , flagged on two ancillas. QSVT then applies to with the phases of Dong et al. [38], and the whole circuit uses 13 qubits at and 15 at : position qubits, 4 local qubits, and 5 ancillas.
Before transpiling, each stage is compared with its matrix at every wavenumber and every input: equals to , the block of equals to , the prepared right-hand side is parallel to to , and the output equals , up to the normalization of the right-hand side, to . Against the finite element solution from a sparse direct solve, the energy-norm error of the output is at and at , below , as Equation (37) requires with .
The success probability is at both meshes, the product of the probability of preparing the right-hand side, at and at , and the probability of the inverse, which is limited by the subnormalization of ; the latter factor is the expected cost of QSVT inversion and is removed by rounds of amplitude amplification [39]. The circuit size, in contrast, grows with : the CX count of one application of grows from 138 to 310 when doubles, most of the increase coming from the two uniformly controlled rotations, whose angles make the multiplexer grow as (§ 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 , and its logical cost is given next.
Resources
Table 6 gives the logical cost of one application of the inverse for the square at and . Each of the queries to applies twice and the controlled material reflection once, so the total is times the cost of a query in § 3.8.
| Toffoli/ | Toffoli/query | rotations/query | Toffoli | qubits | ||||
| 77 | 13.2 | 34 | 25,925 | 51,852 | 544 | 3,576 | ||
| 145 | 17.6 | 45 | 44,462 | 88,926 | 588 | 5,699 |
Table 6. Logical resources of one application of the inverse for the square at and : polynomial tolerance , degree (queries to ), subnormalization , fractional bits from Equation (42), Toffoli gates of one application of 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.
: queries and , with 88,926 Toffoli gates and 588 rotations per query, give Toffoli gates on 5,699 logical qubits.
: queries and give 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.
Rotation synthesis: the single-qubit rotations of Table 6 are counted before synthesis into Clifford and T gates.
Phase rotations of QSVT: the rotations about the input subspace each mark a subspace of a few qubits, at a number of Toffoli gates that does not depend on or .
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 for every . The mesh enters the cost only through the quantum Fourier transforms and the wavenumber-controlled stage, both polylogarithmic in , 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 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 , the degree of the inverse grows linearly in : at , Equation (36) gives at and at , although does not grow with . 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 , with , and with the subnormalization (Equation (42)): at and , fractional bits and Toffoli gates for one application of the inverse. Up to 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 only through . 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 ; 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]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]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]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]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]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]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]Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. Physical Review A, 93(3):032324, 2016.DOI
- [8]Burigele Liu, Michael Ortiz, and Fehmi Cirak. Towards quantum computational mechanics. Computer Methods in Applied Mechanics and Engineering, 432:117403, 2024.
- [9]Scott Aaronson. Read the fine print. Nature Physics, 11(4):291–293, 2015.DOI
- [10]John Golden, Daniel O’Malley, and Hari Viswanathan. Quantum preconditioners and hydrological linear systems. arXiv preprint arXiv:2205.06379, 2022.DOI
- [11]Leigh Lapworth and Christoph Sünderhauf. Preconditioned block encodings for quantum linear systems. Quantum Science and Technology, 10(4):045064, 2025.DOI
- [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]Krishnan Suresh. Multilevel state preparation by CORDIC arithmetic for the periodic Poisson isometry. Companion paper, in preparation, 2026.
- [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]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]Erik Andreassen and Casper Schousboe Andreasen. How to determine composite material properties using numerical homogenization. Computational Materials Science, 83:488–495, 2014.DOI
- [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]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]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]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]George J Fix and Gilbert Strang. An analysis of the finite element method, volume 2. Wellesley-Cambridge Press, 2008.
- [22]Matthias Leuschner and Felix Fritzen. Fourier-accelerated nodal solvers (FANS) for homogenization problems. Computational Mechanics, 62(3):359–392, 2018.DOI
- [23]Krishnan Suresh. Applied Quantum Computing for Engineers: Linear Solvers and Optimization. Independently published, first edition, 2026. ISBN-13: 979-8244366846.
- [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]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]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]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]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]Matthias Deiml and Daniel Peterseim. Quantum realization of the finite element method. Mathematics of Computation, 95:2637–2668, 2026. arXiv:2403.19512.DOI
- [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]Adi Ben-Israel and Thomas NE Greville. Generalized inverses: theory and applications. Springer, 2003.
- [32]Philip J Davis. Circulant matrices, volume 120. Wiley New York, 1979.
- [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]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]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]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]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]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]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



