rcc-refcert

rcc-refcert is a Python research toolkit for structure-fair quantum circuit complexity. It helps researchers make the physical generation model explicit: which resources are supplied, which quantum processes are allowed, and how their description and generation costs are counted.

You can build and audit finite-control quantum-process models, check reference certificates and gain–cost assignments, and develop new model and certificate constructions. Bundled examples provide reproducible numerical evidence, including a worked chain from a declared model to a lower bound on quantum state preparation cost.

The toolkit implements the finite-control models and reference-certificate methods of Reference-Contingent Complexity (RCC), introduced in Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound.

Start here

Manuscript alignment. This source tree is aligned with version 4 of the RCC manuscript, currently being prepared as the next arXiv revision. The publicly available paper is presently arXiv:2509.18205v3; appendix labels and equation numbers in this repository therefore refer to manuscript version 4.

Why reference-contingent complexity

RCC is a structure-fair, model-relative framework for defining and lower-bounding quantum circuit complexity. It asks how much of a target's structure must be generated when the physical background and available resources are fixed.

The same target state can have different preparation costs under different backgrounds. A reset channel, a supplied ancilla, or a short control macro may already carry structure that makes the target easier to prepare. RCC's structure-fairness principle requires this supplied structure to be represented in the reference or charged through the dynamics and resource coordinates. The generation model fixes the reference background, allowed operations, control language, program prior, success semantics, and cost unit together. Complexity is therefore a relational physical quantity, measured relative to that complete specification.

Within a declared model, $C_{\rm opt}^{(\epsilon)}$ is the infimum of the cost over all admissible histories that prepare the target within accuracy $\epsilon$. Universality concerns the joint target-generation coverage of the admissible model class; optimality concerns all legal histories within a given member. Under the theorem's hypotheses, including reference consistency, faithful transcription, and reference admissibility, RCC converts the target's one-shot structural gap into a lower bound on every such history and hence on the global process optimum. Final-state evidence can thus bound the minimum cost without identifying an optimal preparation path.

Section II of the RCC paper formulates this physical model. Appendix F proves that the model class is nonempty and constructs an admissible qubit model family that can approximate arbitrary pure and mixed states; Appendix H supplies constructive finite-control qualification routes. This repository implements selected finite-control constructions from that chain, while Section III states the main lower-bound theorem. Researchers can use the package to check how a model's quantum dynamics, program weights, reference certificates, and description costs fit together.

What this repository implements

The bundled cases reproduce selected finite constructions from the RCC paper, while the package also accepts new finite-control models and supplied proof objects. It can:

• reproduce the Appendix F/H reference cases and their numerical evidence;
• follow one complete fixed-model chain from a physical declaration and program semidensity to a numerical one-shot RCC lower bound;
• construct a prefix-controlled quantum-process model and compute its terminating program semidensity;
• audit independent trajectory and block-superoperator realizations while preserving least-fixed-point semantics in nonhalting sectors;
• test Bellman–Choi, reference-potential, and fixed-model domination certificates;
• identify operations whose code length understates their reference gain and obtain a sufficient prefix-code completion.

This makes rcc-refcert a compact research testbed for a foundational task: turning quantum-complexity models into explicit objects whose supplied structure and generation costs can be examined.

Quick start

Obtain the source and enter the repository directory:

git clone https://github.com/yeruciwenrou-dotcom/rcc-refcert.git
cd rcc-refcert

Alternatively, download and extract the repository ZIP, then open a terminal in the extracted directory containing quickstart.py.

Python 3.10 or newer is required. On macOS and most Linux systems, use:

python3 --version
python3 quickstart.py

If your environment exposes Python 3.10 or newer as python, the equivalent is:

python quickstart.py

On its first run, the script creates a local .venv, installs the locked verification dependencies, runs the independent test suite, checks both frozen reference files, and writes fresh evidence to generated_results/. Later runs reuse the environment unless the package metadata or dependency lock changes. The three reference cases should all report MATCH; the designed route failure and nonhalting boundary are described in the reference-case table below.

To regenerate and compare the scientific evidence without running the independent tests:

python3 quickstart.py --reproduce-only

To run individual commands in the environment created by the quickstart, use its Python interpreter. On macOS and Linux:

.venv/bin/python -m rcc_refcert examples

On Windows:

.venv\Scripts\python.exe -m rcc_refcert examples

Use the same interpreter for Python scripts and API examples. The equivalent module commands accept the same arguments as rcc-refcert below.

If you prefer an environment you already manage, install the package there:

python3 -m pip install .
rcc-refcert examples
rcc-refcert example dephase-or-halt
rcc-refcert reproduce --check

The default check uses the frozen Markdown and normalized JSON installed with the package, so it also works from outside a repository checkout. Pass an explicit report path to compare another evidence pair.

The equivalent module entry point is python3 -m rcc_refcert. Substitute python when it names a supported Python 3 interpreter. Use --details for residuals, margins, and proposed codewords, or --format json for the versioned machine-readable result:

rcc-refcert example multiblock-rectangular --details
rcc-refcert reproduce --format json

To write a new report, choose the destination explicitly:

rcc-refcert reproduce --output reference_report.md

Jupyter notebook

The notebook dependencies are optional and do not enter the runtime package. After the quickstart has created .venv, macOS and Linux users can run:

.venv/bin/python -m pip install -e ".[notebook]"
.venv/bin/python -m ipykernel install --user --name rcc-refcert --display-name "Python (rcc-refcert)"
.venv/bin/python -m jupyterlab

Open RCC_Quickstart.ipynb and select Python (rcc-refcert) as its kernel. On Windows, use .venv\Scripts\python in the same commands.

End-to-end RCC lower-bound example

A fixed one-qubit paired-reset model connects the finite-control qualification layer to the paper's main lower-bound theorem in Section III, Theorem 3.1. It constructs the complete program semidensity, checks the fixed-model reference conditions, and evaluates the endpoint gap

$$ D_{\max}^{0}(\lvert0\rangle\langle0\rvert\Vert I/2) =1\ \mathrm{bit} =1\thinspace\mathrm{st}_R. $$

Appendix A's canonical cost inversion then gives

$$ C_{\mathrm{opt}}^{(0)}\ge1 \quad\text{atomic resource slot} $$

under the model's stated analytic inputs.

The legal program 0 prepares the target exactly in one slot, giving the matching upper bound. Thus the transparent fixed model satisfies

$$ C_{\mathrm{opt}}^{(0)}=1 $$

atomic resource slot. The displayed feasible program establishes tightness for this fixed model.

From the repository root, use the quickstart environment:

.venv/bin/python examples/paired_reset_lower_bound.py
.venv/bin/python examples/paired_reset_lower_bound.py --json

On Windows, use .venv\Scripts\python.exe in these commands. If you installed into another environment, use that environment's Python interpreter.

The worked explanation separates software checks, analytic model obligations, and the theorem-level consequence. The example states all model inputs explicitly.

Reference cases

The designed H.70 failure is a successful diagnostic: it identifies codewords whose description cost falls short of their reference gain.

Python API

The case API gives the shortest route from a bundled model to its complete audit:

from rcc_refcert import audit_case, get_case

result = audit_case(get_case("multiblock-rectangular"))

print(result.matches_expectations)
print(result.model_analysis.fixed_model_domination.constant)
print(result.gain_cost.outcome.value)

The corresponding values are True, 15/14 numerically, and "fail". The last value is the deliberately failed sufficient condition H.70 described above.

For a new model, use Action, FiniteControlModel, require_valid_model, and audit_model. Supplied proof objects can be checked with verify_bellman_choi, verify_reference_potential, and analyze_reference_gain_cost. The model guide contains a complete minimal example.

Results and scientific scope

Every check reports an outcome—pass, fail, inconclusive, or not_applicable—separately from its evidence, currently numerical. The package establishes finite-input and fixed-model statements. The complete framework—including physical reference consistency, faithful transcription, family-uniform admissibility, and the RCC lower-bound theorem—is developed in the accompanying RCC manuscript. The paper map records the implemented objects and manuscript-version alignment.

See Scientific scope for how these results connect to the RCC theorem, Output contract for result fields and exit codes, and Conventions for the numerical and tensor definitions.

Extending the research kernel

The public model and certificate interfaces support research beyond the bundled reference cases. Extensions are most useful when they enlarge the class of auditable structure-fair models, strengthen the certificate layer, or make its evidence more rigorous. Examples include:

• finite-control models with new physical resources or boundary behavior;
• automated Bellman–Choi or reference-potential certificate search;
• rigorous interval or exact-arithmetic verification;
• family-uniform certificate constructions and scaling diagnostics;
• alternative reference gain–cost encodings and negative witnesses;
• serialization, solver, and larger-state-space backends.

Contributions are welcome across scientific models, algorithms, numerical reliability, documentation, and examples. See Contributing for how to propose and verify a change.

Repository structure

Development, citation, and license

python -m pip install -e ".[dev]"
ruff check src tests examples quickstart.py RCC_Quickstart.ipynb
ruff format --check src tests examples quickstart.py RCC_Quickstart.ipynb
python -W error -m pytest
python -m build

See the Changelog for the capabilities included in this version. Citation metadata for the software and associated RCC paper are provided in CITATION.cff. The source code is available under the MIT License.