CryptoRecords.info
Binary decoding

Decoding random binary codes

Decode a random binary linear code at a specified rate and error weight.

Quantum · polynomial qubits · full GV

Full GV distance; maximum over rates; polynomial quantum workspace

2 results · 1 papers
QuantumSource asymptotic analysisRandom binary codes2c n + o(n)
Results
Compare historyJSONCSV
#PUBLICATION / AUTHORSDATETIME BOUNDSPACE BOUNDEVIDENCE
1Reducing the Number of Qubits in Quantum Information Set DecodingClémence Chevignard · Pierre-Alain Fouque · André SchrottenloherAsiacrypt 2024SourceBibTeX / details10 Sept 202420.06035 n + o(n)O(n) qubitsPublishedSource checked
1Reducing the Number of Qubits in Quantum Information Set DecodingClémence Chevignard · Pierre-Alain Fouque · André SchrottenloherAsiacrypt 2024SourceBibTeX / details10 Sept 202420.06035 n + o(n)O(n log² n) qubitsPublishedSource checked
1–2 of 2 entriesIncludes relevant non-record results. Dates refer to the specific bound.
Comparison definition & assumptions
Regime
Full GV distance; maximum over rates; polynomial quantum workspace
Computation
Quantum
Rigor
Source asymptotic analysis
Instances
Random binary codes
Cost scale
2^{c n + o(n)}
Parameter
n
Description
Quantum decoding with a polynomial qubit bound.
Comparison rules
Restrict quantum workspace to a polynomial in n. The listed coefficient is the maximum over code rates at full GV distance. Polynomial gates/depth and qubit scaling remain visible in the record; they must not be conflated with exponential-list quantum walk algorithms.
Tags
quantum, polynomial qubits, full GV distance, maximum over rates