pith. sign in

arxiv: 2606.11478 · v1 · pith:PZ77UZBGnew · submitted 2026-06-09 · 🪐 quant-ph · cs.NA· math.NA

PHASE: Pauli Hierarchical Assembly on Subdivided Elements for Quantum-Compatible Operator Synthesis

Tillman Philo , Caglar Oskay This is my paper

Pith reviewed 2026-06-27 12:54 UTC · model grok-4.3

classification 🪐 quant-ph cs.NAmath.NA
keywords Pauli decompositionfinite element methodstiffness matrixquantum operator synthesishierarchical assemblymesh partitioningquantum computingtensorized decomposition
0
0 comments X

The pith

A hierarchical mesh-partitioning algorithm assembles Pauli coefficients for finite-element stiffness matrices at sub-quadratic exponential cost.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents PHASE, an algorithm that decomposes finite-element stiffness matrices into sums of Pauli strings for use on quantum computers. It organizes the decomposition by recursively subdividing the mesh and combining full- and reduced-space tensorized decompositions with fast Walsh-Hadamard aggregation across scales. This produces a dimension-dependent drop in the exponential scaling factor from 2 to some γ_d less than 2. A reader would care because the naive expansion grows as 8 to the log N and quickly becomes impossible for realistic problem sizes, while existing algebraic methods ignore the geometric structure of the mesh. The result makes operator synthesis feasible for larger continuum models under ordinary mesh assumptions.

Core claim

PHASE is a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales, employs a hybrid strategy of full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation, and yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity from 2^{2⌈log₂N⌉} to 2^{γ_d ⌈log₂N⌉} with γ_d < 2 under standard mesh regularity and balanced partition assumptions.

What carries the argument

Recursive mesh partitioning that organizes element contributions across spatial scales, combined with hybrid Tensorized Pauli Decomposition and Fast Walsh-Hadamard Transform aggregation to assemble global Pauli coefficients.

If this is right

  • Pauli decomposition of stiffness matrices becomes feasible for substantially larger finite-element models than with naive or algebraically sparse methods.
  • Quantum-compatible operator synthesis for large-scale finite-element models improves in asymptotic cost under the stated mesh assumptions.
  • The exponential base in the complexity bound now depends explicitly on spatial dimension rather than remaining fixed at 2.
  • Hybrid full- and reduced-space tensorized decompositions plus Walsh-Hadamard aggregation replace direct enumeration of all Pauli strings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hierarchical organization could be applied to other local operators that arise in quantum algorithms for PDEs, such as mass matrices or load vectors.
  • If the exponent reduction holds in practice, it lowers the barrier to testing whether quantum linear-system solvers can outperform classical ones on realistic continuum problems.
  • Dimension-dependent scaling suggests that three-dimensional engineering models may benefit more than one- or two-dimensional toy problems.
  • The approach opens the possibility of geometry-aware circuit synthesis that respects the underlying discretization rather than treating the operator as an unstructured matrix.

Load-bearing premise

Recursive mesh partitioning must deliver the claimed dimension-dependent exponent reduction when the mesh satisfies standard regularity and balanced-partition conditions.

What would settle it

A measured assembly cost on a sequence of uniformly refined meshes whose fitted exponent remains at or above 2 would show that the reduction does not occur.

Figures

Figures reproduced from arXiv: 2606.11478 by Caglar Oskay, Tillman Philo.

Figure 1
Figure 1. Figure 1: Quantum-compatible finite element assembly. and block-encoding schemes, is to expand operator A in the Pauli basis [21, 24–26]: A = X P ∈Pn αP P, αP := 1 2 n Tr(P A), (2) where Pn is the complete set of 4n tensor product Pauli operators acting on n qubits. The Pauli basis is a natural and practical choice for several reasons. First, it forms an orthonormal basis for the space of 2n × 2 n complex matrices u… view at source ↗
Figure 2
Figure 2. Figure 2: Recursive separator hierarchy and associated cut sets. The decomposition follows immediately from the disjointness of the defining conditions on node labels and the discrete nature of the mesh. This single-separator decomposition defines the geometric primitives used in the recursive hi￾erarchy. Applying the same construction to each subdomain Ω, Ω0, Ω1, . . . at successive depths produces a family of sepa… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of recursive geometric partitioning and binary prefix labeling. new separator Σq¯ by a local Lipschitz function sq¯ : Ωq¯ → R, Σq¯ = {x : sq¯(x) = 0}. (22) This induces the next pair of subdomains Ωq¯1 = {x ∈ Ωq¯ : sq¯ ≥ 0}, Ωq¯0 = {x ∈ Ωq¯ : sq¯ < 0} (23) and the associated submeshes Tq¯1, Tq¯0, and T × q¯ . The recursion continues until each leaf domain Ωq¯ contains exactly one element or th… view at source ↗
Figure 4
Figure 4. Figure 4: Dual assembly paths for hierarchical pauli decomposition of cut elements. is the key structural relation exploited by PHASE’s hybrid assembly. It isolates at depth k, a geometrically thin set of cut elements whose cardinality scales sublinearly with the global problem size (cf. the N(d−1)/d scaling of cut sets), and it preserves exactness: no element is double-counted, and no contribution is omitted. The P… view at source ↗
Figure 5
Figure 5. Figure 5: Meshes A, B and C at varying levels of refinement for empirical PHASE runtime testing. [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: PHASE empirical runtime scaling versus theoretical bounds for three FE meshes. Orange: [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗
read the original abstract

Efficiently decomposing finite element stiffness matrices into the Pauli basis is challenging due to the exponential growth of Pauli strings with problem size. A naive Pauli expansion requires $\Theta(8^{\lceil \log_2 N \rceil})$ operations, where $N$ denotes the number of degrees of freedom, rendering direct decomposition infeasible for large systems. Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the geometric organization intrinsic to finite element discretizations, and consequently exhibit poor scaling for stiffness matrices. To address this problem, we introduce PHASE, a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales. PHASE employs a hybrid strategy that combines full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation to assemble global Pauli coefficients efficiently. We show that this approach yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity relative to existing methods, reducing the cost from $2^{2{\lceil \log_2 N \rceil}}$ to $2^{\gamma_d{\lceil \log_2 N \rceil}}$ with $\gamma_d < 2$ under standard mesh regularity and balanced partition assumptions. These results substantially improve the feasibility of quantum-compatible operator synthesis for large-scale finite element models.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper introduces PHASE, a hierarchical geometry-aware algorithm for decomposing finite element stiffness matrices into the Pauli basis. It combines recursive mesh partitioning with a hybrid strategy of full- and reduced-space Tensorized Pauli Decomposition and Fast Walsh-Hadamard Transform aggregation. The central claim is an asymptotic complexity reduction from 2^{2⌈log₂N⌉} to 2^{γ_d ⌈log₂N⌉} with γ_d < 2 under standard mesh regularity and balanced partition assumptions, improving feasibility of quantum-compatible operator synthesis for large-scale models.

Significance. If the claimed dimension-dependent exponent reduction is rigorously derived and the hybrid strategy is shown to be dominated by the improved term rather than reverting to baseline cost, the work would meaningfully advance scalable Pauli synthesis for finite-element operators by exploiting geometric structure absent from prior algebraic approaches.

major comments (2)
  1. [Abstract] Abstract: the naive baseline is stated both as Θ(8^{⌈log₂N⌉}) and as 2^{2⌈log₂N⌉}; these are inconsistent because 8^k = 2^{3k}. The claimed reduction cannot be evaluated until the baseline is stated uniformly.
  2. [Abstract] Abstract: the central claim that recursive mesh partitioning yields a recurrence whose solution is 2^{γ_d k} with γ_d < 2 is unsupported; no recurrence, master-theorem application, or explicit derivation of γ_d appears. Without this analysis it is impossible to confirm that the hybrid Tensorized Pauli Decomposition + FWHT term is dominated by the improved exponent rather than the baseline 2^{2k} cost.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and for identifying issues in the abstract that require clarification. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the naive baseline is stated both as Θ(8^{⌈log₂N⌉}) and as 2^{2⌈log₂N⌉}; these are inconsistent because 8^k = 2^{3k}. The claimed reduction cannot be evaluated until the baseline is stated uniformly.

    Authors: We agree that the abstract contains an inconsistency in the baseline complexity expression. The Θ(8^{⌈log₂N⌉}) phrasing was an inadvertent error; the intended naive cost is 2^{2⌈log₂N⌉} (equivalent to 4^{⌈log₂N⌉}), which is the correct count of operations for a direct Pauli decomposition of an N×N matrix without exploiting structure. We will revise the abstract to use a single, uniform expression for the baseline throughout. revision: yes

  2. Referee: [Abstract] Abstract: the central claim that recursive mesh partitioning yields a recurrence whose solution is 2^{γ_d k} with γ_d < 2 is unsupported; no recurrence, master-theorem application, or explicit derivation of γ_d appears. Without this analysis it is impossible to confirm that the hybrid Tensorized Pauli Decomposition + FWHT term is dominated by the improved exponent rather than the baseline 2^{2k} cost.

    Authors: The full derivation of the recurrence, its solution via the master theorem, and the explicit bound γ_d < 2 (under the standard mesh regularity and balanced partition assumptions stated in the paper) appears in Section 4. The analysis there also shows that the hybrid full/reduced-space TPD + FWHT aggregation is dominated by the improved 2^{γ_d k} term rather than reverting to the 2^{2k} baseline. To make this immediately verifiable from the abstract, we will add a concise statement of the recurrence and the resulting exponent bound in the revised abstract. revision: yes

Circularity Check

0 steps flagged

No derivation chain or equations visible; no circularity identified

full rationale

The abstract asserts a dimension-dependent complexity reduction to 2^{γ_d ⌈log₂N⌉} with γ_d < 2 under mesh regularity and balanced partition assumptions, but supplies no equations, recurrences, master theorem applications, or derivation steps. Without any exhibited mathematical chain in the provided text, no load-bearing step can be quoted that reduces by construction to fitted inputs, self-citations, or ansatzes. The result is therefore treated as self-contained against external benchmarks, yielding no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on unverified assumptions about mesh properties; no free parameters, invented entities, or additional axioms are stated in the abstract.

axioms (1)
  • domain assumption standard mesh regularity and balanced partition assumptions
    Invoked to achieve the stated reduction in the exponential scaling exponent.

pith-pipeline@v0.9.1-grok · 5771 in / 1147 out tokens · 19994 ms · 2026-06-27T12:54:00.643097+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references

  1. [1]

    Zienkiewicz, Robert L

    Olek C. Zienkiewicz, Robert L. Taylor, and Jian Z. Zhu.The Finite Element Method: Its Basis and Fundamentals. Elsevier / Butterworth-Heinemann, Oxford, UK, 7th edition, 2005

    2005

  2. [2]

    Zienkiewicz, Robert L

    Olek C. Zienkiewicz, Robert L. Taylor, and David D. Fox.The Finite Element Method for Solid and Structural Mechanics. Elsevier / Butterworth-Heinemann, Oxford, UK, 7th edition, 2013

    2013

  3. [3]

    Brenner and L

    Susanne C. Brenner and L. Ridgway Scott.The Mathematical Theory of Finite Element Methods, volume 15 ofTexts in Applied Mathematics. Springer, Princeton, NJ, 3rd edition, 2007

    2007

  4. [4]

    Thomas J. R. Hughes.The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Dover Civil and Mechanical Engineering. Dover Publications, Garden City, NY, 1st edition, 2000

    2000

  5. [5]

    Davis.Direct Methods for Sparse Linear Systems

    Timothy A. Davis.Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2006

    2006

  6. [6]

    January 1994

    Alan George, Joseph Liu, and Esmond Ng.Computer Solution of Sparse Linear Systems. January 1994. Unpublished manuscript updates to the 1981 Prentice-Hall text. Features the SPARSPAK software package platform layout

    1994

  7. [7]

    Society for Industrial and Applied Mathematics, Philadelphia, PA, 2nd edition, 2003

    Yousef Saad.Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2nd edition, 2003

    2003

  8. [8]

    Oosterlee, and Anton Sch¨ uller.Multigrid

    Ulrich Trottenberg, Cornelis W. Oosterlee, and Anton Sch¨ uller.Multigrid. Elsevier / Academic Press, San Diego, CA, 2001

    2001

  9. [9]

    The future of computing beyond Moore’s Law.Philosophical Transactions of the Royal Society A, 378(2166):20190061, March 2020

    John Shalf. The future of computing beyond Moore’s Law.Philosophical Transactions of the Royal Society A, 378(2166):20190061, March 2020

    2020

  10. [10]

    The opportunities and challenges of exascale computing: Summary report of the ASCAC subcommittee

    Advanced Scientific Computing Advisory Committee (ASCAC) Subcommittee on Exascale Computing. The opportunities and challenges of exascale computing: Summary report of the ASCAC subcommittee. Technical report, U.S. Department of Energy, Office of Science, 2010. Robert Rosner, Chair. 28

    2010

  11. [11]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations.Physical Review Letters, 103(15), October 2009

    2009

  12. [12]

    Childs, Robin Kothari, and Rolando D

    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, January 2017

    1920

  13. [13]

    Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J

    Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles. Variational quantum linear solver.Quantum, 7:1188, November 2023

    2023

  14. [14]

    Quantum algorithms and the finite element method

    Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. Physical Review A, 93(3), March 2016

    2016

  15. [15]

    Quantum realization of the finite element method

    Matthias Deiml and Daniel Peterseim. Quantum realization of the finite element method. Mathematics of Computation, August 2025

    2025

  16. [16]

    Ward, and Caglar Oskay

    Abhishek Arora, Benjamin M. Ward, and Caglar Oskay. An implementation of the finite element method in hybrid classical/quantum computers, 2025

    2025

  17. [17]

    Alkadri, Tyler D

    Ahmad M. Alkadri, Tyler D. Kharazi, K. Birgitta Whaley, and Kranthi K. Mandadapu. A quantum algorithm for the finite element method, 2025

    2025

  18. [18]

    Qafe 2: Quantum accelerated multiscale finite element analysis, 2026

    Yiren Wang, Michael Ortiz, and Fehmi Cirak. Qafe 2: Quantum accelerated multiscale finite element analysis, 2026

    2026

  19. [19]

    A quantum computing concept for 1-d elastic wave simulation with exponential speedup.Geophysical Journal Inter- national, 238(1):321–333, May 2024

    Malte Schade, Cyrill B¨ osch, V´ aclav Hapla, and Andreas Fichtner. A quantum computing concept for 1-d elastic wave simulation with exponential speedup.Geophysical Journal Inter- national, 238(1):321–333, May 2024

    2024

  20. [20]

    Childs and Nathan Wiebe

    Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations, November 2012

    2012

  21. [21]

    Berry, Andrew M

    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), March 2015

    2015

  22. [22]

    Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C

    M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms.Nature Reviews Physics, 3(9):625–644, August 2021

    2021

  23. [23]

    Universal quantum simulators.Science, 273(5278):1073–1078, 1996

    Seth Lloyd. Universal quantum simulators.Science, 273(5278):1073–1078, 1996

    1996

  24. [24]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization.Quantum, 3:163, July 2019. 29

    2019

  25. [25]

    Love, Al´ an Aspuru-Guzik, and Jeremy L

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Al´ an Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor.Nature Communications, 5(1), July 2014

    2014

  26. [26]

    Chow, and Jay M

    Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.Nature, 549(7671):242–246, September 2017

    2017

  27. [27]

    Tensorized pauli decomposition algorithm.Physica Scripta, 99(8):085128, July 2024

    Lukas Hantzko, Lennart Binkowski, and Sabhyata Gupta. Tensorized pauli decomposition algorithm.Physica Scripta, 99(8):085128, July 2024

    2024

  28. [28]

    A tree-approach pauli decomposition algorithm with application to quantum computing, 2024

    Oc´ eane Koska, Marc Baboulin, and Arnaud Gazda. A tree-approach pauli decomposition algorithm with application to quantum computing, 2024

    2024

  29. [29]

    Georges, Bjorn K

    Timothy N. Georges, Bjorn K. Berntson, Christoph S¨ underhauf, and Aleksei V. Ivanov. Pauli decomposition via the fast walsh-hadamard transform.New Journal of Physics, 27(3):033004, February 2025

    2025

  30. [30]

    Miller, Shang-Hua Teng, William Thurston, and Stephen A

    Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. Geometric separators for finite-element meshes.SIAM Journal on Scientific Computing, 19(2):364–386, 1998

    1998

  31. [31]

    Lipton and Robert Endre Tarjan

    Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979

    1979

  32. [32]

    pushing the node byεalong the normal

    Alan George. Nested dissection of a regular finite element mesh.SIAM Journal on Numerical Analysis, 10(2):345–363, 1973. A Analytical Derivations A.1 Derivation of Cut Element Scaling We derive the asymptotic scaling of the number of cut elements introduced at a given depth of the recursive partition hierarchy. Throughout, we work under the mesh assumptio...

    1973