PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Kernel Transfer to Clique Complexes and the Hardness of Normalized Persistence

Cheng Xin

arXiv:2610.00075v1cs.CCcs.CG

TL;DR

Normalized persistence is the persistent Betti rank divided by the initial Betti number, and its complexity on clique complexes remained open despite inverse-polynomial endpoint-gap results for a low-energy relaxation. A finite palette of exactly certified clique gadgets transfers simulated Hamiltonian kernels to geometric Laplacians, while exact fillings identify endpoint homology with quotients whose inclusion maps are natural quotient maps. Estimating q_d to additive error 1/24 with success probability 2/3 is hard for BQP_G2^1, even on nested unweighted clique complexes with β_d(X_in)=8 and inverse-polynomial endpoint gaps.

  • Problem

    Normalized persistence is the persistent Betti rank divided by the initial Betti number, and its complexity on clique complexes remained open despite inverse-polynomial endpoint-gap results for a low-energy relaxation.

    Source: §1 · p. 2

  • Method

    A finite palette of exactly certified clique gadgets transfers simulated Hamiltonian kernels to geometric Laplacians, while exact fillings identify endpoint homology with quotients whose inclusion maps are natural quotient maps.

    Source: §1 · p. 3, §8 · p. 14

  • Results

    Estimating q_d to additive error 1/24 with success probability 2/3 is hard for BQP_G2^1, even on nested unweighted clique complexes with β_d(X_in)=8 and inverse-polynomial endpoint gaps.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For the certified history Hamiltonians, the construction gives exact kernel multiplicity, an inverse-polynomial gap above the full kernel, and persistent ranks without compatible harmonic representatives.

    Source: §8 · p. 14

    The result is gate-dependent: complex phases and general integer states are outside the finite real palette, and the hardness is for endpoint-gap promises whose access assumptions for BQP membership are not established.

    Source: §8 · p. 13

Abstract

from arXiv · show

For clique complexes $X_1\subseteq X_2$, normalized persistence in degree $d$ is $\operatorname{rank}[H_d(X_1)\to H_d(X_2)]/\dim H_d(X_1)$. Estimating it requires exact endpoint homology and the inclusion-induced map, even with inverse-polynomial endpoint Laplacian gaps. We prove that additive-error $1/24$ estimation is hard for $\mathsf{BQP}_{1}^{G_2}$, the perfect-completeness class over the exact gate set $G_2=\{X,\mathsf{CX},\mathsf{CCX},H\otimes H\}$, and hence for $\mathsf{BQP}_{1}$ over every finite gate set with entries in a cyclotomic field $\mathbb{Q}(\zeta_{2^k})$, even for unweighted clique complexes. The main tool is a finite-certificate kernel-transfer theorem. For a fixed palette of weighted clique gadgets satisfying finitely many exactly checkable local conditions, every unit chain $x$ of the full geometric complex satisfies $\operatorname{dist}(x,K)^2\le C(t\lambda^2+\langle x,\Delta x\rangle/(g\lambda^{26}))$, where $K$ is the embedded kernel of the simulated projector Hamiltonian, $g$ its gap, $t$ the number of gadgets, and $\lambda$ the private vertex weight. Since $\lambda$ is chosen independently of $g$, the geometric Laplacian has exactly $\dim K$ zero modes and a gap linear in $g$ above them. Exact fillings identify the endpoint homology with a quotient $V/W_A$ of the register cycle space, and nested term sets induce the natural quotient epimorphisms, so the persistent rank equals the later kernel dimension without any choice of compatible harmonic representatives. A fixed eight-dimensional label register turns a $\mathsf{BQP}_{1}^{G_2}$ verifier into instances with $\beta_d(X_1)=8$ and normalized persistence $3/4$ or $1/8$, and an established common-copy blow-up transfers everything to unweighted graphs.

1 Introduction

The paper addresses the difficulty of realizing exact endpoint kernels and controlling the inclusion-induced map needed for normalized persistence. It proves hardness for exact-gate perfect-completeness verifiers by combining kernel transfer, quotient naturality, and a fixed label register.

Motivation

  • The target statistic is the persistent Betti rank divided by β_d(X_1), interpretable as the fraction of degree-d holes that persist.Earlier work posed its complexity for weighted clique complexes and identified kernel-preserving realization of history Hamiltonians as a missing ingredient.Source: §1 · pp. 1–2

Kernel transfer

  • The transfer theorem controls arbitrary chains of the full geometric complex, including chains concentrated on private gadget vertices, with constants independent of the padded register dimension.Finite certificates use exact filling, zero-weight kernels, private coercivity, and retained private outputs; harmonic padding isolates nonharmonic outside modes with a constant gap.Source: §1 · pp. 2–3

Results

  • The construction realizes history Hamiltonians for exact circuits over G2 and extends hardness to BQP1 for finite gate sets with entries in cyclotomic fields.The exact-circuit simulation result is cited as the basis for the broader class inclusion.Source: §1 · p. 2
  • Estimating q_d to additive error 1/24 with success probability 2/3 on weighted or unweighted clique complexes promised inverse-polynomial endpoint gaps is BQPG2-hard; the reduction maps to nested unweighted complexes with β_d(X_in)=8.Source: §1 · p. 2

Kernel transfer

  • A finite-certificate kernel-transfer theorem realizes exactly dim K geometric zero modes and a gap linear in the simulated Hamiltonian gap g.The palette’s local conditions are exactly checkable, and the private weight λ is chosen independently of g; for the palette used here, the conservative gap bound is Ω(η^28g/t^26).Source: §1 · pp. 2–4

Quotient naturality

  • Exact fillings identify endpoint homology with quotients V/W_A, so nested term sets induce natural quotient maps and persistent rank equals the later kernel dimension.This avoids choosing compatible harmonic representatives, which need not be possible when they rotate across the filtration.Source: §1 · p. 3

Hardness reduction

  • A three-bit mixed label register fixes β_d(X_in)=8 and yields normalized persistence 3/4 or 1/8 from the verifier’s perfect eigenspace dimensions.The common-copy blow-up transfers Betti numbers, persistent rank, and gaps to unweighted graphs.Source: §1 · p. 3

Scope

  • The hardness is gate-dependent and does not establish ordinary BQP-hardness, unrestricted SDQC1-hardness, or gate-independent BQP1-hardness.The certified palette excludes complex phases and general integer states; the common-copy blow-up is polynomial but large.Source: §1 · p. 4

2 Preliminaries and problem statement

The paper defines normalized persistence as the fraction of initial degree-d homology that survives the inclusion into a later complex. Its problem uses weighted clique complexes with endpoint spectral-gap promises and simulates logical cycle spaces using a register and local gadgets.

2 Preliminaries and problem statement

  • Normalized persistence divides the rank of the induced homology map by the initial Betti number, measuring the fraction of initial holes that survive.The denominator is the initial Betti number, not the number of simplices, and the statistic counts exact zero modes rather than eigenvalues below a cutoff.Source: §2 · pp. 4–5
  • The estimation problem takes nested graphs, a common positive dyadic vertex-weight function, degree, inverse-polynomial endpoint gap lower bounds, and accuracy as input.The unweighted problem is the restriction w ≡ 1; its fixed decision version distinguishes normalized persistence at least 3/4 from at most 1/8.Source: §2 · pp. 4–5
  • A join of n bowtie graphs gives a top-dimensional register whose cycle space is isometric to n qubits, with the two petal cycles encoding each basis bit.The register has reduced homology only in degree d = 2n − 1; each local rank-one constraint extends by identity on unaffected factors.Source: §2 · p. 5
  • Weighted clique gadgets attach private vertices to the active register and unaffected factors, while term sets determine the resulting complexes and full degree-d Laplacians.The simulated Hamiltonian acts on the register cycle space, whereas the geometric Laplacian acts on all chains of the enlarged complex.Source: §2 · p. 5

3 Finite-certificate transfer to the complete geometric kernel

A finite set of exact local gadget certificates controls the full geometric chain space, including chains outside the simulated register. The transfer theorem yields exact kernel dimensions and a gap above the complete geometric kernel.

3 Finite-certificate transfer to the complete geometric kernel

  • The theorem applies to every unit chain, and its constants depend on a fixed finite palette rather than growing with circuit dimension.The proof combines leakage control and exact fillings with the logical gap; projection onto the logical kernel bounds low-energy dimension, while fillings supply zero modes.Source: §3 · p. 6, §3.2 · pp. 7–8

3.1 The certificate model

  • Each palette gadget is certified through exact boundary filling, a zero-weight kernel decomposition, private-space coercivity, and retained outputs containing a private vertex.The certificate data use finite integer or rational linear algebra; exact fillings and rank checks establish the boundary-intersection condition.Source: §3.1 · p. 6
  • Harmonic padding tensors local private data with outside-register harmonics and places nonharmonic outside modes in a separately gapped sector.The outside register has reduced homology only in its top degree, and its other modes have a constant positive gap.Source: §3.1 · pp. 6–7

3.2 Global theorem

  • The global theorem requires a common private weight small relative to the maximum number of gadgets and uses the exact local certificates to control the full complex.Its conclusion specifies equal logical and geometric kernel dimensions and no spectrum in the positive interval below E_A.Source: §3.2 · p. 7
  • The finite-certificate theorem gives exact geometric kernel multiplicity and excludes positive Laplacian eigenvalues below the stated threshold.This also covers a zero logical kernel, when the geometric Laplacian is bounded below by the threshold.Source: §3.2 · pp. 7–8
  • For the explicit history palette, the conservative exponent is not claimed to be optimal.The palette has m ≤ 6, giving κ = 26 in the stated parameterization.Source: §3.2 · p. 8

4 Filtered quotient naturality

Exact fillings identify endpoint homology with a quotient of the fixed register cycle space. Under inclusion, those quotient identifications commute with natural quotient maps, so persistence needs no compatible choice of harmonic representatives.

4 Filtered quotient naturality

  • The spectral transfer theorem rules out extra geometric classes, while quotient maps compute persistence without comparing harmonic representatives.Those representatives may rotate between filtration levels; the exact statement concerns algebraic homology maps.Source: §4 · pp. 8–9
  • For each term set, the boundary classes killed by fillings are exactly the sum of the ranges of its logical projectors.Independent private supports let a boundary with no private coordinates be checked separately gadget by gadget.Source: §4 · p. 8
  • Exact fillings identify each endpoint homology with a quotient of the register cycle space, and inclusions induce the natural quotient maps.The quotient diagrams commute, and every map along a chain of term sets is an epimorphism in degree d.Source: §4 · pp. 8–9

5 Exact histories, a fixed clique palette, and hardness

The construction uses exact histories and a fixed certified clique-gadget palette to turn perfect-space dimensions into normalized-persistence instances. A fixed-eight label yields separated persistence values, with inverse-polynomial endpoint gaps.

5.1 Rational histories and the certified palette

  • Every local constraint in the split G2 history uses a member of one fixed weighted clique-gadget family with support locality at most six and uniform certificates.The graph construction is polynomial in circuit size; clock, input, and output penalties are basis projectors, and unaffected work qubits use harmonic padding.Source: §5.1 · p. 9

5.2 Complete history kernels

  • The history construction gives complete initial and final kernels corresponding respectively to the clean-input space and the perfect accepting space, with inverse-polynomial logical gaps.When the acceptance operator off the perfect space is at most 1/3, the stated gaps are at least 1/(8L^2) initially and 1/(27L^3) finally.Source: §5.2 · p. 10

5.3 A fixed-eight source

  • A maximally mixed three-bit label compresses acceptance to a space with perfect eigenspace dimension six when px = 1 and one when px ≤ 1/3.In the latter case every off-perfect eigenvalue is at most 1/3.Source: §5.3 · p. 10
  • The fixed-eight reduction has β_d(Xin) = 8 and normalized values 3/4 or 1/8, distinguished with additive error 1/24 and threshold 7/16.Both endpoint degree-d Laplacians have inverse-polynomial gaps above their complete kernels.Source: §5.3 · p. 10
  • The hardness statement extends separately to finite gate sets with entries in cyclotomic fields, but remains gate-family-relative rather than gate-independent.The passage names Clifford+T as an example of such a gate set.Source: §5.3 · p. 11

6 A natural unweighted corollary

A common-copy blow-up turns the weighted construction into unweighted clique complexes while preserving endpoint Betti numbers, persistent rank, gaps, and normalized values. Using identical labeled copy blocks at both levels makes the symmetric copy maps commute with inclusion.

6 A natural unweighted corollary

  • The weighted construction uses weights 1 and a dyadic inverse-polynomial λ, with register vertices receiving F copies and private vertices one copy.The common-copy size is F = λ^-2; since F is polynomial, the blown-up graph is polynomial in size.Source: §6 · pp. 11–12
  • The unweighted corollary preserves endpoint Betti numbers, persistent rank, inverse-polynomial endpoint gaps, and normalized values 3/4 and 1/8.The transfer uses the common-copy blow-up.Source: §6 · p. 11
  • The symmetric/asymmetric decomposition preserves endpoint nullities and induced ranks, while the asymmetric bound excludes asymmetric harmonic vectors.There is no extra normalization factor because inclusion preserves simplex degree, weights, labels, and copy set.Source: §6 · pp. 11–12
  • Using the same labeled copy blocks at both levels makes the symmetric isometries commute with inclusion, preserving the inclusion-induced maps.The construction relies on Hayakawa’s operator decomposition; the filtration-specific step is the commuting identity.Source: §6 · pp. 11–12

7 Relation to prior work

The paper places its result alongside prior work on normalized persistence, clique homology gadgets, and persistence hardness. It establishes kernel fidelity, gaps, and functoriality for exact G2 history Hamiltonians, while distinguishing its scope and proof techniques from earlier results.

Relation to normalized persistence

  • Theorems 3.3 and 4.2 establish kernel fidelity with computable gaps and functoriality for exact G2 history Hamiltonians, but do not establish Lowe et al.’s Conjecture 1.The construction uses a three-mixed-label-qubit source rather than an SDQC1 verifier, and its certified palette is real and exact.Source: §7 · p. 12

Clique homology gadgets

  • Earlier clique-gadget work established exact hole multiplicities or gapped homology under positive-definite Hamiltonians; this transfer theorem handles degenerate kernels and decouples λ from g.The paper attributes the earlier results to Crichigno and Kohler, King and Kohler, and Hayakawa.Source: §7 · p. 12
  • The padding proof keeps local private coordinates tensored with outside harmonics in every bidegree, a proof-technique difference from the coordinate-bulk formulation discussed for [14].The authors make no claim about the presentation in the published version.Source: §7 · p. 13

Persistence hardness

  • Unlike representative-survival hardness [9], normalized persistence measures the fraction of all initial homology that survives, requiring control of both endpoint kernels.The paper uses ordinary endpoint Laplacians for the promise and a quotient model for the map.Source: §7 · p. 13

Unweighting

  • The unweighting step uses Hayakawa’s symmetric/asymmetric decomposition [11]; the paper’s addition is that identical labeled copy blocks make the symmetric isometries commute with inclusion.The authors do not count unweighting as a separate contribution.Source: §7 · p. 13

8 Limitations and open problems

The construction has a finite, real certified palette and yields gate-dependent hardness with a constant initial Betti number. The paper identifies open steps toward broader hardness and BQP containment.

Limitations

  • The exact finite palette excludes arbitrary integer states and complex phases, so the hardness source is BQP1^G2 rather than ordinary BQP, unrestricted SDQC1, or a gate-independent class.The initial Betti number is 8; the gap is a complexity promise, and the common-copy blow-up is polynomial but large.Source: §8 · p. 13

Open problems

  • A stronger hardness result would require a source whose perfect-space fraction is separated by the SDQC1 trace promise and a certified palette for that gate set.The paper poses SDQC1-hardness of normalized harmonic persistence as an open question, as conjectured in.Source: §8 · p. 13
  • BQP containment remains unestablished because the required inverse-polynomial principal-angle bound and efficient preparation of the initial harmonic mixture are not shown.The paper states that establishing both would place the instances in BQP by [19, Lemma 7].Source: §8 · p. 13

Conclusion

  • The paper’s reusable criterion certifies exact kernel multiplicity, an inverse-polynomial gap above the whole kernel, and natural persistent ranks from finite local conditions.The conditions include local zero-weight kernels, private coercivity, exact filling, and interfaces, without a growing-dimensional perturbation argument.Source: §8 · p. 14

A Proof of the all-chain transfer theorem

The appendix derives the all-chain transfer theorem from finite local hypotheses whose constants depend only on the fixed palette. Its proof combines local scaling and padding with global coercivity to establish exact kernel multiplicity and a gap above the full kernel.

A Proof of the all-chain transfer theorem

A.1 Local scaling and harmonic padding

  • Local scaling bounds the weighted boundary using the least nonzero singular value, while harmonic padding places nonharmonic outside modes above a constant floor.At the target degree, the only outside-harmonic bidegree is the active target degree tensored with outside harmonics; the padded positive spectrum is bounded below by c′λ^κ.Source: §A.1 · p. 16

A.2 Global decomposition and interface energy

  • The global decomposition separates register and gadget-private coordinates, tracking shared-register boundary terms to control the full chain’s energy.The proof also uses a constant positive spectral floor for the register boundary operator off its kernel.Source: §A.2 · p. 17

A.3 Zero-weight and private-sector coercivity

  • Zero-weight kernel decomposition and first-order private-sector coercivity control distance from the register subspace across the padded gadgets.The argument sums orthogonal decompositions into the register subspace, private subspaces, and their complements.Source: §A.3 · pp. 17–18

A.4 Logical coercivity

  • Exact filling places each logical projector range inside the gadget boundary space, allowing the local up-Laplacians to bound logical energy.Because private simplices belong to exactly one gadget and the register has no up-columns, the global up-Laplacian is the exact sum of embedded local up-Laplacians.Source: §A.4 · p. 18

A.5 Exact multiplicity and the whole-positive-spectrum gap

  • An energy threshold makes projection onto the simulated kernel injective on low-energy vectors; quotient homology supplies at least dim K geometric zero modes, forcing exact multiplicity and no smaller positive eigenvalue.The argument also covers K = 0 without an additional global relative-acyclicity assumption.Source: §A.5 · pp. 18–19

A.6 Proof of quotient naturality

The appendix proves that nested term sets induce commuting quotient epimorphisms, then develops history-kernel estimates and an eight-label compression used in the source construction. It also delineates the source interface and a real-gate extension that does not cover complex phases.

A.6 Proof of quotient naturality

  • For A ⊆ B, the quotient map sends each register cycle class to the same cycle in X_B and is onto with rank dim(V/W_B) = dim K_B.The proof establishes q_A is well-defined and injective, then uses the domain dimension and Hodge theory to obtain surjectivity.Source: §A.6 · p. 19

B.1 Rational gain/loss split

  • The clock-bit and work-bit gain/loss relations yield H ⊗ H when applied to the two work bits.The vectors in each pair are orthonormal.Source: §B.1 · p. 19

B.2 Weighted path estimate

  • N(ξ) ≤ 8L^2E(ξ) on the orthogonal complement of the complete initial kernel.The estimate follows after treating legal and illegal unary-clock sectors; the diagonal clock term gives illegal strings energy at least one.Source: §B.2 · pp. 19–20

B.3 Adding the output projector

  • Adding the output rejection projector preserves the common kernel S and yields a positive spectral bound under the stated gap and overlap conditions.For the history Hamiltonian, the text gives g = 1/(8L^2) and α ≥ 1/(3L) when r ≤ 1/3.Source: §B.3 · p. 20

B.4 Exact eight-label compression

  • The eight-label compression gives normalized trace 3/4 when p_x = 1 and at most 1/3 when p_x ≤ 1/3, while the perfect-space fractions are 3/4 and 1/8.Acceptance acts as identity on one label, as p_x on five labels, and as zero on two labels.Source: §B.4 · p. 21

B.5 Source-interface boundary

  • The source is a fixed-input BQP_1^G2 verifier with three added mixed label bits, giving initial history dimension eight; the real-gate extension does not cover complex phases.The extension preserves the fraction and off-perfect ceiling while doubling both input and perfect-eigenspace dimensions.Source: §B.5 · p. 21

C Finite palette and guard certificates

The finite palette is supported by exact graph, filling, kernel, and rank certificates rather than numerical eigenvalue thresholds. Selected-cycle guards extend these constructions while preserving exact filling and a fixed positive guard gap outside the target kernel.

C Finite palette and guard certificates

  • The palette uses four explicit active-graph constructors, with archived graph, filling, kernel-basis, modular-rank, and Gram-determinant certificates.The finite checks do not rely on a numerical eigenvalue threshold.Source: C Finite palette and guard certificates · p. 21
  • For the one-qubit atom, the exact boundary ranks are 15 and 24, the Betti numbers are (1, 1, 0), and a denominator-one 24-term two-chain fills the target cycle.The passage also reports a zero-weight target differential-pair rank of 30.Source: C Finite palette and guard certificates · p. 21
  • For |00⟩−|11⟩, the Betti numbers are (1, 0, 0, 3, 0), and a denominator-one 248-term four-chain fills the target.Swapping the second bowtie petals transports the certificate to |01⟩−|10⟩.Source: C Finite palette and guard certificates · p. 22
  • The three-term representative has degree-three Betti number three, a denominator-one 382-term filling, and three complementary register cycles independent modulo boundaries.Signed bowtie-petal permutations transport the graph, filling, kernel, and private pair to the other three gain/loss vectors.Source: C Finite palette and guard certificates · p. 22

C.1 Selected-cycle guards

  • Joining a gadget to a selected bowtie petal tensors the old exact boundary intersection with that petal cycle, adds no killed register class, and leaves other bidegrees with a fixed positive guard gap.The basis projector is a special case, completing the stated proof of theorem 5.1.Source: §C.1 · pp. 22–23

C.2 Reproducibility boundary

The archive’s checkers recompute finite certificate claims, while the paper assigns the analytic implication to theorem 3.3. The authors disclose using ChatGPT and Claude as auxiliary tools and retain responsibility for the submission.

C.2 Reproducibility boundary

  • The archive checkers recompute ranks, fillings, relabelings, and guard identities; the analytic implication from those finite checks is theorem 3.3.The archive lists separate certificates for the representative bulk, remaining active atoms, Hadamard orbit, and selected-cycle guards.Source: §C.2 · p. 23

AI Disclosure

  • ChatGPT and Claude assisted with literature search, brainstorming, proof checking, and exposition drafting and editing; the authors evaluated and revised the material and take responsibility for correctness and originality.Source: AI Disclosure · p. 23
Loading 2610.00075v1…