Source-linked AI summary
Quantum Block Encodings for Periodic Two-Phase Finite Element Operators: 2D Poisson and 2D Elasticity
Krishnan Suresh
TL;DR
Block-encoding costs matter for quantum algorithms, but prior shift decompositions were limited to scalar operators and existing approaches did not provide fixed-length exact encodings over a realized material oracle. The paper constructs exact shift-decomposition encodings for periodic finite-element operators, including elasticity and two-phase cases; for homogeneous elasticity, its LCU uses 17 terms at 12 qubits per direction, compared with 18.9 million Pauli terms.
Problem
Method
The paper constructs exact shift-decomposition block encodings for periodic finite-element operators, using a material reflection oracle and cyclic shifts for node-to-element mapping.
Source: §1 · p. 1, §5.1 · p. 8, §10 · p. 16Results
At 12 qubits per direction, homogeneous 2D elasticity uses 17 LCU terms, against 18.9 million for the Pauli expansion.
Source: §10 · p. 16Takeaways & Limitations
For homogeneous 2D elasticity, the 17-term LCU count holds across mesh resolutions.
Source: §4 · p. 6The formulation targets periodic cells; non-periodic boundaries and unstructured meshes, which require additional de-periodization and mapping, are not treated.
Source: §10 · p. 17
Abstract
from arXiv · showhide
Quantum algorithms require embedding linear operators into unitaries using block encodings. The costs associated with these block encodings determine whether a quantum speedup is achieved. Efficient \emph{shift decomposition} encodings have been proposed for 2D homogeneous scalar operators. Here, we present exact block encodings for 2D homogeneous elasticity, 2D two-phase bilinear Poisson, and 2D two-phase elasticity periodic finite-element operators. For 2D homogeneous elasticity, the resulting linear combination of unitaries (LCU) has $L = 17$ terms for every Poisson ratio $\nu$ and every mesh resolution, and the subnormalization is the closed form $\alpha = E(33+\nu)/\bigl[6(1-\nu^{2})\bigr]$, exceeding $\|\mathbf{K}\|_{2}$ by the resolution-independent factor $(33+\nu)/24$. To address two-phase periodic microstructures, we introduce two oracles with distinct roles: a node-to-element oracle, built from cyclic shifts, that carries a nodal index to each of the four incident element indices, and a microstructure-specific material oracle that marks phase membership with a sign. This yields 25 and 57 LCU terms for two-phase Poisson and elasticity, respectively; the latter reduces to 49 at $\nu = 1/3$. The term counts are independent of mesh resolution, volume fraction, and phase contrast. The subnormalizations, provided in closed form, are independent of mesh resolution and volume fraction. In the scalar case, the tight bound $\alpha = \|\mathbf{K}\|_\infty$ is achieved whenever a node lies entirely in the stiffer phase. In the elasticity case, that bound is not attained, since the shear coupling contributes entries of both signs to a row. An open-source implementation is available at https://github.com/UW-ERSL/PyBlockEncode
1. Introduction
Block-encoding cost is central to whether quantum algorithms can achieve speedups, while general-purpose encoding can incur exponential overhead without exploiting structure. This work constructs exact shift-decomposition encodings for three periodic finite-element operators.
1. Introduction
- A general-purpose encoder based only on matrix entries has exponential gate cost, so exploiting operator structure is important for efficient block encoding.The cited example FABLE costs O(4^n) gates for a 2^n × 2^n matrix at α = 2^n max_ij |A_ij|.Source: §1 · p. 1
- Finite-element operators on regular grids are sparse, assembled from a small element matrix, and expressible through cyclic shifts.These structural properties distinguish them from unstructured matrices given only by their entries.Source: §1 · p. 1
- The paper constructs exact shift-decomposition block encodings for 2D homogeneous elasticity, two-phase bilinear Poisson, and two-phase elasticity.The introduction situates these constructions in a setting where encoding cost affects whether quantum speedup is achieved.Source: §1 · p. 1
2. Background
The background defines block encodings and LCU costs, then contrasts Pauli expansions with structured alternatives. It emphasizes that exploiting operator structure is necessary for efficient block encodings.
2.1. Block Encoding and LCU
- The unitary's encoded block is its contiguous top-left corner, and setting ε=0 gives an exact encoding.The block-encoding definition is introduced as an (α, a, ε)-block encoding of an n-qubit operator.Source: §2.1 · p. 2
- For the LCU, α is the sum of the absolute coefficients, and the paper's generalized-permutation unitaries impose a floor of ||A||∞.Because each unitary has at most one entry in each row, terms cannot cancel to reduce α below the largest absolute row sum.Source: §2.1 · p. 2
- The subnormalization α affects downstream query complexity linearly and post-selection probability quadratically.The PREP register addresses all L terms and requires at least ceil(log2 L) qubits; generic PREP and SELECT also incur rotation and Toffoli costs.Source: §2.1 · p. 2
2.2. Pauli Encodings
- Pauli-basis LCU is described as the common generic encoding approach, while the paper frames efficient block encodings as requiring structure.The cited discussion also describes alternatives whose costs shift to dense factors, deep state preparation, or unmapped oracle operations.Source: §2.2 · pp. 2–3
3. Structured Block Encoding
Structured block encodings exploit the sparsity and translation invariance of regular-grid operators. This section develops shift decompositions for periodic Poisson operators, including a resolution-independent 2D construction with tight scalar subnormalization.
3. Structured Block Encoding
- Regular-grid Poisson and elasticity operators are sparse and translation invariant, enabling structured encodings with poly(m) gate and ancilla counts and constant subnormalization.Each node carries the same stencil, assembled from repeated entries.Source: §3 · p. 3
- Prior shift decompositions were limited to scalar operators and lacked a fixed-length, exact material-oracle construction for heterogeneous coefficients.Existing elasticity constructions either scale their term count or subnormalization with mesh size, or do not provide a resolution-independent decomposition.Source: §3 · p. 3
- Three unitaries give an exact 1D periodic Poisson LCU with α=4, independent of the number of nodes.The shift circuit uses an increment modulo N, with depth O(m).Source: §3.1 · p. 4
3.2. 2D Homogeneous Periodic Poisson
- The 2D periodic Poisson operator uses nine shift unitaries; its decomposition is resolution-independent, and α equals ||K||∞ for the bilinear nine-point Laplacian.The two 1D factors are three-band circulants, so their tensor-product expansion uses pairs of shifts.Source: §3.2 · p. 5
4. 2D Homogeneous Elasticity
The periodic plane-stress Q4 elasticity operator has an exact shift-based LCU with 17 terms for every admissible Poisson ratio and mesh resolution. Its terms represent the stencil’s spatial shifts and the displacement-component couplings.
4. 2D Homogeneous Elasticity
- 17 LCU terms encode the periodic plane-stress Q4 elasticity operator for every ν in (−1, 1/2) and every mesh with m≥2.The nine identity- and Z-component shift pairs and four X-component pairs remain distinct for these mesh sizes.Source: §4 · p. 6
- The operator’s spectral norm is 4C for every ν and N, and α_2D,el/‖K_2D,el‖₂ equals 1.3875 at ν=0.3.The ratio has a closed form independent of mesh resolution.Source: §4 · p. 6
- For every m≥2, the term count L=17 and closed form α2D,el(ν) hold, against 9; an exact Pauli expansion of the same operator has 84m−1 terms (Equation (5)).Source: §4 · p. 6
- The 17 terms group by coefficient magnitude, and their shift pairs correspond to the eight axis and diagonal stencil neighbors.Summing the distinct coefficient magnitudes with their multiplicities gives α_2D,el(ν).Source: §4 · p. 6, Table 3 · p. 7
5. Two-Phase Microstructure
Two-phase periodic operators require connecting element-wise material data to nodal shift operators and incorporating phase-dependent moduli into the encoding. The paper uses cyclic shifts for the index mapping and a material reflection for phase membership.
5. Two-Phase Microstructure
- Two-phase microstructures break translation invariance and require mapping nodal indices to element-wise material data while incorporating phase-dependent moduli as unitaries.The approach represents the modulus using the identity and a material reflection, with coefficients determined by E1 and E2.Source: §5 · p. 7
5.1. Node-to-Element Mapping
- Four periodic cyclic-shift mappings carry a node to its incident element indices, factorizing across spatial registers and remaining unitary at mesh boundaries.The mapping depends on coordinate translation, not the material property or microstructure geometry.Source: §5.1 · pp. 7–8
5.2. The Material Oracle and Reflection
- The material oracle applies a phase flip according to element membership; for the centered square inclusion, its membership test uses coordinate-bit parities and is microstructure-specific.For that inclusion, the reflection uses four CNOT gates and one controlled Z, with no ancilla qubits.Source: §5.2 · p. 8
6. Two-Phase Poisson
The two-phase periodic Q4 Poisson operator is encoded exactly by combining homogeneous shifts with element-wise material reflections. The encoding uses a fixed 25-term LCU for unequal moduli, and its normalization scales with the stiffer phase’s modulus.
6. Two-Phase Poisson
- 25 LCU terms exactly encode the two-phase periodic Q4 Poisson operator for every unequal pair of moduli, microstructure, and mesh size.At equal moduli, the reflection family vanishes and the count returns to 9.Source: §6 · p. 10
- Material contrast adds no subnormalization penalty beyond scaling with the stiffer phase’s modulus, and swapping the soft and stiff phases leaves the subnormalization unchanged.The subnormalization is independent of mesh resolution and volume fraction.Source: §6 · p. 11
- The subnormalization equals the matrix infinity norm when a mesh node is surrounded entirely by the stiffer material.If no such node exists, as in a fine checkerboard, the maximum row sum is below its upper limit; an 8×8 checkerboard at 3:1 contrast has norm 10.667 against α=16.Source: §6 · p. 11
- The 2D,sc quantity reflects a worst-case material bound; across material contrast, neither the LCU term count (L=25) nor the circuit varies, while only PREP angles and αχ change.Source: §6 · p. 11
7. Two-Phase Elasticity
The section extends shift-decomposition block encodings to two-phase periodic elasticity, accounting for displacement components and the sign structure of element contributions. The resulting exact LCU has 57 terms, or 49 at ν = 1/3.
7. Two-Phase Elasticity
- The elasticity construction uses four displacement components, and its four element contributions at a node need not share a sign.Each element corner block resolves over I, Z, X, and iY; iY carries the antisymmetric part.Source: §7 · p. 11
- Variable element moduli break shear-block symmetry, leaving an antisymmetric remainder represented by the iY component.Merging restores K_xy = K_yx and removes iY from the merged family; the component remains in the reflection family.Source: §7 · p. 11
- Equation (42) gives an exact LCU for the two-phase periodic plane-stress Q4 operator, using cyclic-shift pairs with single-qubit I, Z, X, or iY, optionally preceded by one material reflection.This holds for every E1 ≠ E2, every χ, every ν in (-1, 1/2), and N = 2^m with m ≥ 2. The eight iY terms vanish at ν = 1/3 and nowhere else.Source: §7 · p. 11
- At equal phase moduli, the second term family vanishes and the LCU count falls to 17.Away from ν = 1/3, the eight iY terms do not vanish.Source: §7 · pp. 11–12
- At m = 12, the 57-term construction is contrasted with an exact Pauli expansion of 159,338,497 terms for the Figure 1 microstructure.The circuit is fixed across material contrast; only the moduli change.Source: §7 · p. 12
8. The Block-Encoding Circuit
The circuit uses reusable registers, cyclic shifts, factored state preparation, and staged SELECT operations to implement the encodings. Its decomposition-controlled term count and PREP width remain constant with mesh resolution, while shift-driven costs grow with resolution.
8.1. Registers
- Only the system register and reusable carry ancillas depend on m; the term count, PREP width, and coefficients stay constant.The Toffoli count is affine in m, with slope 8 per shifted register.Source: §8.1 · p. 12
8.2. The Cyclic Shift
- A controlled cyclic increment uses 2m − 2 Toffoli gates, m CNOT gates, and m − 1 clean ancillas, transpiling to 11m − 10 two-qubit gates.The controlled cyclic increment is the primitive whose cost grows with mesh resolution.Source: §8.2 · p. 12, Figure 3 · p. 15
8.3. PREP
- Factored PREP indices use 4, 7, 6, and 9 qubits across the four cells, and may be wider than the dense index ⌈log2 L⌉.Each index field selects an operation on one register independently; unused codes receive zero amplitude.Source: §8.3 · p. 13
8.4. SELECT
- SELECT uses four controlled shifts for homogeneous cells and eight for two-phase cells, plus at most three controlled single-qubit gates and one oracle query, regardless of L.Every gate is limited to two controls, avoiding reliance on idle circuit qubits as clean ancillas during transpilation.Source: §8.4 · p. 13
8.6. Tightness
- Across all four cell types, LCU slack is independent of m; the norm gap is independent of m only for homogeneous cells.Table 6 reports the factors at m = 5, ν = 0.3, and E1/E2 = 3.Source: Table 6 · p. 14
8.5. Circuit Cost
- PREP cost is constant in m while SELECT grows; Figure 4 reports measured transpiled two-qubit gate counts against m.PREP's arbitrary-angle rotations dominate the fault-tolerant cost described here.Source: §8.5 · p. 14, Figure 4 · p. 15
9. Implementation
The paper implements the encodings in the open-source PyBlockEncode Python library, with interfaces for two-phase Poisson and elasticity as well as homogeneous elasticity.
9. Implementation
- PyBlockEncode is an open-source Python library built on Qiskit 2.4.2 for constructing the encodings.Its importable module is pyblockencode.Source: §9 · p. 16
- The implementation exposes POISSON2D_2PHASE and ELASTICITY2D_2PHASE cell types.The two-phase results reported use a centered square inclusion with volume fraction 1/4.Source: §9 · p. 16
- At N = 4096, the homogeneous elasticity example reports L = 17, 43 qubits, 100 Toffoli gates, and 719 CX gates.The example has 33,554,432 degrees of freedom and reports α = 6.0989.Source: §9 · p. 16
- At N = 4096, the two-phase elasticity example reports L = 57, 46 qubits, 191 Toffoli gates, and 2164 CX gates.The example has 33,554,432 degrees of freedom and reports α = 19.1209.Source: §9 · p. 16
10. Conclusions
The paper presents exact shift-decomposition encodings for homogeneous elasticity and two-phase Poisson and elasticity on periodic finite-element grids. It gives fixed-size two-phase LCUs and identifies boundaries and extensions of the formulation.
10. Conclusions
- For homogeneous 2D elasticity at m = 12, the 17-term LCU is contrasted with an 18.9-million-term Pauli expansion.The example corresponds to 33.6 million degrees of freedom.Source: §10 · p. 16
- Two-phase Poisson and elasticity use 25 and 57 LCU terms, respectively, with elasticity dropping to 49 at ν = 1/3.The counts do not depend on grid resolution, volume fraction, or phase contrast; the subnormalizations are closed forms independent of resolution and volume fraction.Source: §10 · p. 17
- The construction is limited to regular grids, periodic boundary conditions, and isotropic phases.Non-periodic boundaries and unstructured meshes require additional de-periodization and mapping, which are not treated.Source: §10 · p. 17
- The construction extends to arbitrary microstructures, discretized functionally graded phases, and other translation-invariant finite-element operators on regular periodic grids.The paper also sketches a 3D extension, with additional terms and subnormalization for vector cells.Source: §10 · p. 17
- Nonlinear elasticity and the end-to-end cost of a QSVT-based solve remain outside the present formulation.Whether the tangent-operator oracle can be updated rather than rebuilt at each Newton step remains open.Source: §10 · p. 17
Use of AI Tools
The author reports using Claude and Gemini during manuscript preparation for code development and text drafting, then reviewing and editing all content.
Use of AI Tools
- Claude and Gemini were used for code development and text drafting; the author reviewed and edited all content and takes responsibility for its accuracy and integrity.The author identifies Claude (Anthropic) and Gemini (Google).Source: Use of AI Tools · p. 17
A. The Four Circuits
The appendix presents four encodings at m=2, showing their gates and the PREP-index reindexing between terms.
A. The Four Circuits
- At m=2, the four circuits show only the two preparations boxed, with other gates drawn as built; reindex gaps clear the shift-control qubit, recode the PREP index, and set the control again.These reindex gaps appear between terms.Source: A. The Four Circuits · p. 17
- The scalar homogeneous circuit has L=9 and α=16/3 at m=2; its two spatial-register multiplexers compute and uncompute the select control from a two-bit field.X gates around each Toffoli choose the field value controlling the shift.Source: Figure A.1 · p. 18
- The scalar two-phase circuit has L=25 and α=16 at E1/E2=3; its added stages implement the Equation (33) conjugation using conditional shifts and a g-controlled oracle.The conditional shifts act on each spatial register and are then undone.Source: Figure A.2 · p. 18
- The homogeneous elasticity circuit has L=17 and α=6.099 at ν=0.3.The figure shows the circuit at m=2.Source: Figure A.3 · p. 19
- The two-phase elasticity circuit has L=57 and α=19.121 at ν=0.3 and E1/E2=3, with four spatial multiplexers, a dof multiplexer, and a reflection stage.The dof multiplexer uses Z, X, and iY; the reflection brackets implement the conjugation of Equation (33), read right to left.Source: Figure A.4 · p. 20