Paper 2026/2057

Low-Space Quantum Discrete Logarithms on Genus-Two Jacobians

Abstract

Quantum discrete logarithms on genus-two Jacobians require reversible arithmetic with controlled workspace. Generic divisor-addition formulas apply only outside an exceptional set, which must be accounted for in quantum phase computation. We give a randomized reduction using two fresh independent uniform public seeds in a finite abelian group of odd order to randomize a complete balanced addition tree. For inputs independent of the seeds, exceptional-pair densities bound the averaged phase-channel error and sampling failure probability. We apply this reduction to an odd-prime-order subgroup of a genus-two Jacobian over $\mathbb{F}_q$, where $q$ is an odd prime and the supplied curve model is a square-free monic quintic with zero quartic coefficient. Integer lifting, an independently shifted Legendre phase, and streaming Chinese remainder reconstruction yield a low-space sampler. For subgroup order $r=\Theta(q^2)$, the useful-sample probability is $1-\mathcal{O}(L/q)$, averaged over fresh seeds, for an exact uniform input state and ideal Fourier readout, where $L$ is the number of tree leaves. With window width $w=\Theta(\log_2 n)$, the sampler uses $10n+o(n)$ logical qubits, including both scalar registers, with $n=\lceil\log_2q\rceil$, and allows intermediate measurements, reset, and classical feedforward. For the Gaudry--Schost instance over $\mathbb{F}_{2^{127}-1}$, a $16$-bit window gives an analytic allocation of $1{,}971$ qubits and a capped-run Toffoli bound below $2^{60.561}$. A matched schedule derived from Chen et al.'s addition module uses $3{,}063$ qubits; both schedules retain the same $500$ scalar-input qubits. These comparisons are schedule-specific, and rotation synthesis is counted separately.