qiskit-cayley-codes

CSS quantum code construction from Cayley graphs over F_2^n, connecting original research on ℓ-zero-sumfree sets and the Davenport constant to the quantum LDPC code construction of Couvreur, Delfosse & Zémor.

What this is

Given a classical code over F_2, Couvreur, Delfosse & Zémor (CDZ) show how to build a quantum LDPC code from the Cayley graph of F_2^n generated by the columns of the classical code's parity check matrix. This package implements that construction, and uses it as the target for a separate line of work: generator sets for the Cayley graph are chosen using ℓ-zero-sumfree set theory (closely related to the Davenport constant), which controls the girth of the resulting graph and, through it, properties of the code.

Reference: A. Couvreur, N. Delfosse, G. Zémor, "A Construction of Quantum LDPC Codes from Cayley Graphs," IEEE International Symposium on Information Theory (ISIT), St. Petersburg, 2011. Journal version: IEEE Trans. Inf. Theory 59(9):6087-6098, 2013.

Scope, and how this differs from my other packages

This package is specifically about the code construction problem (classical code + generator set -> quantum CSS code). It does not overlap with:

• qiskit-graph-walks (quantum walks on graphs, not code construction)
• qiskit-zx-verified (ZX-calculus circuit optimization with formal verification, unrelated to error-correcting codes)
• qiskit-qubit-mapping-toolkit (transpiler layout/routing, not codes)

Status

Early stage but functional end-to-end: construct_cdz_code builds a validated CSS code from any F_2^n generating set with even cardinality, and its parameters are checked against the paper's own worked example (Theorem 18: N=8, K=4, D=2 for n=3). Version numbers before 1.0 may change the API. Automated generator-family search (varying S to optimize girth/rate/distance) is not yet implemented -- see the Roadmap section.

Install

pip install qiskit-cayley-codes

For development:

git clone https://github.com/RexRowan/qiskit-cayley-codes.git
cd qiskit-cayley-codes
pip install -e ".[dev]"

Quickstart

import numpy as np
from qiskit_cayley_codes import construct_cdz_code

# Reproduces the paper's own worked example (Theorem 18): the [n,1,n]
# repetition code's generators are the standard basis plus the
# all-ones vector. n must be odd, and |S| = n+1 must be even.
n = 3
generators = [np.eye(n, dtype=np.uint8)[i] for i in range(n)]
generators.append(np.ones(n, dtype=np.uint8))

code = construct_cdz_code(n, generators)
print(code)                          # CDZCode(N=8, K=4, ...)
print(code.min_distance_bruteforce())  # 2 -- matches [[8, 4, 2]] from the paper

Note on generating sets: the CDZ construction requires an even number of (distinct, nonzero) generators -- this alone is sufficient to guarantee a valid CSS code over F_2^n (see the module docstring in construction.py for why). min_distance_bruteforce() is exact but exponential in dim(Ker(Hx)), so it's only practical for small test codes; it is not a substitute for the paper's analytical bounds for real-sized codes.

Integration with qiskit-qec

CDZCode has a to_qiskit_qec() method that converts Hx/Hz into a qiskit_qec.codes.StabSubSystemCode, so codes built here can be handed off to Qiskit QEC's decoders, circuit builders, and analysis tools rather than duplicating that machinery in this package.

qec_code = code.to_qiskit_qec()

Note: qiskit-qec is not published on PyPI, so it isn't listed as a dependency here (PyPI rejects packages that depend on a direct GitHub URL). Install it yourself first:

pip install "qiskit-qec @ git+https://github.com/qiskit-community/qiskit-qec.git"

to_qiskit_qec() raises a clear ImportError with these instructions if it isn't installed.

Analysis tools

Beyond exact brute-force distance (only practical for tiny codes), qiskit_cayley_codes.analysis provides:

from qiskit_cayley_codes import theorem16_lower_bound, search_generator_sets, compare_to_known_families

# Apply the paper's own general lower bound (Theorem 16) without
# brute-forcing the full 2^m-qubit quantum code:
result = theorem16_lower_bound(m=30, w_generators=W)  # {'m', 'w', 'n', 'd', 'bound'}

# Search candidate extra generators for good rate, using
# zero-sumfreeness as a girth proxy:
candidates = search_generator_sets(m=8, candidate_pool=pool, w=2)

# Rough benchmark against toric/surface codes at comparable length:
compare_to_known_families(N=code.n_qubits, D=code.min_distance_bruteforce())

theorem16_lower_bound only requires computing the exact distance of the small classical code C(W) (dimension w, not the full 2^m qubits), which is why it works at scales brute force can't reach -- but it only applies when that classical distance is >= 9, per the theorem's stated range. compare_to_known_families is a rough benchmarking aid: toric and surface codes are topological constructions with very different structure (constant stabilizer weight, geometric locality) from the CDZ family, so treat it as a starting point for comparison, not a rigorous equivalence.

Testing

pytest tests/ -v

Roadmap

• Cayley graph construction over F_2^n, F_2 linear algebra utilities
• ℓ-zero-sumfree set checking and Davenport constant utilities
• construct_cdz_code: full Cayley graph -> CSS code pipeline
• to_qiskit_qec() integration
• Analytical minimum-distance bounds (Theorem 16) for real-sized codes, as a complement to min_distance_bruteforce()
• Generator-set search (search_generator_sets): ranks candidate generating sets by rate, using zero-sumfreeness as a girth proxy
• Benchmark against known code families (compare_to_known_families): toric and planar surface code parameters at comparable length

License

Apache-2.0. See LICENSE.

Citation

If you use this package, please cite the CDZ paper above, and consider citing this repository as well.