PaperlayerView exact revision on arXiv

Source-linked AI summary

Plateau-Constrained Selection of Commuting Phase-Term Orderings Under a Fixed Maintained-Parity Compiler Contract

Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu

arXiv:2608.27592v1quant-phcs.ET

TL;DR

Prior methods leave equal-cost commuting-term tours uncharacterized, despite their potential to improve downstream compilation. The paper uses a two-stage permutation search that certifies support optimality, then selects among equal-cost tours under a frozen routing score. The resulting depth benefit transfers across tested SABRE seeds, generators, and sizes, but reverses under BasicSwap and does not establish a guaranteed hardware benefit.

  • Problem

    Prior ordering methods do not characterize or exploit the set of equal-cost commuting phase-term tours.

  • Method

    A classical two-stage search certifies the primary support optimum, samples equal-cost tours, and selects one using a frozen downstream routed score while preserving that optimum.

  • Results

    Depth selection reduced opposite-SABRE-seed depth by 12.83% at 36 terms, with transfer to a second generator and 48 terms, but reversed under BasicSwap.

  • Takeaways & Limitations

    Equal-primary-cost tours provide useful router-conditioned compiler freedom, rather than a guaranteed hardware benefit.

  • Takeaways & Limitations

    Evidence is limited to fixed-placement synthetic generators, 24 candidates under one placement and basis, and one IBM Heron panel, leaving broader workloads and router populations outside scope.

Abstract

from arXiv · show

Ordering objectives for commuting phase terms can have many equal optima, yet prior methods do not characterize or exploit those ties. We use a classical two-stage permutation search under fixed placement and maintained-parity quantum lowering: Stage 1 certifies the primary support optimum, and Stage 2 samples equal-cost tours and selects by a frozen routed score. On synthetic 16-qubit assignment-Ising instances, exact counting through 20 terms establishes instance-dependent multiplicity; when the support lower bound is attained, the reversal-reduced width equals the number of undirected Hamiltonian paths of the support line graph. A revised engineering analysis found 9.14% fewer routed controlled-NOT gates than unoptimized order, while the registered comparison found 11.10% fewer than prior stochastic search. Among 24 sampled minimum-support-cost orders at 36 terms, direct-depth selection reduced opposite-SABRE-seed depth by 12.83% in all 20 aggregates, whereas a matched 24-restart control changed depth by only -0.41% (unresolved). Candidate rankings persisted across SABRE routing seeds, explaining why selection survived routing re-randomization. The depth benefit transferred to a second generator and to 48 terms, but reversed under BasicSwap. On a prospective IBM Heron panel, raw generator error shifted by -0.0025 (-0.59%); fixed-panel shot uncertainty excluded zero, but term-seed inference remained unresolved. Equal-primary-cost tours are a useful router-conditioned compiler freedom, not a guaranteed hardware benefit.

I. INTRODUCTION

The paper characterizes equal-primary-cost orderings under a fixed compiler contract and tests whether selecting among those ties improves downstream compilation metrics without changing the certified support cost.

  • Motivation: Equal-cost commuting-term tours create a compiler freedom that prior cancellation-oriented methods do not characterize or exploit.The study asks how much ordering freedom survives fixed placement and lowering, and whether it can improve a downstream quantity.
  • Opportunity: Among equal certified support-cost tours, routed mean depths were 228.6, 233.8, and 256.7, demonstrating roughly 12% variation at zero primary-cost difference.The introduction identifies this variation as systematic and exploitable.
  • Compiler contract: The fixed contract holds placement, mapped support realizations, coefficient associations, and maintained-parity workspace behavior constant; only complete term permutation changes.Accepted candidates must preserve occurrence, provenance, phase, and empty-final-parity checks.
  • Two-stage method: Stage 1 certifies the support optimum, while Stage 2 selects among equal-cost tours using a downstream routing criterion.The second stage preserves the coarse support optimum exactly rather than trading primary cost for the secondary score.
  • Structural results: The paper provides support-cost stratification, exact optimum counts through 20 terms, operating-scale lower bounds, and a line-graph attainability result.These results formalize multiplicity rather than treating the optimum as a unique order.
  • Contribution: The claimed contribution is a strict plateau-constrained second stage under a fixed mapped-state contract, distinct from prior TSP ordering, depot transformation, and shared-ancilla lowering.The paper positions the novelty in formal multiplicity analysis and downstream representative selection.

C. ROUTING, SEARCH, AND HARDWARE EVALUATION

The evaluation fixes the logical-to-physical and parity-preserving compilation contract, validates legal circuit realizations, and measures routing and hardware endpoints on synthetic assignment-QUBO workloads.

  • Scope: Routing and hardware interpretation remains bounded because the study uses synthetic workloads, fixed placement, one realization per support, and limited topology and device coverage.The evidence excludes molecular workloads, arbitrary supports, a router population, and broader hardware generalization.
  • Workload: The workload uses a deterministic four-chiplet, four-site assignment-QUBO model converted into quadratic Pauli-Z terms over 16 assignment variables.Term seeds sample distinct quadratic terms for the 36- and 48-term studies.
  • Fixed contract: Placement is deterministic and identical across methods within each term-seed/topology bank, while only term occurrence order varies.Logical and physical rankings determine the fixed placement and workspace assignment.
  • Support realization: Each mapped support is realized deterministically using shortest paths and a metric-MST construction, with exact shortest-path behavior for pair supports.The size-three/four-arm construction remains a heuristic rather than a claimed Steiner optimum.
  • Parity lowering: Maintained parity reuses shared computation between consecutive supports and uncomputes the final workspace state, with no added ancilla or support aggregation.The emitted component must contain every occurrence once and return the workspace to empty.
  • Validation: Validation checks permutation, coefficient/provenance alignment, phase occurrence, phase-polynomial equality, final linear-map identity, and hardware-panel statevector agreement.These checks are intended to ensure reported differences arise from alternative legal realizations of one component.

IV. MAPPED STATE-TRANSITION OBJECTIVES

The section defines support- and tree-based transition objectives for fixed mapped parity states, then characterizes support-cost strata and their degeneracy. At the support lower bound, optimal orderings correspond to Hamiltonian paths in the support line graph, although attainability and counting remain computationally limited.

  • Objective construction: The mapped state uses a binary support mask and physical parity-tree edge set, with the empty depot representing workspace reset.The resulting objective is a symmetric depot-cycle TSP over distinct occurrences, using support Hamming distance and mapped edge-set distance.
  • Objective construction: The combined objective charges logical support mismatches and physical edge edits, with fixed coefficient 0.05.The coefficient was selected empirically and fixed before the 36/48-term campaign, without a claim of theoretical optimality.
  • Support-cost strata: For n pair-support occurrences, Hclosed takes values in the even alphabet {4, 6, . . . , 4n}, inducing at most 2n −1 support-cost strata.For distinct supports, the number of values is at most n; k counts consecutive disjoint support pairs in Hclosed(O) = 2n + 2 + 2k.
  • Support-cost strata: The minimum support cost Hclosed = 2n + 2 is attainable exactly when the support line graph has a Hamiltonian path.Reversal-reduced optimum-stratum width then equals the number of undirected Hamiltonian paths of that line graph.
  • Attainability limits: Lower-bound attainability is observed rather than guaranteed: it held in every frozen 36- and 48-term instance but only 11 of 18 exact-ladder instances.The corresponding unrestricted edge-Hamiltonian-path decision problem is NP-complete, and connectivity is necessary but not sufficient.
  • Tree refinement: The tree refinement can reverse a one-two-unit support preference only when T(O) −T(O′) > 2/w; equality leaves the tours tied.For w = 0.05, more than 40 opposing tree-edge edits are needed for a strict adjacent-stratum reversal.

D. HISTORICAL COMPOSITE AND TOUR DEGENERACY

This section contrasts historical composite objectives with the structure-preserving ordering pass and introduces plateau-constrained secondary selection. Distinct equal-support-cost tours can have similar routed outcomes, motivating representative choice within the certified primary optimum.

  • Ordering pass: Algorithm 1 validates occurrences and placement, constructs mapped states, solves the depot tour, validates the order, and emits the maintained-parity component.Its implemented pairwise matrix construction costs O(n^2|E|/w) word operations, followed by canonical rescoring and contract checks.
  • Historical composite: The historical composite JH combines the prior score JW with a 0.05-weighted closed tree-transition term.It retains directional support-distance behavior and asymmetric depot arcs, forming a directed nonmetric cycle.
  • Secondary selection: The new plateau walk preserves exact Hclosed cost while generating reversal-canonical candidates for secondary evaluation.It uses 100,000 reversal or relocation proposals, a candidate budget K = 24, and rejects any nonzero support-cost change.
  • Secondary selection: The Stage-2 guarantee is limited to unchanged Hclosed; depth, CX, and two-qubit depth are evaluated separately under the opposite routing seed.Thus equal primary cost does not entail equal routed cost, and opposite-seed evaluation is an experimental rather than algorithmic step.
  • Tour degeneracy: JSPT and JH OR-Tools tours shared 73.8% of adjacencies, yet differed by only −2.9 routed CX (−0.67%).The LKH-3 comparison differed by −0.9 CX (−0.22%), with Holm p = 1.0; overlapping local structures occupied a common routed-cost regime.

V. METHODS

The methods combine exact and practical solvers with fixed software, routing, topology, and statistical protocols. The campaign evaluates primary ordering, plateau selection, and engineering comparisons while documenting a post-outcome change to the revised primary analysis.

  • Solvers: Held–Karp supplies exact optima, while OR-Tools and LKH-3 provide practical reference solvers under fixed budgets.OR-Tools uses 5 seconds; LKH-3 uses ten runs with a 9-second effective budget, while CEM samples 7,200 orders.
  • Scaling and exactness: OR-Tools reached the pair-support lower bound 2n + 2 at every tested size from 24 through 120 terms.This deployability measurement reports Stage-1 software cost only and generated no new routes beyond 48 terms.
  • Routing campaign: The study uses 20 independent 36-term seeds across three fixed topologies and two transpiler seeds.The topologies are heavy hex and two modular graphs with one or three bridges; the descriptive landscape uses a fixed 24-bank selection rule.
  • Inference: The analysis reports paired means, percentage changes, bootstrap intervals, Wilcoxon tests, wins/ties/losses, and Holm correction across declared inferential families.A global correction over 64 formal comparisons left 28 surviving, including every headline routing and Stage-2 depth endpoint.
  • Analysis provenance: The revised primary engineering comparison changed after the campaign from JSPT OR-Tools versus JW-CEM to JSPT OR-Tools versus Default.The authors identify this post-outcome hierarchy change as a deviation while retaining the registered prior-work replication test unchanged.
  • Scope: The 48-term arm repeats the methods and 20 scientific units as a secondary analysis, while production-scale extrapolation beyond 120 terms changes the workload.The 36- and 48-term results are not rescued or invalidated by the secondary scale arm.

C. PRIOR COST AND FULL RESYNTHESIS

The paper fixes a compiler contract and compares transition objectives, exact optimization, plateau sampling, routing controls, and hardware evaluation under maintained-parity constraints.

  • Gui-open reproduces the archival transition scorer rather than Gui et al.’s broader synthesis freedom.
  • The study uses fixed placement, maintained-parity realization, exact equivalence checks, independent routing seeds, and separate hardware studies.
  • Exact support-objective optimization propagates both minimum cost and the number of minimizing directed depot paths, with reversal-reduced reporting dividing by two orientations.
  • Operating-scale plateau widths at 36 and 48 terms are lower bounds, not estimates of the full equal-cost strata.
  • The strict Stage-2 protocol samples 24 distinct reversal-canonical tours at certified Hclosed = 74 without relaxing to neighboring support strata.

VI. STAGE-1 ORDERING RESULTS

Stage 1 reliably reaches the best support stratum and improves routed-CX over unoptimized and prior stochastic orders, while matched restart spending does not reproduce the same advantage.

  • OR-Tools and LKH-3 matched the exact optimum on every registered 10/12/14/16/18/20-term unit, with zero relative gap.
  • 9.14% fewer routed-CX gates than Default was achieved by JSPT OR-Tools in all 20 term-seed units.
  • 11.10% fewer routed CX than JW-CEM was achieved by JSPT OR-Tools, which won 19/20 units.
  • 382 transpiler restarts recovered only 10.49% of the original Default-to-OR-Tools gap, with restarted order still above JSPT OR-Tools in 19/20 units.
  • Within the equal-cost stratum, canonical minus JSPT OR-Tools depth was −10.96%, while the routed-CX difference of −0.96% remained unresolved.
  • Topology-specific results retained the practical and prior-study-comparator direction on every graph, while Gui-open and JH contrasts remained unresolved on each graph.

D. SCALE TRANSFER

The ordering advantage transfers to larger instances and alternative generators, but surrogate refinements often produce unresolved routed-CX differences and can reverse under another router.

  • 6.70% fewer routed CX than Default was found at 48 terms, while JSPT OR-Tools again favored comparison with prior-work JW-CEM.
  • Table 5 separates independent routed-CX inference roles and warns that displayed means are rounded while percentages use unrounded canonical values.
  • JSPT, closed support, and Gui-open had statistically unresolved routed-CX contrasts in the heterogeneous-support study at 36 and 48 terms.
  • Closure lowered endpoint charge by 3.10 logical CNOTs and JSPT reduced tree transition by 42.73 edge edits in 59/60 banks, but routed-CX association was weak.
  • Optimization nearly halves logical transition burden in mixed-support instances, but the resulting 46.6% routed-CX contrast remains secondary to the surrogate comparison.

A. RANDOM-ORDER ENVELOPE

Random permutations show substantial routed-CX variation, while structured orders remain consistently better across sampled banks. Equal primary-cost tours also exhibit large downstream depth differences, enabling router-conditioned selection that transfers beyond one generator but depends on the routing heuristic.

  • Random-order envelope: 553.0–946.5 routed CX spans the sampled random rows, with a 125.8 CX mean within-bank range.Six random samples do not establish a population percentile, but they reveal substantial physical variation.
  • Random-order envelope: JSPT OR-Tools and prior-work JW-CEM fell below all six sampled random orders in every bank.Default also beat all six random orders in all 24 banks.
  • Plateau variation: Equal-Hclosed tours showed evaluated routed-depth ranges of 58–83, 61–112, and 74–123 at three 10-term units.Two exhaustive 12-term units spanned 52–109 and 78–129.5; these are evaluated ranges, not upper bounds.
  • Plateau variation: 12.83% opposite-SABRE-seed depth reduction from direct-depth selection occurred in all 20 term-seed aggregates.Both selectors preserved Hclosed exactly, but neither guaranteed routed CX.
  • Transfer: The second generator showed −17.95% depth, −6.91% routed CX, and −15.95% two-qubit depth under direct-depth selection.Every endpoint favored selection across all 20 term-seed aggregates.
  • Transfer: BasicSwap reversed the effect: depth increased 1.82%, routed CX 2.51%, and two-qubit depth 2.08%.The median SABRE–BasicSwap depth association was only 0.093, indicating router-specific candidate rankings.

E. STRICT-VERSUS-ADJACENT-STRATUM CONTROL

Strict selection within the minimum-support stratum outperformed tested adjacent-stratum relaxations and controls, while candidate-budget gains remained measurable through 24 candidates. Separate resynthesis and hardware studies impose important scope and inference boundaries.

  • Strict-versus-adjacent control: At equal K = 24, adjacent-stratum selection worsened aggregate opposite-seed depth and routed CX relative to strict selection.The Hmin + 2 depth comparison was narrowly unresolved after correction, while the Hmin + 4 depth comparison resolved.
  • Strict-versus-adjacent control: Adjacent strata still contained within-stratum diversity: direct selection reduced depth by 14.28% at Hmin + 2 and 15.24% at Hmin + 4.These are descriptive comparisons against each pool’s routing-independent first candidate.
  • Candidate budget: The direct-depth curve reached −12.83% at K = 24, with a 1.21-percentage-point gain from K = 16.The frozen L2 curve reached −11.14%, with an incremental 16-to-24 gain of about 0.45 percentage points.
  • Architecture-aware resynthesis: Restricted LKH-3 averaged 430.2 routed CX versus 543.6 for full-graph PauliOpt ParitySynth, a 20.85% reduction relative to ParitySynth.ParitySynth compiled faster, while routed-depth differences crossed zero and varied by topology.
  • Prospective execution: On ibm_pittsburgh, Stage 2 changed mean generator error by −0.0025 (−0.59%), but the term-seed interval crossed zero.The fixed executed-panel analysis excluded zero, without establishing generalization to new term seeds.
  • Prospective execution: Across 80 executed direction/seed cells, Stage 2 reduced routed depth by 34.3 on average but native two-qubit count by only 0.5.Between-seed variation, rather than shot count alone, limited the population-level conclusion.

C. DIRECT JSPT TEST ON BOSTON

The Boston direct test reduced structural circuit burden relative to Default, but exposure moved oppositely and neither co-primary MAE comparison established a hardware benefit. The endpoint was dominated by near-zero ideal observables, limiting method ranking.

  • Direct test: 9.14% lower scheduled duration accompanied 10.91% lower native CZ count relative to Default, while exposure increased 3.60%.Total depth fell 8.71% and CZ depth 9.20%, so structural burden and calibrated exposure moved in opposite directions.
  • Endpoint resolution: 0.0941 MAE was obtained by the all-zero predictor because 86.5% of ideal expectations had magnitude below 0.25.Every term-seed-level method-minus-zero interval included zero, making the aggregate endpoint low-information for method ranking.
  • Direct test: 0.1018 versus 0.1077 mitigated MAE favored JSPT OR-Tools over Default by 5.44%, but the interval [−0.0155, 0.0028] crossed zero.The OR-Tools versus insertion comparison was effectively null at −0.0001 MAE.
  • Exposure inversion: Exposure had the strongest reported single-proxy association with MAE, at Pearson/Spearman 0.58/0.43.The study explicitly treats exposure as a proxy rather than fidelity, and no scalar fully explains hardware MAE.
  • Exposure inversion: A 40.99% exposure reduction in the offline extension measured selection-snapshot proxy optimization, not cross-snapshot transfer or fidelity.The retained pre/mid/post native-two-qubit calibration tables were identical.
  • Endpoint resolution: Only 14 of 20 term seeds contained qualifying observables at |Eideal| ≥0.25, and the resulting direction reversed against JSPT without resolving.The incomplete coverage prevented replacing the 20-unit primary analysis.

XI. DISCUSSION

The discussion identifies equal-primary-cost ordering as a router-conditioned compiler freedom: it can improve depth under SABRE, but benefits reverse under BasicSwap and do not guarantee hardware gains.

  • Solver benefit and plateau exploitation: 0.910 median candidate-rank correlation across SABRE seeds explains why direct-depth selection transfers across routing re-randomization.Uniform, hash, permuted-score, and matched-restart controls did not reproduce the 36-term effect.
  • Solver benefit and plateau exploitation: Stage 2 depth benefits transferred to a bounded MaxCut generator and 48 terms, but SABRE-selected candidates worsened all three BasicSwap endpoints.The corresponding BasicSwap rank association was only 0.093.
  • Hardware translation is nontrivial: −0.59% raw generator error was observed on the prospective IBM Heron panel, while term-seed inference remained unresolved.The fixed-panel effect exceeded finite-shot uncertainty but did not establish population-level transfer.
  • Scope and limitations: The evidence is bounded by fixed placement, one clean workspace qubit, synthetic generators, one placement and basis, and limited hardware coverage.Exact counts stop at 20 terms, operating-scale widths are lower bounds, and the prospective probe covers one IBM Heron processor.
  • Compiler-design implication: The compiler-design implication is to separate primary transition cost from representative choice and align secondary selection with the downstream router.Strict Stage 2 preserves primary cost exactly and is preferred here because it gives the best absolute result without a primary-cost penalty.

APPENDIX A AUDIT AND PROTOCOL TABLES

The appendix audits protocol provenance, multiplicity, comparison families, and revised analyses, distinguishing registered, revised, exploratory, descriptive, and unresolved claims.

  • Audit structure: Tables 15–18 preserve the compiler-freedom taxonomy, multiplicity audit, protocol reconciliation, and evidence-and-multiplicity map.Table 17 explicitly prevents pooling absolute routed counts across protocols.
  • Multiplicity audit: 13 of 31 formal comparisons survived the original manuscript-wide global Holm correction.Successive frozen revision families expanded the audit to 64 comparisons, with 28 survivors.
  • Engineering comparisons: The revised 36-term JSPT OR versus Default comparison was designated the primary engineering comparison, while JSPT OR versus JW-CEM remained the registered replication.The revised endpoint was post-outcome and therefore a deviation from the pre-specified analysis hierarchy.
  • Cross-comparison status: Additional benchmarks favored OR, whereas JSPT versus JH/Gui routed contrasts and several CX or size-robustness analyses remained unresolved or mixed.The appendix separately labels exploratory, descriptive, and confirmatory families rather than pooling them.
  • Stage 2 validation: The 36-term opposite-routing-seed Stage 2 depth result was favorable in 20/20 aggregates under a new exact three-test Holm family.The corresponding 48-term replication was also favorable in 20/20, while CX remained unresolved.
  • Hardware evidence: The prospective Pittsburgh hardware endpoint had a fixed-panel interval excluding zero, but the result was not a resolved term-seed family inference.Boston and other hardware comparisons likewise retain separate unresolved or fragile statuses.
Loading 2608.27592v1…