Crate prav_core

Crate prav_core 

Source
Expand description

§prav-core: High-Performance Union Find Decoder for Quantum Error Correction

prav-core is a no_std, zero-allocation library implementing a Union Find-based decoder for quantum error correction (QEC) codes, particularly optimized for surface codes and related topological codes.

§Overview

Quantum computers are inherently noisy, and quantum error correction is essential for fault-tolerant quantum computation. This library implements a decoder that:

  1. Receives syndrome measurements - Parity check outcomes indicating where errors occurred
  2. Groups syndromes into clusters - Using Union Find to track connected components
  3. Extracts correction operators - Edges that, when applied, restore the code state

§Architecture

The decoder uses a block-based approach where the lattice is divided into 64-node blocks organized in Morton (Z-order) layout for cache efficiency. Key optimizations:

  • Path halving in Union Find for O(α(n)) amortized complexity
  • Monochromatic fast-path - 95% of blocks at typical error rates
  • SWAR (SIMD Within A Register) bit operations for syndrome spreading
  • Sparse reset - Only reset modified state, not entire data structures

§Quick Start

ⓘ
use prav_core::{Arena, QecEngine, SquareGrid, EdgeCorrection};

// Allocate memory buffer (no heap allocation)
let mut buffer = [0u8; 1024 * 1024];
let mut arena = Arena::new(&mut buffer);

// Create decoder for 32x32 grid
let mut engine: QecEngine<SquareGrid, 32> = QecEngine::new(&mut arena, 32, 32, 1);

// Load syndrome measurements (one u64 per 64 nodes)
let syndromes: &[u64] = &[/* syndrome data */];
let mut corrections = [EdgeCorrection { u: 0, v: 0 }; 1024];

// Decode and get corrections
let num_corrections = engine.process_cycle_dense(syndromes, &mut corrections);

§Module Organization

  • arena - Bump allocator for no_std memory management
  • decoder - Core decoding logic (Union Find, cluster growth, peeling)
  • topology - Lattice connectivity definitions (square, 3D, triangular, honeycomb)
  • qec_engine - High-level API wrapping the decoder
  • intrinsics - Low-level bit manipulation and Morton encoding
  • testing_grids - Standard grid configurations for testing and benchmarks

Re-exports§

pub use arena::Arena;
pub use arena::required_buffer_size;
pub use decoder::DecoderBuilder;
pub use decoder::DynDecoder;
pub use decoder::BlockStateHot;
pub use decoder::BoundaryConfig;
pub use decoder::DecodingState;
pub use decoder::EdgeCorrection;
pub use decoder::TiledDecodingState;
pub use decoder::FLAG_VALID_FULL;
pub use decoder::ClusterGrowth;
pub use decoder::Peeling;
pub use decoder::StaticGraph;
pub use decoder::UnionFind;
pub use qec_engine::QecEngine;
pub use testing_grids::isqrt;
pub use testing_grids::GridConfig;
pub use testing_grids::TestGrids;
pub use testing_grids::ERROR_PROBS;
pub use topology::Grid3D;
pub use topology::HoneycombGrid;
pub use topology::SquareGrid;
pub use topology::Topology;
pub use topology::TriangularGrid;
pub use topology::INTRA_BLOCK_NEIGHBORS;
pub use intrinsics::morton_encode_2d;

Modules§

arena
Arena-based memory allocator for no_std environments. Arena-based bump allocator for no_std environments.
decoder
Core decoder types, traits, and implementations.
intrinsics
Low-level bit manipulation, Morton encoding, and syndrome spreading.
qec_engine
High-level QEC engine wrapper. High-level QEC decoder API.
testing_grids
Pre-configured test grid sizes and error probabilities.
topology
Grid topology definitions (square, 3D, triangular, honeycomb). Grid topology definitions for QEC lattices.