Quantum sieving for SVP in dimension 400 needs ~10^13 physical qubits and ~10^31 years under optimistic assumptions, offering no practical speedup over classical methods.
Quantum Carry-Save Arithmetic
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper shows how to design efficient arithmetic elements out of quantum gates using "carry-save" techniques borrowed from classical computer design. This allows bit-parallel evaluation of all the arithmetic elements required for Shor's algorithm, including modular arithmetic, deferring all carry propagation until the end of the entire computation. This reduces the quantum gate delay from O(N^3) to O(N log N) at a cost of increasing the number of qubits required from O(N) to O(N^2).
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 1years
2024 1verdicts
UNVERDICTED 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
On the practicality of quantum sieving algorithms for the shortest vector problem
Quantum sieving for SVP in dimension 400 needs ~10^13 physical qubits and ~10^31 years under optimistic assumptions, offering no practical speedup over classical methods.