45 Def 13: Bivariate Bicycle Code
A Bivariate Bicycle (BB) code is a CSS code built from two polynomials over a product of cyclic groups. Let \(\ell , m\) be positive integers. The code is defined using cyclic shift operators \(x = C_\ell \otimes I_m\) and \(y = I_\ell \otimes C_m\) acting on \(\mathbb {F}_2^{\ell m}\), where \(C_r\) denotes the \(r \times r\) cyclic permutation matrix. Given polynomials \(A, B \in \mathbb {F}_2[x, y]\), the parity check matrices are \(H_X = [A \mid B]\) and \(H_Z = [B^\top \mid A^\top ]\), where \(A^\top = A(x^{-1}, y^{-1})\).
The monomial set is defined as
This is an additive abelian group where addition represents multiplication of monomials.
The group algebra \(\mathbb {F}_2[x, y]/(x^\ell - 1, y^m - 1)\) is defined as
i.e., the set of finitely-supported functions \(M \to \mathbb {F}_2\) with convolution multiplication.
The generator \(x = C_\ell \otimes I_m\) as an element of the group algebra is defined as the single monomial supported at \((1, 0) \in M\) with coefficient \(1\):
The generator \(y = I_\ell \otimes C_m\) as an element of the group algebra is defined as the single monomial supported at \((0, 1) \in M\) with coefficient \(1\):
A monomial \(x^a y^b\) is represented as the group algebra element \(\delta _{(a,b)} \in \mathbb {F}_2[M]\), i.e., the finitely-supported function that is \(1\) at \((a,b)\) and \(0\) elsewhere.
The transpose operation on monomials maps \((a, b) \mapsto (-a, -b)\) in \(M\). This corresponds to the substitution \(x \mapsto x^{-1}\), \(y \mapsto y^{-1}\).
For all \(a \in \mathbb {Z}/\ell \mathbb {Z}\) and \(b \in \mathbb {Z}/m\mathbb {Z}\),
This holds by reflexivity, directly from the definition of \(\mathrm{transposeMonomial}\).
The transpose monomial operation is involutive: for all \((a, b) \in M\),
Let \((a, b) \in M\) be arbitrary. By the definition of \(\mathrm{transposeMonomial}\) and the fact that \(-(-a) = a\) and \(-(-b) = b\) (double negation in \(\mathbb {Z}/\ell \mathbb {Z}\) and \(\mathbb {Z}/m\mathbb {Z}\) respectively), we obtain \(\mathrm{transposeMonomial}(-a, -b) = (a, b)\).
The transpose monomial operation is injective.
This follows directly from the fact that \(\mathrm{transposeMonomial}\) is involutive, and any involutive function is injective.
The transpose of a group algebra element \(p \in \mathbb {F}_2[M]\) is defined as \(p^\top = p(x^{-1}, y^{-1})\), computed by applying the monomial transpose to the domain:
This maps each monomial \((a, b)\) to \((-a, -b)\) while preserving coefficients.
The algebraic transpose operation is involutive: for all \(p \in \mathbb {F}_2[M]\),
Let \(p \in \mathbb {F}_2[M]\). By the definition of \(\mathrm{transposeAlg}\), \((p^\top )^\top = \mathrm{mapDomain}(\mathrm{transposeMonomial}, \mathrm{mapDomain}(\mathrm{transposeMonomial}, p))\). Rewriting via the composition law for \(\mathrm{mapDomain}\), this equals \(\mathrm{mapDomain}(\mathrm{transposeMonomial} \circ \mathrm{transposeMonomial}, p)\). Since \(\mathrm{transposeMonomial}\) is involutive, \(\mathrm{transposeMonomial} \circ \mathrm{transposeMonomial} = \mathrm{id}\). Applying \(\mathrm{mapDomain}(\mathrm{id}, p) = p\) completes the proof.
The matrix representation of a group algebra element \(p \in \mathbb {F}_2[M]\) is the \(|M| \times |M|\) matrix over \(\mathbb {F}_2\) whose \((\alpha , \beta )\)-entry is \(p(\alpha - \beta )\):
This gives a circulant-like structure on the product group.
For any \(p \in \mathbb {F}_2[M]\),
By extensionality, it suffices to show equality for arbitrary \(\alpha , \beta \in M\). By the definition of matrix transpose, the \((\alpha , \beta )\)-entry of \(\mathrm{toMatrix}(p)^\top \) equals the \((\beta , \alpha )\)-entry of \(\mathrm{toMatrix}(p)\), which is \(p(\beta - \alpha )\). We observe that \(\alpha - \beta = \mathrm{transposeMonomial}(\beta - \alpha )\) since negation reverses the subtraction. Rewriting \(p(\beta - \alpha )\) using the \(\mathrm{mapDomain}\) definition of \(\mathrm{transposeAlg}\) with injectivity of \(\mathrm{transposeMonomial}\), we obtain \(p^\top (\alpha - \beta )\), which is the \((\alpha , \beta )\)-entry of \(\mathrm{toMatrix}(p^\top )\).
The four label types for checks and qubits of a BB code are:
\(X\): X-type check
\(Z\): Z-type check
\(L\): Left qubit
\(R\): Right qubit
A labeled element is a pair \((\alpha , T)\) where \(\alpha \in M\) is a monomial and \(T \in \{ X, Z, L, R\} \) is a label type. X checks, Z checks, left qubits, and right qubits are each in one-to-one correspondence with elements of \(M\).
A Bivariate Bicycle (BB) code with parameters \(\ell , m\) is specified by two polynomials \(A, B \in \mathbb {F}_2[M]\). The structure consists of:
\(\mathrm{polyA} : \mathbb {F}_2[M]\) — the first polynomial \(A\),
\(\mathrm{polyB} : \mathbb {F}_2[M]\) — the second polynomial \(B\).
The number of physical qubits is \(n = 2\ell m\).
The number of left qubits is \(\ell m\).
The number of right qubits is \(\ell m\).
The total number of physical qubits equals the sum of left and right qubits:
Unfolding the definitions of \(\mathrm{numPhysicalQubits}\), \(\mathrm{numLeftQubits}\), and \(\mathrm{numRightQubits}\), this reduces to \(2\ell m = \ell m + \ell m\), which follows by ring arithmetic.
The number of X-type stabilizer checks is \(\ell m\).
The number of Z-type stabilizer checks is \(\ell m\).
The matrix representation of polynomial \(A\), defined as \(\mathrm{toMatrix}(A)\), where the \((\alpha , \beta )\)-entry is \(A(\alpha - \beta )\).
The matrix representation of polynomial \(B\), defined as \(\mathrm{toMatrix}(B)\), where the \((\alpha , \beta )\)-entry is \(B(\alpha - \beta )\).
The matrix representation of \(A^\top = A(x^{-1}, y^{-1})\), defined as \(\mathrm{toMatrix}(\mathrm{transposeAlg}(A))\).
The matrix representation of \(B^\top = B(x^{-1}, y^{-1})\), defined as \(\mathrm{toMatrix}(\mathrm{transposeAlg}(B))\).
The matrix \(\mathrm{matAT}\) equals the matrix transpose of \(\mathrm{matA}\):
By simplification using the definitions of \(\mathrm{matAT}\), \(\mathrm{matA}\), and the theorem \(\mathrm{toMatrix\_ transpose}\), the result follows directly.
The matrix \(\mathrm{matBT}\) equals the matrix transpose of \(\mathrm{matB}\):
By simplification using the definitions of \(\mathrm{matBT}\), \(\mathrm{matB}\), and the theorem \(\mathrm{toMatrix\_ transpose}\), the result follows directly.
The X parity check matrix is
an \(\ell m \times 2\ell m\) matrix over \(\mathbb {F}_2\) with rows indexed by \(M\) (X checks) and columns indexed by \(M \oplus M\) (left \(\oplus \) right qubits), formed by horizontally concatenating the matrix representations of \(A\) and \(B\).
The Z parity check matrix is
an \(\ell m \times 2\ell m\) matrix over \(\mathbb {F}_2\) with rows indexed by \(M\) (Z checks) and columns indexed by \(M \oplus M\) (left \(\oplus \) right qubits), formed by horizontally concatenating the matrix representations of \(B^\top \) and \(A^\top \).
The CSS orthogonality condition states that
over \(\mathbb {F}_2\). This ensures that the X and Z stabilizers commute, which is necessary for the code to be a valid CSS code.
An X-type Pauli operator \(X(p, q)\) is specified by two polynomials:
\(\mathrm{leftPoly} \in \mathbb {F}_2[M]\): the pattern on left qubits,
\(\mathrm{rightPoly} \in \mathbb {F}_2[M]\): the pattern on right qubits.
A Z-type Pauli operator \(Z(p, q)\) is specified by two polynomials:
\(\mathrm{leftPoly} \in \mathbb {F}_2[M]\): the pattern on left qubits,
\(\mathrm{rightPoly} \in \mathbb {F}_2[M]\): the pattern on right qubits.
The support of a Pauli operator \(X(p, q)\) as a binary vector over \(M \oplus M\) (left \(\oplus \) right qubits) is defined as:
The support of a Pauli operator \(Z(p, q)\) as a binary vector over \(M \oplus M\) (left \(\oplus \) right qubits) is defined as:
In the group algebra, \(x^\ell = 1\). More precisely, the monomial \((\ell , 0)\) equals the monomial \((0, 0)\) (the identity):
By simplification using the definition of \(\mathrm{monomial}\) and the fact that \(\ell \equiv 0 \pmod{\ell }\) (i.e., \(\mathrm{ZMod.natCast\_ self}\)), the two monomials are equal.
In the group algebra, \(y^m = 1\). More precisely, the monomial \((0, m)\) equals the monomial \((0, 0)\) (the identity):
By simplification using the definition of \(\mathrm{monomial}\) and the fact that \(m \equiv 0 \pmod{m}\) (i.e., \(\mathrm{ZMod.natCast\_ self}\)), the two monomials are equal.
The cyclic permutation on \(\mathbb {Z}/r\mathbb {Z}\) is the bijection \(i \mapsto i + 1\) with inverse \(i \mapsto i - 1\).
The generator \(x\) as a permutation on \(M = \mathbb {Z}/\ell \mathbb {Z} \times \mathbb {Z}/m\mathbb {Z}\) is defined by \((a, b) \mapsto (a + 1, b)\), with inverse \((a, b) \mapsto (a - 1, b)\).
The generator \(y\) as a permutation on \(M = \mathbb {Z}/\ell \mathbb {Z} \times \mathbb {Z}/m\mathbb {Z}\) is defined by \((a, b) \mapsto (a, b + 1)\), with inverse \((a, b) \mapsto (a, b - 1)\).
The permutations \(x\) and \(y\) commute:
By extensionality, it suffices to check equality on an arbitrary element \(p \in M\). By simplification using the definitions of \(\mathrm{permX}\), \(\mathrm{permY}\), and the application rule for composed permutations, both sides evaluate to \((p_1 + 1, p_2 + 1)\).
The permutation matrix of \(x\) is orthogonal:
Rewriting the transpose of a permutation matrix as the permutation matrix of the inverse, and using the fact that composing a permutation with its inverse gives the identity, the product equals the identity permutation matrix, which is \(I\).
The permutation matrix of \(y\) is orthogonal:
Rewriting the transpose of a permutation matrix as the permutation matrix of the inverse, and using the fact that composing a permutation with its inverse gives the identity, the product equals the identity permutation matrix, which is \(I\).