Decoding random binary codes
Decode a random binary linear code at a specified rate and error weight.
6 variants · 28 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
Binary decodingBinary · full GV distanceClassical · Source analysisBinary random linear codes; full Gilbert–Varshamov distance; maximum over ratesRandom binary linear codes100.0885 Binary decodingQuantum · full GV distanceQuantum · Source analysisQuantum ISD for random binary codes at full GV distance; maximum over ratesRandom binary linear codes70.058326 Binary decodingBinary · half distanceClassical · Asymptotic analysisHalf-distance decoding; worst asymptotic rateRandom binary codes80.0453 Binary decodingQuantum · polynomial qubits · full GVQuantum · Source asymptotic analysisFull GV distance; maximum over rates; polynomial quantum workspaceRandom binary codes20.06035 Binary decodingQuantum · R = 0.454 · full GVQuantum · Source asymptotic analysisk/n = 0.454; t/n = H₂⁻¹(0.546) ≈ 0.125869Random binary codes10.057866 Binary decodingQuantum ISD · fixed-rate templateQuantum · Asymptotic analysisSpecify code rate R, relative error weight τ, QRAM access and qubit cost before comparingRandom binary codes0—