WorksComputer Science
Quantum Block Encodings for Periodic Two-Phase Finite Element Operators: 2D Poisson and 2D Elasticity
Abstract
Quantum algorithms require embedding linear operators into unitaries using block encodings. The costs associated with these block encodings determine whether a quantum speedup is achieved. Efficient shift decomposition encodings have been proposed for 2D homogeneous scalar operators. Here, we present exact block encodings for 2D homogeneous elasticity, 2D two-phase bilinear Poisson, and 2D two-phase elasticity periodic finite-element operators. For 2D homogeneous elasticity, the resulting linear combination of unitaries (LCU) has terms for every Poisson ratio and every mesh resolution, and the subnormalization is the closed form , exceeding by the resolution-independent factor . To address two-phase periodic microstructures, we introduce two oracles with distinct roles: a node-to-element oracle, built from cyclic shifts, that carries a nodal index to each of the four incident element indices, and a microstructure-specific material oracle that marks phase membership with a sign. This yields 25 and 57 LCU terms for two-phase Poisson and elasticity, respectively; the latter reduces to 49 at . The term counts are independent of mesh resolution, volume fraction, and phase contrast. The subnormalizations, provided in closed form, are independent of mesh resolution and volume fraction. In the scalar case, the tight bound is achieved whenever a node lies entirely in the stiffer phase. In the elasticity case, that bound is not attained, since the shear coupling contributes entries of both signs to a row. An open-source implementation is available at https://github.com/UW-ERSL/PyBlockEncode
Introduction
Quantum algorithms for linear systems, differential equations, and matrix functions promise substantial speedups for large-scale computational problems [1, 2, 3, 4, 5]. Modern algorithmic formulations require the underlying operator to be embedded in a larger unitary as a block encoding: an -qubit unitary whose top-left block is for some subnormalization . Constructing that encoding is the first step of every modern pipeline. The block encoding cost determines whether a quantum speedup is achieved. A general-purpose encoder working from the entries of alone, such as FABLE [6], costs gates at for a matrix, and the exponential overhead is unavoidable without structure [7].
Operators in computational mechanics over regular meshes typically have structure. A finite element discretization on a regular grid is sparse, assembled from one small element matrix, and expressible in terms of cyclic shifts. A substantial literature, reviewed in § 2, uses this structure for scalar 1D and 2D homogeneous operators.
In this work, we construct exact shift-decomposition-based block encodings of three operators: 2D homogeneous elasticity, 2D two-phase bilinear Poisson, and 2D two-phase elasticity.
§ 2 provides a brief technical background and reviews the literature. § 3 recalls the shift-decomposition encoding of the periodic homogeneous Poisson cell, and § 4 derives the same for elasticity. § 5 introduces the two-phase microstructure, the node-to-element mapping and the material oracle. § 6 and § 7 generalize the two encodings to two phases. § 8 describes the circuit and summarizes the resources, and § 9 documents the open-source implementation and the reproduction of every table reported here. Appendix § 15 draws the four circuits at .
ORCID(s): 0000-0002-9688-9697 (K. Suresh)
Background
Block Encoding and LCU
A unitary acting on qubits is an -block encoding [4] of an -qubit operator if
We place the system register on the least-significant qubits, so the encoded block is the contiguous top-left corner . Setting gives an exact encoding.
The canonical construction assembles as a linear combination of unitaries (LCU) [8, 5]. Given
with unitaries and real coefficients , the subnormalization is . For symmetric , and whenever every is a generalized permutation, carrying one nonzero entry per row,
Every unitary used in this paper is of that form: each has at most one entry in a given row, so no cancellation between terms can push below the largest absolute row sum, and is a floor on what the decomposition can attain.
The subnormalization controls both the post-selection success probability at , and the query complexity of downstream routines. The circuit then has three stages: PREP loads into the ancilla register, SELECT applies controlled on the ancilla state , and UNPREP uncomputes the ancilla, with the sign of absorbed into or carried by a second preparation. On the -ancilla subspace,
Consequently, three quantities determine the cost of block-encoding:
The subnormalization , which affects the query complexity linearly and the post-selection probability quadratically.
The Toffoli count of SELECT, which, for a generic implementation, is [9].
The arbitrary-angle rotation count of PREP, which dominates the fault-tolerant cost because each rotation costs gates at precision , while everything else is Clifford and Toffoli.
The PREP register must address all terms, so its width satisfies . A dense PREP on qubits uses rotations, whether or not every index carries amplitude.
Pauli Encodings
The common generic approach is LCU expansion in the Pauli basis [10]. The Pauli term count, verified numerically for to , is
for qubits per spatial direction. The two 2-phase counts hold at every contrast, but they are specific to the microstructure of Figure 1; other microstructures may give different counts. The subnormalization grows quadratically in for both homogeneous 2D cases. Considerable effort has gone into computing Pauli coefficients faster, through tensorized recursion [11], tree traversal [12], symmetry-restricted enumeration [13] and the fast Walsh–Hadamard transform [14].
Figure 1. The two-phase cell at : a square inclusion of side , centered, at volume fraction . The inclusion carries and is left unshaded; the matrix carries .
Beyond standard Pauli decompositions, several alternative matrix encoding strategies have been proposed. Lu et al. [15] benchmarked multiple encoding approaches: parallel Walsh–Hadamard expansions, standard LCU methods, and an SVD-based singular value dilation that reduces any real square matrix to an exact two-term LCU. The SVD dilation attains , but its two factors are dense rather than generalized permutations. Other general block-encoding frameworks, such as state preparation pairs or oracle-based linear combinations of unitaries [4], similarly shift the computational complexity to deep state-preparation circuits or unmapped oracle operations unless specific structural assumptions are made. Xu and Hu [16] remove the operator encoding entirely; instead they vectorize and evaluate the variational cost functions as inner products through a swap test; the expense moves to state preparation, which they state as an open problem.
Kuklinski et al. [7] make the premise of this paper precise: efficient block encodings require structure.
Structured Block Encoding
On a regular grid, a finite difference (FD) or finite element (FE) discretization of the Poisson or elasticity operator produces a matrix that is sparse and translation invariant: every node carries the same stencil, built from a small set of repeated entries. Structured block encoding is the collection of techniques that use this structure so that the gate and ancilla counts scale as rather than , and the subnormalization stays constant, for an -qubit operator.
Several families of structured block encoding have been proposed. These include shift decomposition, where we write the operator in closed form as a short sum of shift operators and use that sum in an LCU [8, 17, 18, 19, 20]. A closely related recursion expands the Dirichlet stencil in terms built from the ladder operators [21]; Gnanasekaran and Surana [22] generalize this to a basis of such operators and recover the decomposition by unitary completion, at terms for the one-dimensional Poisson operator and a SELECT cost that grows with the term count. The sparse-access approach places the nonzero values of a structured operator by addressing them directly, through a pair of oracles [23, 24, 25]. Finally, the element-decomposition method, which is specific to FE, assembles the global stiffness matrix from small element matrices [26, 27].
This paper focuses on the shift decomposition approach and addresses two limitations in the literature. The first is the scalar restriction. Shift decomposition has been developed for scalar operators, and the two constructions that address linear elasticity take a different approach: Hölscher et al. [27] take an LCU over elements, so the term count equals the element count and the subnormalization grows with the mesh, and Danz et al. [25] build the stiffness and mass matrices of an elastic structure from general fixed-point arithmetic oracles. Neither yields a decomposition whose length is independent of resolution.
The second limitation is the homogeneity restriction. Block encodings of variable-coefficient operators do exist: Deiml and Peterseim [28] admit an arbitrary spatially varying coefficient but leave its oracle abstract and the subnormalization grows with the ellipticity contrast; Pechan et al. [29] construct a heterogeneous three-dimensional Poisson encoding from the sparse local structure of the discretized operator, at a subnormalization bounded by the largest conductivity in the cell; Yano and Sato [30] represent a piecewise coefficient profile by a controlled Fourier series, which is approximate at a material interface. What none of them provides is a linear combination of fixed length in closed form, over a material oracle realized exactly.
Table 1 compares the scope of the proposed work against the existing literature.
1D Homogeneous Periodic Poisson
Shift decomposition is easiest to see on a 1D operator. For the 1D Poisson problem on periodic nodes, discretized using linear finite elements of unit element length, leads to the stiffness matrix
where the corner entries carry the periodic wrap. This can be expressed compactly as
Prior block encodings and the present construction. S scalar, V vector; FD finite difference, FE finite element; Dim spatial dimension, any dimension; U uniform, H heterogeneous, 2 two-phase; Y/N whether the work names a public repository. means constant in ; the term count of a shift construction grows linearly with for finite differences and as for tensor-product finite elements. {sup}† also treats non-periodic boundary conditions; {sup}‡ holds for constant coefficients; {sup}§ the framework is stated for any $d$, but the stiffness analysis is carried out in one dimension; {sup}⋆ the two SVD factors are dense and unstructured, and no efficient circuit for them is given. marks a quantity that does not apply, a dash one the cited work does not report. Every is quoted at unit element length.
| work | Op | FE/FD | Dim | Mat | Approach | code | ||
| Kharazi [17] [17] | S | FD | U | shift{sup}†` | Y | |||
| Sturm [18] [18] | S | FD | U | shift | N | |||
| Hogancamp [20] [20] | S | FD | U | shift{sup}†` | N | |||
| Mahmud [31] [31] | S | FD | U | shift + optimality | N | |||
| Gnanasekaran [22] [22] | S | FD | U | ladder + completion | — | N | ||
| Alkadri [19] [19] | S | FE | U, H | element LCU | N | |||
| Deiml (2025) [28] | S | FE | H | FE + BPX, oracle | n/a | contrast | Y | |
| Pechan [29] [29] | S | FD | 3 | H | sparse access | n/a | Y | |
| Yano [30] [30] | S | FD | H | diagonal, Fourier | n/a | assumed | N | |
| Danz [25] [25] | V | FE | U, H | arithmetic oracle | n/a | — | N | |
| Arora [26] [26] | S | FE | 1 | H | VQLS; element | n/a | N | |
| Lu [15] [15] | S | any | 2 | n/a | coh. VQLS; SVD | N | ||
| Hölscher [27] [27] | V | FE | 2 | 2 | element + Grover | Y | ||
| This work | S, V | FE | 2 | 2 | shift + reflections | Y |
Table 1. Prior block encodings and the present construction.
where carries on the sub-diagonal, on the diagonal and on the super-diagonal, each off-diagonal band wrapping into the opposite corner.
Let be the cyclic shift
so that . It is a permutation matrix, hence unitary, and its adjoint is the backward shift. Thus Equation (6) can be expressed as
This is an exact LCU, and hence a block encoding: three unitaries, coefficients known in closed form, and a subnormalization that does not grow with . The cost is one increment modulo of depth [32, 23]; the controlled ripple-carry increment used here costs Toffoli, CNOT and clean ancillas that are returned to and reused by every shift in the circuit [33, 34].
Table 2 compares the cost of encoding using shift decomposition against an exact Pauli expansion of the same operator at . The gap widens in 2D and for heterogeneous cells. For the 1D cell, the chain collapses to equality, so the shift decomposition is optimal.
| quantity | Pauli | shift |
| terms | 3,072 | 3 |
| PREP qubits | 12 | 2 |
| PREP slots | 4,096 | 4 |
| SELECT Toffoli | 3,072 | 48 |
| 14.0 | 4.000 | |
| 0.082 | 1.00 |
Table 2. Periodic 1D finite element Poisson cell at qubits, 4,096 degrees of freedom. The shift column is measured; the Pauli column is exact in closed form, , and , since at every even . This is the one cell in which the comparison is tabulated; the four 2D cells follow the same pattern more sharply, at the term counts of Equation (5).
2D Homogeneous Periodic Poisson
For a 2D periodic Poisson problem consisting of a grid of bilinear elements, the finite element operator separates into 1D factors [35, 36, 19],
where is the consistent mass matrix. Throughout this paper, the left factor of a Kronecker product acts on the register, the next on the register; thus lists registers from least to most significant, the reverse of the matrix Kronecker product. Both factors are three-band circulants, so both admit the shift decomposition of § 3.1,
and Equation (10) expands over the nine unitaries . This approach to the periodic scalar cell is due to Sturm and Schillo [18] and, for tensor-product finite elements, to Qu-FEM [19].
Merging the coefficients that land on the same pair of shifts,
nine terms with
As a nodal stencil, Equation (12) is the bilinear nine-point Laplacian, and exactly.
The shift decomposition is independent of mesh resolution, against terms at for a generic Pauli expansion of the same operator.
2D Homogeneous Elasticity
In this section, we extend the above results to 2D homogeneous periodic elasticity. Ordering rows and columns by displacement component gives the familiar block
The blocks separate [35, 37] as
where and is the antisymmetric gradient coupling, whose shift decomposition is
The coupling is the new cross-derivative term. Since is antisymmetric, is symmetric, so on a periodic homogeneous grid.
Elasticity carries degrees of freedom per node, so is and the spatial qubits no longer address it. One further qubit is required, the dof qubit , with selecting the displacement and the displacement. It is now the most significant qubit of the system register, following the and registers.
Equation (14) is the sum of three matrices, a block-diagonal average, a block-diagonal difference, and a purely off-diagonal part. With each is a single Kronecker product,
each term a single Kronecker product of an spatial block with , and respectively, so that
This splits into three Pauli components, each an spatial block tensored with one single-qubit matrix. We can now substitute the shift decompositions of , and into (20) to arrive at the following proposition.
Proposition 1. For the periodic plane-stress elasticity operator with Young’s modulus and Poisson ratio , the global stiffness matrix admits the exact LCU
with , , and the set of triples carrying a nonzero coefficient, of size for every and every with . The subnormalization is
constant in .
Proof. Substitute the shift decompositions of , and into the three Pauli components of Equation (20) and merge coefficients landing on the same shift pair. The and components expand over the nine pairs , the component over the four pairs carrying a shift in both directions, since has no identity term. Of the nine entries only the four axis pairs survive the antisymmetric combination , giving $9+4+4=17$. The nine pairs are distinct as operators for , where , so no further merging occurs, and no coefficient vanishes: the prefactor carries and the and prefactors carry , vanishing only at and respectively, neither of which the plane-stress operator admits. For , the merged coefficients of the spatial factors sum in magnitude to , and for the , and components respectively, and weighting them by the component prefactors , and $C(1+\nu)/2 gives Equation (22). □
Table 3 groups the 17 terms. There are at most four distinct magnitudes. The eight non-identity shift pairs are the eight stencil neighbors: four axis pairs such as and , and four diagonal pairs such as and . The spectral norm is for every and every , so the ratio is a closed form,
which is 1.3875 at .
The term count and the closed form hold at every , against terms for an exact Pauli expansion of the same operator ((5)).
| stencil offsets | # | coefficient | ||
| , the centre | 1 | +1.9780 | ||
| all eight neighbours | 8 | −0.2473 | ||
| , | 2 | +0.3571 | ||
| , | 2 | −0.3571 | ||
| , | 2 | +0.1786 | ||
| , | 2 | −0.1786 | ||
| 17 | 6.0989 |
Table 3. The 17 LCU terms of the periodic plane-stress elasticity operator at , grouped by coefficient. , , and the pair names the stencil offset. Summing the distinct magnitudes with their multiplicities gives of Equation (22).
Two-Phase Microstructure
We now turn our attention to finite element meshes that carry two materials. We refer to the spatial distribution of the two phases as the microstructure. The periodic two-phase cell is the natural target, because it is the unit cell of computational homogenization [38, 39, 40, 41].
With a second phase, the operator is no longer translation invariant. This leads to two challenges. First, the material is defined element by element, whereas the shift operators act on nodal registers, so the encoding must relate the two indices; § 5.1 constructs this node-to-element mapping from cyclic shifts. Second, the element moduli must enter the linear combination as unitaries. A diagonal modulus matrix is not unitary, and expanding it in a generic basis would tie to the microstructure; § 5.2 writes it instead as a combination of the identity and a material reflection, with coefficients determined by and . § 6 and § 7 then assemble the two-phase operators from these pieces.
Figure 1 shows the primary example used throughout: a square inclusion of side at the center of the cell. Each phase carries its own material property. For the Poisson problem, and are the conductivities of the two phases; for elasticity, they are the two Young’s moduli, with a common Poisson ratio . Each element carries a modulus implied from these two phases,
where is the microstructure-specific binary field discussed in § 5.2.
The assumed periodicity of the microstructure links opposite boundaries of the domain. Under this assumption, an mesh carries elements and distinct nodes. We index both nodes and elements using qubits, where . We write , with , when the register is read as an element index, and , with , when read as a nodal index.
Node-to-Element Mapping
The material field is defined element by element, whereas the shift operators of § 3 act on nodal registers. We therefore define a mapping from one to the other.
Each grid node is touched by four adjacent elements, located at the relative spatial offsets
Figure 2 illustrates this for the node .
Figure 2. The four elements incident on node , on the patch surrounding it. Each element carries the index of its own lower-left node, marked by a square, so the element at offset has index and the four indices are , , and as runs over Equation (25).
The node-to-element mapping carries the nodal register to the element index , componentwise:
where is the 1D cyclic forward shift of Equation (8) and its backward counterpart. Thus, for example,
Since , the mapping factorizes over the two spatial registers, and the four offsets of Equation (25) are generated by one conditional shift per register. The offsets are taken modulo , so a node on the last row or column reaches elements in the first, and is the same four offsets at every node with no exception at the mesh ends. Periodicity is also what makes a permutation, and hence unitary. acts purely as a spatial coordinate translation, without referencing the material property or the microstructure geometry.
The Material Oracle and Reflection
The microstructure itself is defined as a binary field on the elements,
where
is the volume fraction of phase 1. We write for the phase contrast ratio.
Two-phase encoding requires a quantum circuit that evaluates the membership field . For the square inclusion in Figure 1 the membership test factorizes into independent conditions on and . An element lies inside the inclusion when and . The two leading bits of , with the most significant, place it in one of four quarters, and lies in range precisely when . Applying the identical condition to yields the Boolean predicate
for every . Note that Equation (30) applies only to the microstructure of Figure 1; other microstructures require their own predicates.
Given the Boolean indicator , the material phase enters the block encoding through the material reflection oracle :
which acts on the element state by applying a phase flip conditional on phase membership,
The operator is diagonal, Hermitian, and unitary (). Because it marks states with a phase rather than a flag register, it requires no additional ancilla qubits and enters linear combinations of unitaries directly. Under Equation (30), acts on exactly four qubits at every , the two leading bits of each coordinate: two CNOT gates compute the two parities in place, one controlled applies the phase, and two CNOT gates restore the register. No ancilla is needed, because the parities are computed in place on the coordinate registers rather than onto shift-control qubits. For this microstructure the cost is four CNOT and one controlled at every .
Combining the mapping with the base oracle yields the four element-wise material reflection operators as seen from node . Reading right to left, the nodal index is carried to the element index, the oracle is queried there, and the index is carried back:
Writing for the modulus of the element at offset as seen from node , the two-phase field of Equation (24) gives
Two-Phase Poisson
Section 3.2 decomposed the homogeneous cell into 1D factors. A variable modulus destroys that separation, so we work instead at the level of the element matrix, where the modulus is a scalar multiplier and the shift structure survives. At unit conductivity the bilinear element matrix is
its rows and columns running counterclockwise from the lower-left corner. We index them by the corners, writing with .
For node , Figure 2 shows the four incident elements and their offsets . Each of those elements couples that node to all four of its own nodes, so a second index is needed to enumerate them. The element at offset has lower-left node , so node is its corner and its four nodes are as runs over . That node couples to node , with , through the entry .
An entry in the row at and the column at is the operator , so the element at contributes the four-term operator
with running with the sum. Scaling each element by its modulus gives the assembled operator
with defined in Equation (34).
The four merge into the nine-term homogeneous operator of Equation (12),
and each carries the same four coefficients up to order, hence the same coefficient sum , so the four together sum to , which is of Equation (13).
Substituting Equation (34) into Equation (37) splits the operator into a mean part, which merges by Equation (38), and a contrast part, which does not:
The microstructure appears only inside the reflections.
Proposition 2. Equation (39) is an exact LCU of the two-phase periodic Poisson operator in which every unitary is a cyclic shift pair, optionally preceded by one material reflection. For every , every and every with it has
At the second family vanishes and collapses to the 9 of Equation (12).
Proof. The first family of Equation (39) is , nine terms. The second is four reflections carrying four shifts each, and the sixteen combinations occupy sixteen index slots distinct from each other and from the first family, so nothing merges: . For , the first family contributes and the second , where denotes the sum of the coefficient magnitudes of . Each one is , so the second sum is , as is , giving , which is . The factor gives the collapse.
Material contrast introduces no extra subnormalization penalty beyond scaling with the stiffer phase’s modulus. Switching the soft and stiff phases gives the same subnormalization.
This subnormalization reaches the smallest value a shift-based LCU can attain, , whenever the mesh contains at least one node completely surrounded by the stiffer material. Because the matrix infinity norm is the maximum absolute row sum across all nodes, a single fully stiffened node raises the matrix norm to its upper limit of , which equals .
If no such node exists, as in a fine checkerboard pattern where every node touches a mix of soft and stiff elements, the maximum row sum is smaller than , making the bound less tight. For example, an checkerboard with a material contrast yields against . The encoding remains exact in all cases, but reflects a worst-case material bound.
Neither nor the circuit varies with the contrast; only the PREP angles and do. An exact Pauli expansion of the same operator leads to terms at every contrast for the microstructure of Figure 1 (Equation (5)).
Two-Phase Elasticity
For two-phase elasticity, the construction of § 6 applies unchanged once becomes a block. Two things differ, and both belong to elasticity rather than to the method: a fourth dof component, , appears, and the four element contributions at a node no longer share a sign.
The plane-stress element matrix is , two degrees of freedom per node. Indexing rows and columns by corners as before, is now the block coupling the two displacement components at the corner- node to those at the corner- node. Each block resolves over the real orthogonal basis of the dof register, the first three as in § 4 and the fourth , which is real and orthogonal and carries the antisymmetric part of each block. Writing for the component along , the element at offset contributes
with and as in Equation (36). The assembly and the split are then Equations (37) and (39) verbatim, with acting on the spatial registers alone:
The two properties that carried § 6 now read differently. The merge still holds, , the 17 terms of Proposition 1. But each now carries ten terms rather than four, distributed over its four offsets: the offset at the node itself and the diagonal offset carry , while the two axis offsets carry . The reflection family therefore holds 40 terms.
The component is absent from the merged family and present in the reflection family, and the reason is structural. Merging restores the symmetry on which the three-component rewriting of Equation (20) depends; with a variable modulus each element is weighted separately, the shear block loses that symmetry, and carries the antisymmetric remainder. Its total weight is
so the eight terms vanish at and nowhere else.
Proposition 3. (42) is an exact LCU of the two-phase periodic plane-stress operator in which every unitary is a cyclic shift pair tensored with a single-qubit , optionally preceded by one material reflection. For every , every , every and every with ,
and the subnormalization is
with of Equation (22) at and
At the second family vanishes and collapses to 17.
Proof. The counting is that of Proposition 2 with ten terms per element in place of four, and the eight terms carry total weight by Equation (43), vanishing at and nowhere else, which is the drop to 49. For the subnormalization, summing magnitudes in Equation (42) gives , and writing collects the two into Equation (45) with . Evaluating that sum on the plane-stress element gives Equation (46), whose absolute-value term is half the weight of Equation (43).
Written out, Equation (45) reads
As in the scalar cell, the reflections are present at every contrast, so and the circuit are fixed and only the moduli move, against an exact Pauli expansion of 159,338,497 terms at for the microstructure of Figure 1 (§ 2.2).
The Block-Encoding Circuit
Registers
The system register carries qubits ( for Poisson and for elasticity), ordered as , , then the dof qubit. The ancilla carries one shift-control qubit , the clean carry ancillas of the incrementer and finally, the PREP register of qubits. Table 4 collects the resulting cost in closed form.
| cell | system | carry | PREP | total | Toffoli gates | |
| 1D Poisson | 3 | 2 | ||||
| 2D Poisson | 9 | 4 | ||||
| 2D Poisson | 25 | 7 | ||||
| 2D elasticity | 17 | 6 | ||||
| 2D elasticity | 57 | 9 |
Table 4. Cost of the five encodings as a function of , exact at every and verified against measurement at every from 2 to 12. A superscript marks a two-phase cell. is the number of LCU terms, the four middle columns are qubit counts, and the last is a gate count. Every cell also carries one shift control qubit, included in the total; it and the carry ancillas are clean and shared by every shift in the circuit, so both are counted once. can exceed because the index is factored; see § 8.3. The Toffoli count is taken before transpilation; for the transpiled two-qubit count see Figure 4.
Only two entries depend on the mesh: the system register, at qubits, and the carry ancillas, which are returned to and reused by every shift. Everything the decomposition controls is constant in : the term count, the PREP width, and the coefficients themselves. The Toffoli count is affine in at a slope of 8 per shifted register, which is the four controlled shifts of a homogeneous cell and the eight of a two-phase cell at Toffoli each.
The Cyclic Shift
The shift is the controlled ripple-carry cyclic increment of § 3.1, drawn in Figure 3: Toffoli, CNOT and clean ancillas, transpiling to two-qubit gates.
Figure 3. The controlled cyclic increment at , the only primitive whose cost grows with the mesh.
PREP
Two different preparations are used,
so that
has top-left block and no signs appear inside SELECT.
A standard dense PREP uses qubits. SELECT must then apply each controlled on all qubits, which requires controlled blocks and Toffoli gates [9]. Every unitary in Equations (21), (39) and (42) is, however, a tensor product with one factor per register: a shift on , a shift on , a Pauli on the dof register, and at most one reflection . Each factor is drawn from a small fixed set, three shifts per spatial register and four Pauli operators, so the terms are the combinations of those sets while the operations the circuit has to realize are their union. We therefore use a factored encoding of the index [23], in which SELECT applies one multiplexer per register and the choice made on one register is independent of the choice made on the others; for a Pauli LCU, factored encoding over qubits is standard. Consequently, SELECT cost is independent of ; the Poisson operators at (FD) and (FE) compile to identical SELECT circuits. The small price to pay is a wider PREP register. The index is the concatenation of one field per factor: two bits for each shift exponent, two bits for , and, for a two-phase operator, three one-bit fields for the reflection: a flag that applies , and bits and that select the offset in Equation (33). Unused codes receive zero amplitude. The register grows from to for the four cells (Table 4).
SELECT
SELECT applies one controlled operation for each value of each PREP field. The stages, in circuit order, are (see Appendix § 15):
Spatial: on each of and , a controlled increment and a controlled decrement , four controlled shifts in all.
Dof: a controlled and , and in the two-phase elasticity cell a controlled , implemented as . This stage is absent in the scalar cells.
Reflection: in the two-phase cells, decrements on and controlled on and , controlled on , and the matching increments. This is of Equation (33), and adds four controlled shifts and one oracle query.
SELECT therefore contains four controlled shifts in a homogeneous cell and eight in a two-phase cell, at most three controlled single-qubit gates, and at most one oracle query, for every . Each controlled shift costs Toffoli and each two-bit stage adds two, which gives the Toffoli counts of Table 4. Since SELECT does not depend on , each elasticity circuit exceeds its scalar counterpart by a constant number of gates.
Finally, every field is at most two bits wide, so each control line is computed by one Toffoli, and no gate in the four circuits has more than two controls. This matters for the following reason.
In Qiskit 2.4.2 [42], the transpiler synthesizes a multi-controlled with four or more controls using idle circuit qubits as clean ancillas, since a Qiskit circuit assumes every qubit starts in . A block encoding must act correctly on an arbitrary system state, so the transpiled circuit applies a different operator. The circuits here avoid this: the factored index of § 8.3 limits every gate to two controls, and we synthesize every multi-controlled gate explicitly. Appendix § 15 draws all four encodings as built.
Circuit Cost
Section 2.1 noted that the arbitrary-angle rotations of PREP dominate the fault-tolerant cost, each costing gates while everything else is Clifford and Toffoli. Table 5 splits the two-qubit count accordingly: PREP is constant in and SELECT grows.
| cell | slots | rot. | PREP CX | share | ||
| 2D scalar, homog. | 4 | 16 | 9 | 29 | 22 | 4% |
| 2D scalar, 2-phase | 7 | 128 | 25 | 253 | 240 | 18% |
| 2D elast., homog. | 6 | 64 | 17 | 125 | 114 | 16% |
| 2D elast., 2-phase | 9 | 512 | 57 | 1021 | 1004 | 46% |
Table 5. Cost of the two preparations at , against the whole circuit. Slots is , the addressable indices; of them carry amplitude and the rest are prepared at zero.
Figure 4 gives the transpiled two-qubit count from to 12; the slopes are 48 gates per qubit of resolution in the homogeneous cells and 96 in the two-phase cells. The homogeneous elasticity circuit costs a constant more than the homogeneous scalar one. The intercepts are 25 and 143 in the homogeneous cells and 209 and 1012 in the two-phase cells.
Figure 4. Two-qubit gate count against for the four 2D cells, measured rather than fitted, for the circuit transpiled to at optimization level 2 (Qiskit 2.4.2).
Tightness
The ratio factors as
Table 6 evaluates both factors. Both scalar cells have an LCU slack of 1 here: the four element contributions at a node share a sign, so whenever some node lies entirely in the stiffer phase, as shown in § 6; for a microstructure with no such node, the checkerboard of that section for instance, the slack exceeds 1. The elasticity cells have a slack above 1 at every microstructure because contributions of opposite sign cancel (§ 7). For homogeneous elasticity, at every ; in the two-phase cells the norm gap, and with it the product, decreases as increases.
| cell | LCU slack | norm gap | ||
| 2D scalar, homog. | 1.0000 | 1.3333 | 1.3333 | 0.563 |
| 2D scalar, 2-phase | 1.0000 | 1.3485 | 1.3485 | 0.550 |
| 2D elast., homog. | 1.1935 | 1.1625 | 1.3875 | 0.519 |
| 2D elast., 2-phase | 1.2473 | 1.1778 | 1.4691 | 0.463 |
Table 6. The two factors of Equation (50) at , , . The LCU slack is independent of in all four cells; the norm gap is independent of only in the homogeneous cells. is the post-selection probability on the maximizing singular vector.
Implementation
This work is implemented in PyBlockEncode, an open-source Python library built on Qiskit 2.4.2 [42] and available at https://github.com/UW-ERSL/PyBlockEncode; the importable module is pyblockencode. The supported operators are
POISSON1D()POISSON2D('fd')POISSON2D('fe')ELASTICITY2D(nu, E)POISSON2D_2PHASE(vf, E1, E2)ELASTICITY2D_2PHASE(nu, vf, E1, E2)
The size is given either as , the grid points per direction, or as qubits per direction; the encoded operator carries , or rows according to the cell. Listing 1 encodes the homogeneous elasticity cell at .
Listing 1: The homogeneous elasticity cell at .
from pyblockencode import blockencode, ELASTICITY2D
cell = ELASTICITY2D(nu=0.3)
qc, info = blockencode(cell, N=4096)
print(f"operator = {info.kind}")
print(f"dofs = {info.dofs:,} L = {info.L}")
print(f"alpha = {info.alpha:.4f}")
print(f"qubits = {info.qubits}")
print(f"Toffoli = {info.toffoli} CX = {info.cx}")
----- output ------------------------------
operator = elasticity2d
dofs = 33,554,432 L = 17
alpha = 6.0989
qubits = 43
Toffoli = 100 CX = 719
The two-phase operators place a centered square inclusion of volume fraction vf; every result reported here uses , for which the oracle is Equation (30). Listing 2 encodes the two-phase elasticity cell at .
Listing 2: The two-phase elasticity cell at .
from pyblockencode import blockencode, ELASTICITY2D_2PHASE
cell = ELASTICITY2D_2PHASE(nu=0.3, vf=0.25, E1=3, E2=1)
qc, info = blockencode(cell, N=4096)
print(f"operator = {info.kind}")
print(f"dofs = {info.dofs:,} L = {info.L}")
print(f"alpha = {info.alpha:.4f}")
print(f"qubits = {info.qubits}")
print(f"Toffoli = {info.toffoli} CX = {info.cx}")
----- output ------------------------------
operator = elasticity2d_2phase
dofs = 33,554,432 L = 57
alpha = 19.1209
qubits = 46
Toffoli = 191 CX = 2164
Conclusions
In this paper, we presented exact block encodings for 2D homogeneous elasticity, two-phase 2D Poisson, and two-phase 2D elasticity operators on periodic finite element grids, built on shift decomposition and a material reflection oracle. For homogeneous 2D elasticity at qubits per direction (33.6 million degrees of freedom), the LCU has 17 terms, against 18.9 million for the Pauli expansion.
Two-phase microstructures enter through one material reflection oracle conjugated by the four node-to-element shifts. The resulting LCUs have terms for scalar Poisson and for elasticity ( at ), independent of the grid resolution , the volume fraction , and the contrast ; the subnormalizations are closed forms in the two moduli, independent of and . The formulation is restricted to regular grids, periodic boundary conditions, and isotropic phases.
The periodic cell is the setting of computational homogenization that this paper targets. Non-periodic boundaries and unstructured meshes require additional de-periodization and mapping [17], which are not treated here.
Several extensions follow the same construction: (1) Arbitrary microstructures require only a different , since neither nor depends on , so the open cost is the oracle itself: four CNOT and one controlled for a predicate with a closed form, and a table lookup for one without. (2) A functionally graded phase replaces the binary indicator with a discretized modulus, which the same split encodes as one reflection per bit plane, so grows with the bit depth rather than with the number of distinct moduli. (3) The decomposition applies unchanged to any translation-invariant finite element operator on a regular periodic grid, including the mass, convection-diffusion and Helmholtz operators, for which only the element matrix and hence the coefficients change. (4) Extending the work from 2D to 3D leave the node-to-element map and the reflection unchanged, with eight incident elements in place of four, and the scalar cell follows with new constants and no new argument, while the vector cell requires padding the nodal blocks into a two-qubit dof register, which is where the additional terms and subnormalization arise [29]. (5) A more efficient PREP [43] may be desirable, especially in 3D.
Two directions lie outside the present formulation. Nonlinear elasticity re-encodes, at every Newton step, a tangent operator whose element moduli vary with the current state; whether the oracle can be updated rather than rebuilt at each iteration is open. Finally, the end-to-end cost of a QSVT-based solve [4] remains to be quantified, and the subnormalizations reported here need to be quantified.
Acknowledgments
The author acknowledges the Vilas Associate Grant from the University of Wisconsin Graduate School.
Declarations
The author declares no conflict of interest.
Code availability
The code developed in this work is available at https://github.com/UW-ERSL/PyBlockEncode.
Use of AI Tools
The author used generative AI assistants, specifically, Claude (Anthropic) and Gemini (Google) 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.
The Four Circuits
Figures A.1 to A.4 give the four encodings at , with only the two preparations boxed and every other gate drawn as built. The gaps marked reindex are where the shift-control qubit is cleared, the PREP index is recoded for the next term, and is set again.
Figure A.1. Scalar homogeneous cell at , , , on qubits. The four bracketed stages , , , are the two multiplexers of § 8.4, one per spatial register. Within each, the Toffoli before and after computes and uncomputes the SELECT control from a two-bit field, and the gates around it choose which value of that field the shift controls.
Figure A.2. Scalar two-phase cell at , , at , on qubits. The first half is Figure A.1; the three brackets , , at the right are the conjugation of Equation (33) read right to left, a conditional shift on each spatial register, the oracle controlled on , and the shifts undone.
Figure A.3. Elasticity homogeneous cell at , , at , on qubits.
Figure A.4. Elasticity two-phase cell at , , at and , on qubits. Every stage of the construction appears: the four spatial multiplexers, the dof multiplexer , , , and the reflection stage, whose three brackets , , are the conjugation of Equation (33) read right to left.
CRediT authorship contribution statement
Krishnan Suresh: Conceptualization, Methodology, Software, Validation, Writing – original draft.
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.
- [3]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
- [4]András Gilyén, Yuan Su, Guang Hao Low, and Isaac L Chuang. 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 (STOC), pages 193–204, 2019. arXiv:1806.01838.DOI
- [5]Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical review letters, 114(9):090502, 2015.pubmed.ncbi.nlm.nih.gov/25793789
- [6]Daan Camps and Roel Van Beumeen. FABLE: Fast approximate quantum circuits for block-encodings. 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 104–113, 2022. arXiv:2205.00081.DOI
- [7]Parker Kuklinski, Benjamin Rempfer, Justin Elenewski, and Kevin Obenland. Efficient block-encodings require structure, 2025. arXiv:2509.19667.arxiv.org/abs/2509.19667
- [8]Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information & Computation, 12(11-12):901–924, 2012.
- [9]Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X, 8(4):041015, 2018.DOI
- [10]Krishnan Suresh. Applied Quantum Computing for Engineers: Linear Solvers and Optimization. Independently published, first edition, 2026. ISBN-13: 979-8244366846.
- [11]Lukas Hantzko, Lennart Binkowski, and Sabhyata Gupta. Tensorized Pauli decomposition algorithm. Physica Scripta, 99(8):085128, 2024.
- [12]Océane Koska, Marc Baoubin, and Arnaud Gazda. A tree-approach Pauli decomposition algorithm with application to quantum computing. In ISC High Performance 2024 Research Paper Proceedings (39th International Conference), pages 1–11. Prometeus GmbH, 2024.arxiv.org/abs/2403.11644
- [13]Rocco Monteiro Nunes Pesce and Paul D Stevenson. H2ZIXY: Pauli spin matrix decomposition of real symmetric matrices. arXiv preprint arXiv:2111.00627, 2021.arxiv.org/abs/2111.00627
- [14]Timothy N. Georges, Bjorn K. Berntson, Christoph Sünderhauf, and Aleksei V. Ivanov. Pauli decomposition via the fast Walsh–Hadamard transform. New Journal of Physics, 27(3):033004, 2025.DOI
- [15]Chao Lu, Muralikrishnan Gopalakrishnan Meena, Eduardo Antonio Coello Perez, Kalyana Chakravarthi Gottiparthi, and Seongmin Kim. Memory-, circuit-, and ansatz-efficient vqls for cfd on hybrid quantum-hpc systems. arXiv preprint arXiv:2608.09661, 2026.arxiv.org/abs/2608.09661
- [16]Yongchun Xu and Heng Hu. Decomposition-free variational quantum linear solver: Application in computational mechanics. Computer Methods in Applied Mechanics and Engineering, 447:118396, 2025.DOI
- [17]Tyler Kharazi, Ahmad M Alkadri, Jin-Peng Liu, Kranthi K Mandadapu, and K Birgitta Whaley. Explicit block encodings of boundary value problems for many-body elliptic operators. Quantum, 9:1764, 2025.DOI
- [18]Andreas Sturm and Niclas Schillo. Efficient and explicit block encoding of finite difference discretizations of the Laplacian. ACM Transactions on Quantum Computing, 2025.
- [19]Ahmad M Alkadri, Tyler D Kharazi, K Birgitta Whaley, and Kranthi K Mandadapu. A quantum algorithm for the finite element method. arXiv preprint arXiv:2510.18150, 2025.arxiv.org/abs/2510.18150
- [20]Thomas Hogancamp, Reuben Demirdjian, and Daniel Gunlycke. Linear-combination-of-unitaries decomposition for the Laplace operator. Physical Review A, 114(1):012455, 2026.DOI
- [21]Hai-Ling Liu, Yu-Sen Wu, Lin-Chun Wan, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen. Variational quantum algorithm for the Poisson equation. Physical Review A, 104(2):022418, 2021.DOI
- [22]Abevnya Gnanasekaran and Amit Surana. Efficient quantum access model for sparse structured matrices using linear combination of “things”. Physical Review A, 113(2):022437, 2026.
- [23]Daan Camps, Lin Lin, Roel Van Beumeen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. SIAM Journal on Matrix Analysis and Applications, 45(1):801–827, 2024. arXiv:2203.10236.arxiv.org/abs/2203.10236
- [24]Christoph Sünderhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing. Quantum, 8:1226, 2024. arXiv:2302.10949.DOI
- [25]Sven Danz, Tobias Stollenwerk, and Alessandro Ciani. An implementation of quantum oracles for the finite element method. SIAM Journal on Scientific Computing, 48(3):B386–B419, June 2026.DOI
- [26]Abhishek Arora, Benjamin M Ward, and Caglar Ozkay. An implementation of the finite element method in hybrid classical/quantum computers. Finite Elements in Analysis and Design, 248:104354, 2025.arxiv.org/abs/2411.09038
- [27]Leonhard Hölscher, Oliver Ahrend, Lukas Karch, Carlotta L’Estocq, Marc Marfany Andreu, Tobias Stollenwerk, Frank K Wilhelm, and Julia Kowalski. End-to-end quantum algorithm for topology optimization in structural mechanics. Quantum Science and Technology, 11(2):025029, 2026.arxiv.org/abs/2510.07280
- [28]Matthias Deiml and Daniel Peterseim. Quantum realization of the finite element method. arXiv preprint arXiv:2403.19512, 2024.DOI
- [29]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
- [30]Hiroshi Yano and Yuki Sato. Quantum framework for parameterizing partial differential equations via diagonal block-encoding. arXiv preprint arXiv:2603.01358, 2026.arxiv.org/abs/2603.01358
- [31]Jishnu Mahmud and Rebekah Herrman. Moment-structured block encodings of periodic finite-difference operators. arXiv preprint arXiv:2607.11596, 2026.arxiv.org/abs/2607.11596
- [32]Thomas G. Draper. Addition on a quantum computer. arXiv preprint quant-ph/0008033, 2000.DOI
- [33]Craig Gidney. Halving the cost of quantum addition. Quantum, 2:74, 2018.DOI
- [34]Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/0410184, 2004.DOI
- [35]Michel O. Deville, Paul F Fischer, and Ernest H Mund. High-order methods for incompressible fluid flow, volume 1. Cambridge university press Cambridge, 2002.
- [36]Charles F Van Loan. The ubiquitous Kronecker product. Journal of computational and applied mathematics, 123(1-2):85–100, 2000.DOI
- [37]Olgierd Cecil Zienkiewicz, Robert Leroy Taylor, and Jian Z Zhu. The finite element method: its basis and fundamentals. Elsevier, 2013.
- [38]Felix Givois, Matthias Kabel, and Nicolas Gauger. QFT-based homogenization. arXiv preprint arXiv:2207.12949, 2022.arxiv.org/abs/2207.12949
- [39]Burigede Liu, Michael Ortiz, and Fehmi Cirak. Towards quantum computational mechanics. Computer Methods in Applied Mechanics and Engineering, 432:117403, 2024.
- [40]Yiren Wang, Michael Ortiz, and Fehmi Cirak. QAFE2: Quantum accelerated multiscale finite element analysis. Computer Methods in Applied Mechanics and Engineering, 461:119204, 2026.DOI
- [41]Loïc Balazi, Matthias Deiml, and Daniel Peterseim. Quantum enhanced numerical homogenization. arXiv preprint arXiv:2603.28521, 2026.arxiv.org/abs/2603.28521
- [42]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.arxiv.org/abs/2405.08810
- [43]Krishnan Suresh and Sanjay Suresh. Pyencode: an open-source library for structured quantum state preparation. Quantum Science and Technology, 2026.arxiv.org/abs/2603.28259