Decoding random binary codes
Decode a random binary linear code at a specified rate and error weight.
Quantum · R = 0.454 · full GV
k/n = 0.454; t/n = H₂⁻¹(0.546) ≈ 0.125869
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | A novel improved information set decoding algorithm via nearest neighbor searchCybersecurity 2026SourceBibTeX / details | 11 Jun 2026 | 20.057866 n + o(n) | 20.026094 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- k/n = 0.454; t/n = H₂⁻¹(0.546) ≈ 0.125869
- Computation
- Quantum
- Rigor
- Source asymptotic analysis
- Instances
- Random binary codes
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Fixed-rate quantum ISD comparisons.
- Comparison rules
- The code length is n. Fix R=0.454 and relative error weight H₂⁻¹(1−R). Charge quantum subset-sum, nearest-neighbor and Grover costs as in each source. This list is not a maximum over all code rates.
- Tags
- quantum, full GV distance, fixed rate, quantum memory