Binary decoding / Quantum · polynomial qubits · full GV

Reducing the Number of Qubits in Quantum Information Set Decoding

Clémence Chevignard · Pierre-Alain Fouque · André Schrottenloher

Asiacrypt 2024

PublishedSource checked

Time bound: 2^{0.06035 n + o(n)}
Space bound: O(n log² n) qubits

Source / version date: 10 Sept 2024
Comparison variant: Quantum · polynomial qubits · full GV
Cost scale: 2^{c n + o(n)}
per_iterate_Toffoli_gates: O(n² log² n)
total_gates_per_iterate: O(n³)

Assumptions and source notes

Same search coefficient; alternative polynomial gate/qubit trade-off.

Source location

Abstract, second trade-off
Version: 2024-09-10

Primary source ↗

BibTeXDownload .bib

@misc{chevignard-fouque-schrottenloher2024,
  author = {Clémence Chevignard and Pierre-Alain Fouque and André Schrottenloher},
  title = {{Reducing the Number of Qubits in Quantum Information Set Decoding}},
  year = {2024},
  url = {https://eprint.iacr.org/2024/907},
  cr_date = {2024-06-06},
  cr_status = {published},
  cr_venue = {ASIACRYPT 2024},
  cr_author_ids = {clemence-chevignard; pierre-alain-fouque; andre-schrottenloher}
}