Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Equivalence of bipartite encoder forms

Abstract

For graphs with only input–output edges, equivalence generated by local complementation, the two vertex permutations, binary input-row addition and input-edge removal implies reachability by the two permutations and row additions alone.

Definition 1.1 (The three operations on bipartite forms).

Formalization. D5/S3/Quantum/Codes/KhesinLiBipartiteEncoderEquivalence.BipartiteStep (✓ std3).

Citation. Andrey Boris Khesin, Alexander M. Li (2024). Equivalence Classes of Quantum Error-Correcting Codes. DOI: 10.48550/arXiv.2406.12083. URL: https://arxiv.org/abs/2406.12083v1.

Commentary.

BipartiteStep relates G to an output permutation, an input permutation, or the addition of input row j to a distinct input row i over ZMod 2. These are operations 2–4 of Conjecture 6.3 (arXiv:2406.12083v1, main.tex, lines 1226–1237); line 1247 specifies addition modulo two. The embedding in each graph map is explicitly coerced to a function. The row addition is D5/S3/Quantum/Codes/KhesinLiEquivalenceClasses.addInputRow. The relation is defined on all graphs on Fin k ⊕ Fin n; bipartiteness is imposed on the endpoints in the next statement.

Definition 1.2 (The bipartite-form conjecture for operation-generated equivalence).

Formalization. D5/S3/Quantum/Codes/KhesinLiBipartiteEncoderEquivalence.claim (✓ std3).

Source. Repository-derived.

Acknowledgement. Andrey Boris Khesin, Alexander M. Li (2024). Equivalence Classes of Quantum Error-Correcting Codes. DOI: 10.48550/arXiv.2406.12083. URL: https://arxiv.org/abs/2406.12083v1.

Commentary.

Conjecture 8.3 (arXiv:2406.12083v1, main.tex, lines 1768–1771) asks whether all bipartite forms in one equivalence class are related by output permutations, input permutations and row operations. Here the equivalence is the equivalence closure of D5/S3/Quantum/Codes/KhesinLiEquivalenceClasses.Step, comprising operations 1–5 on graphs without local Clifford decorations. Section 7 constructs classes from these operations (main.tex, lines 1557 and 1582–1584). Both endpoint graphs have only input–output edges: the left and right vertex predicates explicitly compare Sum.isLeft and Sum.isRight to Bool.true. The conclusion is a finite, possibly empty, sequence of BipartiteStep operations. There is no positivity, connectedness, rank or normalization hypothesis. This is a statement about the operation-generated classes; it does not identify them with the quantum-code equivalence of Definition 6.2 or establish Conjecture 6.3.

Theorem 1.3 (Output cut ranks determine the bipartite row space).

Proof. Machine-checked in Lean as D5/S3/Quantum/Codes/KhesinLiBipartiteEncoderEquivalence.result (✓ std3). ∎

Resolves. Problems/khesin-li-2024-bipartite-encoder-equivalence (proved) by D5/S3/Quantum/Codes/KhesinLiBipartiteEncoderEquivalence.result.

Source. Repository-derived.

Acknowledgement. Andrey Boris Khesin, Alexander M. Li (2024). Equivalence Classes of Quantum Error-Correcting Codes. DOI: 10.48550/arXiv.2406.12083. URL: https://arxiv.org/abs/2406.12083v1.

Commentary.

For a graph G, form its k by n input–output adjacency matrix B over ZMod 2 by restricting D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.cut to the input vertices and output vertices. The cut rank of an output subset is D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.entropy. Output permutation transports this profile by the inverse permutation, by D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.relabel. Adding input row j to row i preserves both same-side adjacency blocks and replaces cross-row i by its binary sum with cross-row j. It preserves bipartiteness and left-multiplies B by the elementary transvection with entry one at i,j. For bipartite graphs the cross block determines every edge, so equality of these matrices implies equality of graphs.

For an output subset S, neither input i nor input j belongs to its image A in the full vertex set. Writing cᵢ and cⱼ for these inputs as vertices outside A, the cut matrix after D5/S3/Quantum/Codes/KhesinLiEquivalenceClasses.addInputRow is cut(G,A) multiplied on the right by the transvection with row cⱼ, column cᵢ and coefficient one. Distinctness of i and j gives determinant one, so the cut rank is unchanged.

The local-complementation operation in Step agrees with D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.lc by D5/S3/Quantum/Codes/KhesinLiEquivalenceClasses.lc_source. Its cut ranks are invariant by D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.lc_eq; complementary cuts have equal rank by D5/S3/Quantum/Entanglement/GraphStateMonogamyForbiddenSubgraph.compl_eq. Input permutations reindex the complementary columns by relabel. Row additions preserve rank by the transvection calculation, and input-edge removal changes no entry of an output cut. Thus each Step preserves the output profile up to an output permutation. Induction over the equivalence closure handles reversal by the inverse permutation and composition by composition of permutations. Consequently there is an output permutation σ such that J, the corresponding output relabelling of G, has the same output cut ranks as H; J is still bipartite.

For any bipartite graph with input–output matrix B and any output subset S, reindex the cut rows by S. Its input columns are precisely the columns of the transpose of B restricted to S; its remaining output columns are zero. The column spans therefore agree, and invariance of rank under transpose identifies the cut rank with the rank of the column restriction B_S. Extending a vector on S by zero gives a bijection from the kernel of B_S to the vectors u in the kernel of B with support contained in S. Rank-nullity and the cardinality of a binary vector space give exactly 2^(|S| − rank(B_S)) such vectors.

For two binary matrices B and C with equal supported-kernel counts, let b(T) be the indicator vector of a subset T. Every binary vector is uniquely b(T), with support T. The supported-kernel count on S is therefore the sum over T contained in S of the indicator that B b(T) = 0. Cast these natural-number sums to the reals and apply D5/S3/Quantum/Information/EvenLeggedHyperlinkReconstruction.hyperlink and its subset-sum inverse D5/S3/Quantum/Information/EvenLeggedHyperlinkReconstruction.hyperlink_zeta. The indicators agree for each T, so B and C have the same kernel.

The coordinate pairing Module.piEquiv identifies a vector u in the matrix kernel with a functional annihilating every row. Hence equality of kernels implies equality of row-space dual annihilators, and injectivity of the dual annihilator gives equality of row spaces. The quotients by the common kernel identify the two matrix ranges. Extend that range isomorphism to a linear automorphism t of the full input-coordinate space. Its invertible matrix R satisfies C = R B, as is seen by applying both matrices to every vector.

Induct on an invertible binary matrix R using diagonal matrices, elementary transvections and multiplication. An invertible diagonal binary matrix has every diagonal entry equal to one, so it needs no operation. A transvection has coefficient zero or one: zero again needs no operation, while one is the addition of its distinct input rows. For a product, perform the operations for the right factor and then those for the left factor. Every intermediate graph is bipartite and its cross block is the required matrix product. Equality of the final cross block with that of the target graph identifies the two graphs.

Apply this to J and H. Their equal output cut ranks give equal ranks for every restricted input–output matrix, hence equal supported-kernel counts, equal kernels and equal row spaces. Choose R with the input–output matrix of H equal to R times that of J, and realize R by the finite row-addition sequence just described. Prepending the output permutation from G to J gives the asserted finite BipartiteStep sequence from G to H.

References