Metadata-Version: 2.4
Name: qiskit-cayley-codes
Version: 0.1.1
Summary: CSS quantum code construction from Cayley graphs over zero-sumfree sets
Author: Rex Rowan
License: Apache-2.0
Project-URL: Homepage, https://github.com/RexRowan/qiskit-cayley-codes
Project-URL: Repository, https://github.com/RexRowan/qiskit-cayley-codes
Project-URL: Issues, https://github.com/RexRowan/qiskit-cayley-codes/issues
Keywords: qiskit,quantum computing,quantum error correction,CSS codes,Cayley graphs
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Physics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: qiskit<3,>=2.0
Requires-Dist: numpy>=1.24
Requires-Dist: networkx>=3.0
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Requires-Dist: pytest-cov; extra == "dev"
Requires-Dist: black; extra == "dev"
Requires-Dist: ruff; extra == "dev"
Dynamic: license-file

# 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.

[![Tests](https://github.com/RexRowan/qiskit-cayley-codes/actions/workflows/test.yml/badge.svg)](https://github.com/RexRowan/qiskit-cayley-codes/actions/workflows/test.yml)
[![PyPI](https://img.shields.io/pypi/v/qiskit-cayley-codes.svg)](https://pypi.org/project/qiskit-cayley-codes/)
[![License](https://img.shields.io/badge/license-Apache%202.0-blue.svg)](LICENSE)

## 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

```bash
pip install qiskit-cayley-codes
```

For development:

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

## Quickstart

```python
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](https://github.com/qiskit-community/qiskit-qec)'s
decoders, circuit builders, and analysis tools rather than duplicating
that machinery in this package.

```python
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:

```bash
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:

```python
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

```bash
pytest tests/ -v
```

## Roadmap

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

## License

Apache-2.0. See [LICENSE](LICENSE).

## Citation

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