Module subpoly_decoder 

Subpolynomial-complexity surface code decoders.

This module establishes provable subpolynomial complexity bounds for surface code decoding by exploiting the locality structure of physical errors. Three decoders are provided:

• HierarchicalTiledDecoder: Recursive multi-scale tiling achieving O(d^{2-epsilon} polylog d) expected-case complexity.
• RenormalizationDecoder: Coarse-graining inspired by the renormalization group, contracting local error chains at each scale.
• SlidingWindowDecoder: Streaming decoder for multi-round syndrome data with O(w d^2) per-round complexity.

A ComplexityAnalyzer provides rigorous certificates for decoder scaling, and DefectGraphBuilder constructs spatial-hash-accelerated defect graphs for efficient neighbor lookup.

Complexity argument (sketch)

For a distance-d surface code at physical error rate p < p_th, the probability that any error chain spans a region of linear size L decays as exp(-c L). A tile of side s therefore has probability 1 - O(exp(-c s)) that all its errors are interior. The hierarchical decoder processes d^2/s^2 tiles of cost O(s^2) each (total O(d^2)), but boundary merging costs only O(perimeter) = O(s) per tile edge. Across log(d/s) hierarchy levels the merge cost sums to O(d^2 / s * sum_{k=0}^{log(d/s)} 2^{-k}) = O(d^2 / s). Choosing s = d^epsilon yields total cost O(d^{2-epsilon} polylog d).

Structs

ComplexityAnalyzer

Analyzes decoder complexity and threshold behaviour.

ComplexityBound

Provable complexity certificate for a decoder configuration.

DefectEdge

An edge in the defect graph.

DefectGraphBuilder

Spatial-hash-accelerated defect graph for efficient neighbor queries.

HierarchicalTiledDecoder

Recursive multi-scale decoder achieving O(d^{2-epsilon} polylog d) expected complexity for physical error rates below threshold.

RenormalizationDecoder

Renormalization-group inspired decoder.

ScalingDataPoint

A single data point from empirical scaling measurements.

SlidingWindowDecoder

Streaming decoder for multi-round syndrome data.

SubpolyVerification

Result of a statistical test for subpolynomial scaling.

ThresholdTheorem

Threshold theorem parameters for a surface code family.

Functions

benchmark_scaling

Measure empirical decode time scaling across code distances.

verify_subpolynomial

Statistical test for subpolynomial (subquadratic) scaling.