A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets

• ChatGPT 5.6 sol helped develop arguments in Sections 4–10 and Appendix B.Source: AI disclosure · p. 1
• The authors verified and wrote the manuscript with the aim of making its proofs accessible.Source: AI disclosure · p. 1
• The authors take full responsibility for the manuscript’s correctness and originality.Source: AI disclosure · p. 1
• The authors are affiliated with the University of Science and Technology of China and the University of Wisconsin–Madison.Source: AI disclosure · p. 1

• Output-probability calculations pair circuit tensors with their conjugates, naturally yielding conjugate-closed Holant signature sets.Source: §1 · p. 4
• Holant grids assign signatures to graph vertices and evaluate a partition function by summing products of local signature values over edge assignments.Source: §1 · p. 4
• The dichotomy extends the real-valued Holant classification with the same four exhaustive tractability conditions, while its hardness proof handles complex signatures and local-unitary transformations.Source: §1 · pp. 4–5
• Conjugate closure lets Holant gadgets realize reduced density matrices, making k-uniformity and entanglement properties applicable to signature classification.Source: §1 · p. 5
• The six-ary obstruction is addressed by deriving third-order orthogonality, identifying an AME(6, 2) state, and reducing signatures to the quantum hexacode’s local-unitary form.Further gadgets and complexity reductions address the fact that the local unitaries in that form need not themselves be available as Holant gadgets.Source: §1 · p. 5
• The work situates its result among prior classifications for symmetric, auxiliary-unary, nonnegative-real, and real-valued Holant signatures.Source: §1 · pp. 5–6

2.1 Definitions and Notations

• A Holant instance is a signature grid whose edge assignments are summed, and the preliminaries define realizability, constraint classes, and conjugate closure.A signature set is conjugate closed when it contains the entrywise conjugate of each of its signatures.Source: §2.1 · p. 7

2.2 Holographic Transformation

• For any invertible T, the bipartite holographic transformation preserves Holant complexity; conjugate closure corresponds to arrow-reversal closure after the K-transformation.The transformation replaces signatures on the two sides by F T^-1 and T G.Source: §2.2 · p. 8

2.3 Signature Factorization

• Every nonzero signature has a unique prime factorization up to variable permutation and nonzero scalar multiples of its factors [CFS20a].Irreducibility and primality are equivalent under the defined signature division relation.Source: §2.3 · p. 9

2.4 Gadget Construction

• 1st-Orth is invariant under conjugation and unitary holographic transformations, and real scalar multiples from each mating gadget imply 1st-Orth.The K-transformation is unitary, so it also preserves 1st-Orth.Source: §2.4 · pp. 10–11
• If a conjugate-closed set contains a nonzero signature outside 1st-Orth and fails condition (T), then its Holant problem is #P-hard.The proof uses a mating gadget to obtain a binary signature with a degenerate matrix, factorizes it into unary signatures, and derives hardness.Source: §2.4 · p. 11

2.5 Tractable Signatures

• The preliminaries define T as tensor products of unary and binary signatures and define affine signatures through affine support and a quadratic phase over Z4.Every affine signature has affine support.Source: §2.5 · p. 12
• For affine signatures, every variable cut has nonzero rows that are orthogonal or proportional, equal nonzero singular values, and power-of-two rank; irreducible signatures of arity at least two satisfy 1st-Orth.These properties are stated for every subset of indices in the cut matrix.Source: §2.5 · pp. 12, 14
• The tractability framework defines product-type, local-affine, and transformable classes, with polynomial-time cases when F ⊆ T or F is P-, A-, or L-transformable [SC20].Product-type signatures are ordinary products of unary, equality, and disequality signatures; local-affine signatures become affine after support-dependent diagonal transformations.Source: §2.5 · pp. 14–15

Dichotomy for Counting Eulerian Orientations

• For finite sets of complex-valued Eulerian-orientation signatures, the cited results state a polynomial-time versus #P-hard dichotomy,, whose alternatives are uniform across each set.The preliminaries also define perfect pairings of variables and associated support restrictions.Source: Dichotomy for Counting Eulerian… · p. 16
• For conjugate-closed signature sets, containment in either half-wave class implies every signature is Eulerian; containment in either quasi-polymorphism class implies affine support.The supplied lemma states these implications for the corresponding up and down classes.Source: Dichotomy for Counting Eulerian… · p. 16

Dichotomy for Holant with an Odd Arity Signature

• An odd-arity signature is single-weighted when its support lies at one Hamming weight, and the preliminaries associate an Eulerian-orientation signature with it.The passages also define restriction to the Eulerian support class elementwise for signature sets.Source: Dichotomy for Holant with an Odd Arity… · pp. 16–17
• For conjugate-closed F containing a nonzero odd-arity signature, failure of condition (T) makes Holant(F) #P-hard.The decomposition lemma also states that if a nonzero signature in F factors as g ⊗ h, then Holant(g, h, F) ≡T Holant(F).Source: Dichotomy for Holant with an Odd Arity… · pp. 17–18

Dichotomy for Quaternary Signatures

• The six-vertex dichotomy identifies a polynomial-time case when each pair (a, x), (b, y), and (c, z) contains a zero, and also lists f ∈⟨M⟩ or f ∈⟨XM⟩ as a last tractable case.The theorem states hardness except for its listed cases; the supplied passage does not show the full list.Source: Dichotomy for Quaternary Signatures · p. 18
• If F fails condition (T), then for every T ∈ GL2(C), #CSP2(T(F ∪ {=2})) is #P-hard.The same subsection cites the single-quaternary-signature dichotomy, whose listed A-transformable and L-transformable cases are polynomial-time computable.Source: Dichotomy for Quaternary Signatures · p. 19

2.7 Signatures and Quantum States

• A signature satisfies k-th order orthogonality when every k-index flattening product MS(f)MS(f)† equals µI2^k for some nonzero µ; this is equivalent to its state being k-uniform.An AME(n, 2) state is ⌊n/2⌋-uniform, and k-th order orthogonality is invariant under conjugation and unitary holographic transformations.Source: §2.7 · p. 20

2.8 Algebra Toolkits

• Conjugation by SU(2) on traceless Hermitian 2×2 matrices induces a 2-to-1 onto map to SO(3), with kernel {I, −I}.The induced map sends U to ΦU(X) = UXU†.Source: §2.8 · p. 21

3 Main Theorem and Proof Outline

• Holant(F) is #P-hard unless the conjugate-closed set F satisfies condition (T), in which case it is tractable.The proof overview identifies establishing hardness outside (T) as the remaining task.Source: §3 · p. 21
• The proof generalizes second-order orthogonality to the conjugate-closed setting, using a new argument that depends on the quaternary-signature dichotomy.Second-order orthogonality remains important throughout the proof.Source: §3 · p. 21
• For a signature outside U⊗, the proof inducts on arity, using first-order orthogonality at arity two and second-order orthogonality plus the nonexistence of AME(4, 2) at arity four.For higher arities, the induction seeks a lower-arity signature still outside U⊗ or proves hardness directly.Source: §3 · p. 21
• At arities six and eight, special signatures defeat the usual merging, mating, and factorization reductions, so each arity needs a separate proof.These signatures are outside U⊗, while the lower-arity signatures obtained by those reductions lie in U⊗.Source: §3 · p. 21
• For arity six, the proof realizes an AME(6, 2) state by classifying possible finite projective binary groups and ruling out some group cases.Realization is shown for polyhedral, large dihedral, and standard Klein cases; non-standard Klein and cyclic cases cannot occur.Source: §3 · pp. 21–22
• After realizing the six-ary state, the proof recovers f6 or proves hardness by analyzing its local unitaries and the resulting projective binary group.The two group cases yield f6 and four Bell signatures; with f6 available, realification handles parity signatures, while a non-parity reduction and minimal-counterexample argument handle the other case.Source: §3 · p. 22
• For arity eight, the proof realizes f8 and proves hardness when F is not contained in A; for arities at least ten, it reduces arity while staying outside U⊗.The arity-eight proof uses a realification argument similar to the arity-six proof.Source: §3 · p. 22

4.1 Unary and Binary Tensor

• If mij f belongs to the unary/binary tensor class, then Holant(F) is #P-hard, f is reducible, or M(mij f) = λijI4 for some λij > 0.The proof handles unary factors and binary tensor products, with the latter yielding reducibility or the scalar identity condition.Source: §4.1 · pp. 23–24

4.2 Affine, Product, Local-affine Transformable

• For an arity-2n signature f (2n≥4), if some pair {i,j} makes mij f irreducible, 1st-Orth, and A-, P-, or L-transformable, rank 2 gives #P-hard Holant(F), while rank 4 gives M(mij f)=λijI4 with λij>0.Source: §4.2 · pp. 25, 28
• When mij f is affine-, product-, or local-affine-transformable, it is either reducible, yields #P-hardness, or has M(mij f) = λijI4 for λij > 0.The result combines the reducible and non-first-order-orthogonal cases with the rank-2 and rank-4 outcomes.Source: §4.2 · p. 28

4.3 Weighted Matching and H Type

• The mating signature bh is invariant under exchanging its two input pairs: bh(a, b, c, d) = bh(c, d, a, b).The subsection introduces this symmetry while ruling out the cases mij f ∈⟨KM⟩ or mij f ∈⟨KXM⟩.Source: §4.3 · p. 28
• If mijf is irreducible, it cannot belong to ⟨KM⟩ or ⟨KXM⟩.Lemma 4.15 establishes this for every pair of indices {i, j}.Source: §4.3 · p. 28
• If mijf belongs to H, then f is reducible, Holant(F) is #P-hard, or M(mijf) = λijf for some λij > 0.Lemma 4.16 gives these alternatives for signatures of arity at least 4.Source: §4.3 · p. 29

4.4 Proof of Second Order Orthogonality

• An irreducible signature of arity at least 4 that fails 2nd-Orth makes Holant(F) #P-hard.This is the main conclusion of Lemma 4.17.Source: §4.4 · p. 29
• The proof applies the arity-4 Holant classification to mijf, excludes ⟨KM⟩ and ⟨KXM⟩, and obtains M(mijf) = λijI4 for transformable cases unless Holant(F) is #P-hard.Lemma 4.2 makes all λij equal; the H and ⟨T⟩ cases follow from Lemmas 4.16 and 4.4, respectively.Source: §4.4 · p. 29

5.1 Base Case

• A binary signature outside U⊗ and a 4-ary signature outside U⊗ each imply that Holant(F) is #P-hard.The binary case follows from first-order orthogonality; the quaternary case also uses the nonexistence of AME(4, 2).Source: §5.1 · pp. 29–30

5.2 Induction Framework

• For arity greater than four, induction seeks a lower-arity signature outside U⊗ or establishes hardness directly.A sequence of reductions reaching a binary signature outside U⊗ completes the hardness argument.Source: §5.2 · p. 30
• If the starting signature is reducible, factorization yields a lower-arity signature outside U⊗ or an odd-arity signature, either of which completes the argument.If it is irreducible, the proof may assume second-order orthogonality and use merging, factorization, and concatenation to generate binary signatures.Source: §5.2 · p. 30
• The projective binary group is generated from binary signatures realized by repeated reduction and concatenation, and it must be finite or hardness follows.In the conjugate-closed setting, the group corresponds to a finite subgroup of SO(3) and can be assumed closed under conjugation and transpose.Source: §5.2 · pp. 30–31

6 Third Order Orthogonality

• An irreducible arity-six signature satisfying second-order orthogonality and the binary-group closure assumption satisfies third-order orthogonality, hence defines an AME(6, 2) state.The proof enumerates the possible finite subgroups of SO(3).Source: §6 · p. 31

6.1 Polyhedral Groups

• For polyhedral projective binary groups, the proof uses Pauli slices and the full matrix span to show that the signature satisfies third-order orthogonality.The groups considered are A4, S4, and A5.Source: §6.1 · pp. 32–33

6.2 Dihedral Groups of Order at Least Six

• For dihedral groups Dn with n ≥ 3, the proof shows that the signature satisfies third-order orthogonality.It uses the Pauli representation and the group’s span on the plane and axis components.Source: §6.2 · p. 34

6.3 Klein Group

• The Klein-group analysis separates the standard and non-standard cases.The proof identifies these as the two cases to consider.Source: §6 · p. 31, §6.3 · p. 34

6.3.1 Standard Case

• In the standard case B(f) ≅ K4, f satisfies 3rd-Orth.The proof realifies f to a real signature and uses transpose symmetry of the reduced density matrix to show the weight-three Pauli coefficients vanish when the indices are distinct.Source: §6.3.1 · pp. 34–35

6.3.2 Non-standard Case

• Under assumption (6), the non-standard case B(f) ≅ K4 cannot occur.Factoring the four contractions forces them to share a common matching; rank and permutation constraints then yield a contradiction.Source: §6.3.2 · pp. 36–38

6.4 Trivial Group

• Under assumption (6), the trivial-group case B(f) ≅ C1 cannot occur.The proof derives a contradiction by showing a common nonzero scalar must equal its negative.Source: §6.4 · p. 39

6.5 Order Two Group

• For B(f) ≅ C2, the subsection gives a normal-form result and shows that exactly one of ∂e12g and ∂b12g is nonzero and they are not proportional under the stated pairing condition.The normal-form result is up to normalization and a real orthogonal holographic transformation.Source: §6.5 · pp. 39–40

6.5.1 Symmetric Case

• The order-two symmetric case B(f) ∼= C2 cannot occur under assumption (6).Lemma 6.18 establishes the contradiction by considering the possible forms of a contraction and comparing further projections.Source: §6.5.1 · pp. 41–42

6.5.2 Asymmetric Case

• The order-two asymmetric case B(f) ∼= C2 also cannot occur under assumption (6).Lemma 6.20 derives a contradiction from the possible contraction forms and the resulting projections.Source: §6.5.2 · p. 42

6.6 Cyclic Group of Order at Least Three

• For cyclic groups of order n ≥ 3, the analysis separates standard and non-standard cases, following the reduction in v1.The standard case has a projective binary group generated by powers of a binary signature; the non-standard case is described using a binary signature and B(bf).Source: §6.6 · p. 43

6.6.1 Standard Case

• In the standard case, contracting any fixed variable pair by any group binary yields a four-variable signature that factors into binary signatures on a common matching independent of the contraction.The common matching is asserted in Lemma 6.21.Source: §6.6.1 · p. 43
• If two standard-case contractions have the same support, every contraction has that support; moreover, every assignment in S(f) has even weight.The support implication is Claim 6.22, and the even-weight property is Lemma 6.26.Source: §6.6.1 · pp. 43–45
• Under assumption (6), the standard case B(f) ≅ Cn for n ≥ 3 cannot occur.The proof derives an incidence-count contradiction: 60 = 15e + 7(m2 + m4) implies e ≡ 4 (mod 7), despite 0 ≤ e ≤ 2.Source: §6.6.1 · p. 46

6.6.2 Non-standard Case

• Under assumption (6), the non-standard case B(f) ≅ Cn for n ≥ 3 cannot occur.The support is restricted to weights 0, 6, or 3; counting unequal bit-pairs then gives 60 = 9m for an integer m, a contradiction.Source: §6.6.2 · pp. 46–47

6.7 Synthesis of All Cases

• The cases are exhaustive: when B(f) is polyhedral, dihedral of order at least six, or the standard Klein group, f satisfies 3rd-Orth; non-standard and cyclic cases cannot happen.Source: §6.7 · p. 47

7 Recovering f6 from Six-Qubit AME(6, 2) Signatures

• The special signature f6 corresponds to an AME(6, 2) state, and the induction and uniqueness argument yields this concrete signature in conjugate-closed Holant, extending the hardness proof from [SC20].The paper relates the obstruction identified in real Holant to the AME(6, 2) state and uses its unique local-unitary normal form.Source: §7 · p. 47
• Either Holant(F) is #P-hard, or a real orthogonal transformation O enables recovery of f6 and the four Bell signatures from Holant(OF).This applies when F is outside condition (T) and contains a nonzero six-ary signature whose normalized state is AME(6, 2).Source: §7 · pp. 47–48

7.1 Binary Contractions and Hardness

• A nonzero contraction of f6 through a binary matrix Q factors into two binary signatures exactly when [Q] belongs to Γ, and then both factors are projectively unitary with classes in Γ.Source: §7.1 · p. 49
• If a realizable nonzero binary signature B has [U_i^T B U_j] outside Γ for any input pair, then Holant(F) is #P-hard.Taking B = I gives hardness whenever [U_i^T U_j] is outside Γ for some pair.Source: §7.1 · p. 50

7.2 A Common Real Orthogonal Transformation

• If every pair satisfies [U_i^T U_j] ∈ Γ, one real orthogonal transformation O makes all O U_i projectively belong to Γ; any realizable nonzero binary signature outside Γ then implies hardness.The common transformation preserves unitarity of the resulting matrices.Source: §7.2 · p. 51

7.3 Recovering f6 from Binary Factors

• The projective binary group G is either Γ or a subgroup of K4; when G = Γ, inverse local factors and all four Bell signatures are available to recover f6.Source: §7.3 · p. 52
• In the K4 case, the contraction-factor restriction is used to show that, after relabeling inputs, h differs from f6 only by Bell matrices.The passage describes obtaining the Bell signatures and removing those matrices as the next steps.Source: §7.3 · p. 52
• Coset-index constraints leave at most eighteen tuples, and tensor identities supply all eighteen, allowing relabeling to express the available signature as g with Bell matrices on its inputs.The identities permute and shift the coset tuples; after relabeling, Bell matrices can be transferred onto the inputs without changing availability.Source: §7.3 · pp. 53–54
• The six contraction-factor classes generate [X] and [Z], so K4 ⊆ G; with G ⊆ K4, this proves G = K4.The first three factor classes sum to (1, 0) and the last three to (0, 1) over F2.Source: §7.3 · p. 55
• With all Bell signatures available, removing the Bell matrices recovers g and then f6; the non-hardness proof reduces the projective binary group to G = Γ or G ⊆ K4.The proof starts from the AME normal form and uses an orthogonal transformation before applying the two group cases.Source: §7.3 · p. 55

8.1 Parity Condition

• If every signature has parity, each is projectively real unless hardness already follows; the real-valued result then gives #P-hardness [SC20].The projective-reality step is proved by induction on arity.Source: §8.1 · pp. 56–57

8.2 Non-parity Condition

• Without parity, arity reduction yields a binary signature with no parity; it lies in Γ unless hardness already follows, and together with B generates Γ.The proof then invokes the hardness result for Holant(Γ, f6, F).Source: §8.2 · pp. 57–59
• For the non-affine case, Pauli-weight reduction and a minimal-arity argument produce an irreducible signature failing 2nd-Orth, which yields #P-hardness.The proof constructs signatures that reduce Pauli-tensor weight, then applies the result for an irreducible signature not satisfying 2nd-Orth.Source: §8.2 · pp. 58–59

8 Hardness When f6 is Available

• Outside condition (T), Holant(f6, B, F) is #P-hard, completing the hardness analysis for the setting with f6 available.The proof combines the parity and non-parity cases.Source: §8.3 · p. 59

8.3 Hardness When f6 is Available

• A 6-ary signature outside U⊗ gives an AME(6,2) state after normalization; realizing f6 then transfers the hardness result back to Holant(F).The proof uses Theorems 6.1 and 7.1 before applying the hardness lemma for f6.Source: §8.3 · p. 59

9 Final Obstacle: f8

• Shao and Cai discovered f8 [SC20], whose membership in U⊗ means simple merging and factorization cannot realize a signature outside U⊗.The section proceeds to realize f8 and then prove #P-hardness when it is available.Source: §9 · p. 60

9.1 Realizing f8 Through the Lens of Reed-Muller Code

• For any f outside U⊗ of even arity at least 8, Lemma 9.2 yields either a realizable lower-arity signature outside U⊗ or a realizable irreducible signature of the same arity with the strong equality property.The lower-arity alternative reduces the induction; the other alternative prepares the arity-8 analysis.Source: §9.1 · p. 60
• For an arity-8 signature h with the strong equality property, all scalars λij in its pairwise merged forms have the same norm; otherwise Holant(F) is #P-hard.The signature h can be assumed to exist after applying Lemma 9.2 or the induction is already completed.Source: §9.1 · p. 65
• Unless Holant(F) is #P-hard, the pair relation ∼ is an equivalence relation and all λij values are equal.The proof also shows that pairs in the same equivalence class have equal λ values.Source: §9.1 · pp. 65–66
• For every arity-8 signature h ∈ F with the strong equality property, either Holant(F) is #P-hard or there exists λ ∈ C× such that ∂ijh = λ·∂ijf8 for every pair of distinct indices {i, j}.Source: §9.1 · p. 67
• For F failing condition (T), an arity-8 signature outside U⊗ is either #P-hard or can be transformed by a real orthogonal matrix to f8 up to nonzero scalar.The proof obtains an arity-8 signature with the strong equality property, then shows it is real-orthogonally equivalent to f8.Source: §9.1 · pp. 70–71

9.2 Hardness When f8 is Available

• If H fails condition (T), contains f8, and its gadget closure contains a nonzero binary signature not projectively in B, then Holant(H) is #P-hard.Source: §9.2 · p. 71
• The final six-ary obstruction yields a signature outside U⊗, which gives hardness by Lemma 8.15.The support-eight factorization forces the relevant binary-factor ratios to be one common sign, placing them in the projective classes of b1 and b3.Source: §9.2 · p. 72
• When F fails condition (T), adjoining all Bell signatures to f8 does not increase hardness beyond Holant(f8, F).The reduction simulates Bell signatures in two steps, using bounded-occurrence oracle reconstruction, and obtains the fourth by connecting two independent Bell signatures as a path.Source: §9.2 · pp. 72–73
• Under the assumption that Holant(f8, F) is not #P-hard, every nonzero parity signature in the closure of B ∪ {f8} ∪ F is projectively real.The induction handles reducible signatures by extracting factors and treats larger irreducible even-arity signatures by comparing contractions to establish a common phase.Source: §9.2 · p. 74
• If F fails condition (T), then Holant(f8, F) is #P-hard.Assuming otherwise, the proof either obtains a non-Bell binary signature or realifies the parity signatures and invokes real Bell-hardness.Source: §9.2 · pp. 74–75
• If F fails condition (T) and contains an arity-8 signature outside U⊗, then Holant(F) is #P-hard.The proof reduces through the real orthogonal transform case and applies the hardness result for Holant(f8, F).Source: §9.2 · p. 75

• No nonzero signature of arity at least 10 can satisfy both 2nd-Orth and the strong equality property.The proof compares residual matchings from two contraction orders; their required coincidence is impossible.Source: §10 · p. 75
• For arity 2n ≥10, Theorem 10.2 gives #P-hardness or a realizable even-arity g outside U⊗ with arity at most 2n −2.Source: §10 · p. 75
• If f is reducible, proper factors are available; an odd-arity factor gives hardness, while an even-arity factor outside U⊗ supplies the lower-arity witness.Source: §10 · p. 76
• For irreducible f, failure of 2nd-Orth gives hardness, while an equality contraction outside U⊗ supplies a witness of arity 2n −2.Source: §10 · p. 76
• When f is irreducible, satisfies 2nd-Orth, and all equality contractions lie in U⊗, Lemma 9.2 yields either the required lower-arity signature or an impossible strong-equality case.At arity at least 10, the strong-equality outcome contradicts Lemma 10.1.Source: §10 · pp. 75–76
• The induction follows the final induction in [SC20, Theorem 9.2], with the complex arity-6 and arity-8 cases supplied by Lemma 8.15 and Theorem 9.21.Source: §10 · p. 76
• The main theorem concludes that Holant(F) is polynomial-time computable under condition (T), and otherwise #P-hard.Source: §10 · p. 76
• The induction starts from arities 2, 4, 6, and 8, and each descent lowers the fixed signature arity by at least two until reaching a base case.Source: §10 · p. 76

• The exposition presents Xia’s framework for classifying Holant(F) problems with unknown complexity by the projective binary group generated by F.Source: A An Exposition of Xia’s Framework… · p. 79
• Theorem 5.5 states that B(f) is a finite subgroup of PU(2), unless Holant(F) is #P-hard.Source: A An Exposition of Xia’s Framework… · p. 79
• The proof establishes finite exponent for B(f) by bounding the algebraic degree of its eigenvalue ratios, contradicting unbounded projective orders.The contradiction uses that the degree of a primitive d-th root of unity is φ(d), which grows without bound as d grows.Source: A An Exposition of Xia’s Framework… · p. 79
• After lifting B(f) to SU(2), the proof applies Burnside’s theorem to conclude that B(f) is finite.Source: A An Exposition of Xia’s Framework… · p. 79
• Because SU(2)/{±I2} is isomorphic to SO(3), the finite groups at issue are cyclic, dihedral, or polyhedral.Source: A An Exposition of Xia’s Framework… · p. 80

B.1 Definitions and Notations; B.2 AME States and Pure Quantum Codes

• A normalized 6-qubit state |ψ⟩ is AME(6, 2) if and only if its one-dimensional span is a pure ((6, 1, 4))2 code.Source: §B.2 · p. 81

B.3 The Standard Four-qubit Code

• Rains shows that every pure ((4, 4, 2))2 code is locally unitary equivalent to the standard [[4, 2, 2]]2 code.Source: §B.3 · p. 83

B.4 Four-qubit Reductions of AME States

• For any pair of qubits A, 4 Tr_A(P) is a rank-4 projector of a pure ((4, 4, 2))2 code, where P is the AME state projector.Source: §B.4 · pp. 83–84
• For each pair A, local unitaries on the other four qubits can make the AME state a simultaneous +1 eigenstate of SX and SZ on those qubits.Source: §B.4 · pp. 84–85

B.5 The Six-qubit Local-Unitary Normal Form

• Every AME(6, 2) state is locally unitary equivalent, up to qubit permutation and a nonzero scalar, to one fixed 6-qubit stabilizer state, the quantum hexacode state.Source: B All AME(6,2) States Have One… · p. 80, §B.5 · p. 85
• In the normal-form proof, the four-qubit reduction yields four rank-one blocks whose vectors form an orthonormal basis of maximally entangled two-qubit states.Source: §B.5 · p. 86
• A common local unitary maps those four vectors to the Bell basis up to phases, giving the fixed local-unitary normal form.Source: §B.5 · pp. 85, 87
• The reduced rank-4 projector has no nonidentity Pauli terms of weights 1, 2, or 3, leaving only identity and weight-4 terms.Its resulting expansion is 1/4 times the identity plus six weight-4 Pauli strings with real coefficients.Source: §B.5 · p. 88
• Projector constraints and a swap of qubits 5 and 6 reduce the weight-4 coefficients to two signed parameters and their product.One coefficient triple can be taken to vanish; the remaining coefficients are ±1/4 and their product divided by 4.Source: §B.5 · p. 89
• The reduced-projector constraints lift to six independent commuting Pauli stabilizers that fix the twice-standardized state.Two additional generators are obtained from the signed coefficients; linear independence of all six is checked through their binary encodings.Source: §B.5 · pp. 89–90
• The common +1 eigenspace of six independent commuting Pauli stabilizers is one-dimensional, so it determines the standardized state up to phase.The projector onto this eigenspace has trace and rank 1.Source: §B.5 · p. 90
• Local Pauli operators correct possible negative stabilizer eigenvalues, yielding the common +1 eigenspace used to define the hexacode state.The sign-corrected state lies in the one-dimensional space spanned by the quantum hexacode state.Source: §B.5 · pp. 90–91
• Every AME(6,2) state is locally unitarily equivalent to the quantum hexacode state, up to qubit permutation and global phase.The proof combines the standardizing local unitaries with a possible swap of qubits 5 and 6 and a final local Pauli operator.Source: §B.5 · p. 91

• The appendix provides deferred proofs of the preliminary lemmas.Source: C Proofs of Some Lemmas in Preliminaries · p. 91

C.1 Proof of Some Lemmas in Section 2.5

• Real orthogonal transformations preserve conjugate closure of a signature set.The proof uses that the transformation matrix is real and applies the same argument to its inverse.Source: §C.1 · p. 91
• Condition (T), including its four alternatives, is invariant under real orthogonal holographic transformations.Orthogonality preserves the binary equality signature, and applying the argument to the inverse gives the converse.Source: §C.1 · pp. 91–92
• For every nonzero signature, irreducibility is preserved under a real orthogonal holographic transformation.Tensor decompositions are preserved in both directions by the transformation and its inverse.Source: §C.1 · pp. 91–92

C.2 Proof of Some Lemmas in Section 2.6

• When F fails condition (T), the associated #CSP2 problem remains #P-hard after every invertible holographic transformation T.The proof starts from the alternatives for a non-hard #CSP2 instance and derives a contradiction with failure of condition (T).Source: §C.2 · pp. 92–93
• Lemma 2.36 gives a polynomial-time versus #P-hard dichotomy for the considered Holant problems.Its proof handles odd-arity signatures, EO signatures, and non-EO signatures in separate cases.Source: §C.2 · p. 93
• When a nonzero odd-arity signature is present, a holographic transformation reduces the problem to a setting covered by the cited dichotomy.The proof invokes Theorem 2.26 together with.Source: §C.2 · p. 93
• When every signature in bF is an EO signature, the problem is treated as a #EO problem and receives a polynomial-time versus #P-hard classification.The cited classification is invoked for #EO(≠4, bF).Source: §C.2 · p. 93
• For a non-EO signature, the proof constructs a signature with nonzero all-zero or all-one entry, then uses gadgets to reach a hardness case.When the construction has arity 2, it is extended to arity 4 before applying the preceding argument.Source: §C.2 · pp. 93–95
• If F does not satisfy condition (T), Lemma 2.37 rules out the polynomial-time cases of Lemma 2.36 and concludes #P-hardness.The proof treats the odd-arity, EO, and non-EO cases separately.Source: §C.2 · p. 95

C.3 Proof of Some Lemmas in Section 2.7

• The proof begins with a nonzero scalar condition for each size-k subset of the signature's variables.This is the stated setup for the kth-Orth property.Source: §C.3 · p. 95
• Conjugating a signature preserves whether it satisfies kth-Orth.The proof uses equality of the corresponding reduced matrices under conjugation.Source: §C.3 · p. 95
• A unitary holographic transformation preserves whether a signature satisfies kth-Orth.The reduced matrix transforms by U on one factor and its transpose on the other; unitarity yields the stated invariance.Source: §C.3 · pp. 95–96