prav_core/
lib.rs

1//! # prav-core: High-Performance Union Find Decoder for Quantum Error Correction
2//!
3//! `prav-core` is a `no_std`, zero-allocation library implementing a Union Find-based
4//! decoder for quantum error correction (QEC) codes, particularly optimized for surface
5//! codes and related topological codes.
6//!
7//! ## Overview
8//!
9//! Quantum computers are inherently noisy, and quantum error correction is essential
10//! for fault-tolerant quantum computation. This library implements a decoder that:
11//!
12//! 1. **Receives syndrome measurements** - Parity check outcomes indicating where errors occurred
13//! 2. **Groups syndromes into clusters** - Using Union Find to track connected components
14//! 3. **Extracts correction operators** - Edges that, when applied, restore the code state
15//!
16//! ## Architecture
17//!
18//! The decoder uses a block-based approach where the lattice is divided into 64-node
19//! blocks organized in Morton (Z-order) layout for cache efficiency. Key optimizations:
20//!
21//! - **Path halving** in Union Find for O(α(n)) amortized complexity
22//! - **Monochromatic fast-path** - 95% of blocks at typical error rates
23//! - **SWAR (SIMD Within A Register)** bit operations for syndrome spreading
24//! - **Sparse reset** - Only reset modified state, not entire data structures
25//!
26//! ## Quick Start
27//!
28//! ```ignore
29//! use prav_core::{Arena, QecEngine, SquareGrid, EdgeCorrection};
30//!
31//! // Allocate memory buffer (no heap allocation)
32//! let mut buffer = [0u8; 1024 * 1024];
33//! let mut arena = Arena::new(&mut buffer);
34//!
35//! // Create decoder for 32x32 grid
36//! let mut engine: QecEngine<SquareGrid, 32> = QecEngine::new(&mut arena, 32, 32, 1);
37//!
38//! // Load syndrome measurements (one u64 per 64 nodes)
39//! let syndromes: &[u64] = &[/* syndrome data */];
40//! let mut corrections = [EdgeCorrection { u: 0, v: 0 }; 1024];
41//!
42//! // Decode and get corrections
43//! let num_corrections = engine.process_cycle_dense(syndromes, &mut corrections);
44//! ```
45//!
46//! ## Module Organization
47//!
48//! - [`arena`] - Bump allocator for `no_std` memory management
49//! - [`decoder`] - Core decoding logic (Union Find, cluster growth, peeling)
50//! - [`topology`] - Lattice connectivity definitions (square, 3D, triangular, honeycomb)
51//! - [`qec_engine`] - High-level API wrapping the decoder
52//! - [`intrinsics`] - Low-level bit manipulation and Morton encoding
53//! - [`testing_grids`] - Standard grid configurations for testing and benchmarks
54
55#![no_std]
56#![deny(missing_docs)]
57#![allow(internal_features)]
58
59// =============================================================================
60// Module Declarations
61// =============================================================================
62
63/// Arena-based memory allocator for no_std environments.
64pub mod arena;
65
66/// Core decoder types, traits, and implementations.
67pub mod decoder;
68
69/// Low-level bit manipulation, Morton encoding, and syndrome spreading.
70pub mod intrinsics;
71
72/// High-level QEC engine wrapper.
73pub mod qec_engine;
74
75/// Pre-configured test grid sizes and error probabilities.
76pub mod testing_grids;
77
78/// Grid topology definitions (square, 3D, triangular, honeycomb).
79pub mod topology;
80
81/// Kani formal verification proofs for arena allocator.
82#[cfg(kani)]
83mod arena_kani;
84
85// =============================================================================
86// Convenience Re-exports (Clean Public API)
87// =============================================================================
88
89// Memory allocation and sizing
90pub use arena::{Arena, required_buffer_size};
91
92// Builder pattern (ergonomic API for hiding STRIDE_Y)
93pub use decoder::{DecoderBuilder, DynDecoder};
94
95// Core decoder types
96pub use decoder::{
97    BlockStateHot, BoundaryConfig, DecodingState, EdgeCorrection, TiledDecodingState,
98    FLAG_VALID_FULL,
99};
100
101// Decoder traits (for advanced users and benchmarks)
102pub use decoder::{ClusterGrowth, Peeling, StaticGraph, UnionFind};
103
104// High-level engine
105pub use qec_engine::QecEngine;
106
107// Testing utilities
108pub use testing_grids::{isqrt, GridConfig, TestGrids, ERROR_PROBS};
109
110// Topology types
111pub use topology::{Grid3D, HoneycombGrid, SquareGrid, Topology, TriangularGrid};
112pub use topology::INTRA_BLOCK_NEIGHBORS;
113
114// Morton encoding (commonly needed for defect generation)
115pub use intrinsics::morton_encode_2d;
prav_core/lib.rs

prav_core/
lib.rs
