A new construction shows exact in-place addition of two n-bit quantum registers can be done in O(log^2 n) depth with O(n log n) classical reversible gates and zero ancilla qubits.
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Ancilla-free Quantum Adder with Sublinear Depth
A new construction shows exact in-place addition of two n-bit quantum registers can be done in O(log^2 n) depth with O(n log n) classical reversible gates and zero ancilla qubits.