Paulihedral: a generalized block-wise compiler optimization framework for Quantum simulation kernels

Quantum simulation kernels compile into enormous gate sequences, and gate-level compilers can no longer see the physics inside them — Paulihedral keeps the program as a sum of Pauli strings, where reordering is provably harmless, then schedules, synthesizes, and maps whole blocks at once, cutting gate counts and circuit depth by roughly half.

Why this problem is worth solving

Quantum computing’s founding purpose — Feynman’s original argument — was simulating quantum physics. The machinery for it, applying the operator exp(iHt) where H is the system’s

The compilation recipe is standard. H is decomposed into a weighted sum of

Why care about shaving gates? Because on near-term hardware every two-qubit gate is error-prone and every layer of depth spends scarce coherence time — gate count and depth translate directly into whether the answer survives. On future fault-tolerant machines, gates are costly in error-correction resources instead. Either way, the kernel’s size makes it the highest-leverage optimization target in quantum compilation.

What people did before, and where it broke

Generic gate-level compilers. Qiskit and t|ket⟩ take the flattened circuit and apply local rewriting: cancel adjacent inverse gates, match small templates, remap qubits to satisfy hardware connectivity. These passes are designed for arbitrary circuits, so they cannot assume what is true here: that the circuit is a product of per-term templates whose order was a free choice, whose synthesis shape was a free choice (any CNOT tree connecting the active qubits, any root), and whose terms obey algorithm-level constraints. t|ket⟩‘s strongest simulation-specific technique (simultaneous diagonalization) works at the operator level but scales poorly — on large benchmarks it ran past 72 hours in the paper’s experiments.

Algorithm-specific compilers. Term-ordering heuristics for chemistry, dedicated QAOA compilers — effective in their niches, but each hard-codes one algorithm’s constraints, precisely because no shared IR existed that could express “these strings must stay together” or “these share a parameter” in general.

The missed structure, concretely. Two adjacent templates whose strings share non-identity operators on many qubits can cancel most of their boundary gates — if the compiler orders them adjacently and synthesizes their trees to match. Blocks touching disjoint qubits can run in parallel — if scheduled into one layer. On superconducting chips, the CNOT tree can be embedded directly into the hardware’s connectivity graph — if synthesis and mapping talk to each other instead of running as separate stages. All three are invisible at gate level.

The idea

Choose an IR whose algebra makes the hard transformations trivially legal. At gate level, reordering operations is dangerous — quantum gates are matrix products, and products do not commute. But the kernel’s meaning is the Hamiltonian, a matrix sum — and sums always commute. Pauli IR defines its formal semantics as that sum, so any reordering of blocks or of strings within blocks is semantics-preserving by the definition of the IR. The entire optimization space that gate-level compilers must painstakingly prove safe, term by term, Paulihedral gets by construction. (Different orderings do change the higher-order approximation error of

Blocks carry the algorithm’s rules. UCCSD chemistry requires certain string groups to stay together (symmetry, shared parameters); QAOA shares one parameter across all strings. The pauli_block is the unit of scheduling, so constraints ride along through every pass — this is what makes one framework serve algorithms that previously needed bespoke compilers.

Schedule for your objective. Gate-count-oriented scheduling sorts strings lexicographically so consecutive strings share operator prefixes — shared operators become cancellable gates. Depth-oriented scheduling instead treats blocks as jobs in layers: place the largest block, then greedily add blocks whose active qubits are disjoint; these execute simultaneously. The ablation shows they are genuinely different tools: on QAOA-style benchmarks, depth-oriented wins by 84.2% depth reduction where gate-count-oriented finds nothing.

Synthesize with the freedom the template offers. Each string’s CNOT tree may connect its active qubits in any shape, rooted anywhere. The FT pass exploits this by pairing layers with maximal operator overlap and choosing tree shapes so that a string’s right tree mirrors its successor’s left tree — whole subtrees and basis layers annihilate. The SC pass exploits it differently: rather than synthesizing an ideal circuit and then paying SWAP gates to fit the chip, it embeds the tree in the chip’s coupling graph from the start — core qubits (active in every string of the block) anchor the tree, paths are chosen by error rate, and when a tree edge meets an inactive qubit, the SWAP that would have been overhead becomes part of the construction.

program = [ (strings, θ₁), (strings, θ₂), … ]
semantics = Σ weight × string (a Hamiltonian)

Why it works

• The kernel’s meaning is a sum, and sums commute → reordering blocks is legal by the IR’s semantics, not by case-by-case proof → the scheduler explores a space gate-level compilers cannot even represent safely.
• Cancellation between templates depends on adjacency and on tree shape → scheduling (who is adjacent) and synthesis (which tree) are decided together, both aware of operator overlap → boundary gates annihilate at scale instead of by lucky local pattern-match.
• Blocks preserve algorithmic constraints through every pass → one framework serves UCCSD, QAOA, and Hamiltonian simulation without bespoke compilers → generality and deep optimization stop being a trade-off.
• On hardware, the template’s flexible tree meets the chip’s fixed graph → embedding the tree in the coupling map merges synthesis with mapping → SWAP overhead (the dominant near-term cost) is largely designed away rather than minimized after the fact.
• All passes work on strings and blocks (sorting, pairwise overlap), not on the exploded gate list → near-linear practical scaling → ~5% compile-time overhead where operator-level baselines time out beyond 72 hours.

What it costs

• Scope. The framework optimizes simulation kernels; programs outside that structure (arbitrary circuits) see no benefit — the IR’s power comes precisely from its restriction.
• Trotter-order effects. Reordering preserves the represented Hamiltonian, but different orders give (bounded, algorithmically accepted) different Trotter approximation errors — fidelity of the final answer is governed by that budget, not bit-identical output.
• Heuristic passes. Scheduling and embedding are greedy heuristics with no optimality guarantee; objectives (gates vs depth) must be chosen per backend by the user.
• A second compiler still runs. Output circuits pass through Qiskit/t|ket⟩ generic backends; Paulihedral replaces the simulation-specific stage, not the whole toolchain.
• Evaluation-scale hardware. The real-system study is a 16-qubit device and 1-level QAOA — meaningful end-to-end evidence, small relative to the 80-qubit compilation benchmarks.

The evaluation

Thirty-one benchmarks span the kernel’s habitats: UCCSD chemistry ansatzes (8–28 qubits), QAOA MaxCut on regular and random graphs plus traveling-salesman encodings, five molecular Hamiltonians from PySCF (N₂, H₂S, MgO, CO₂, NaCl), Ising and Heisenberg models in 1D/2D/3D, and random Hamiltonians of 30–80 qubits with 5n² Pauli strings. The superconducting target is IBM’s 65-qubit Manhattan; the fault-tolerant target follows standard gate-count/depth accounting. Baselines: t|ket⟩ with simultaneous diagonalization (‘TK’) and an algorithm-specific QAOA compiler for the first stage, with Qiskit L3 and t|ket⟩ O2 as generic second stages.