Paper 2026/2057

Low-Space Quantum Discrete Logarithms on Genus-Two Jacobians

Abstract

Generic divisor-addition formulas require little arithmetic workspace but fail on exceptional inputs. We prove a randomized reduction that enables their use in quantum phase computation. The reduction uses two independent public group seeds in a finite abelian group of odd order. For every fixed input, the two child values at each internal node of a complete balanced addition tree are independent and uniform. The density of exceptional pairs therefore controls both the total failure probability and the error of the averaged quantum channel. We apply this reduction to an odd prime-order subgroup of size $r$ in a genus-two Jacobian over $\mathbb{F}_q$, where $q$ is an odd prime. The curve is represented by a monic quintic with zero quartic coefficient. An integer lift of weighted Mumford arithmetic, a terminal polynomial for phase computation, and an independently shifted Legendre symbol yield useful-sample probability $1-\mathcal{O}(L/q)$ on the exact domain $\mathbb{Z}_r^2$ when $r=\Theta(q^2)$. Here $\mathbb{Z}_r=\mathbb{Z}/r\mathbb{Z}$ and $L$ denotes the number of tree leaves. This probability bound assumes exact state preparation and Fourier readout. Explicit height certificates, streaming Chinese remainder reconstruction, and clean modular primitives give a sampler using $10n+o(n)$ logical qubits, including both scalar registers, where $n=\lceil\log_2 q\rceil$. The computational model permits 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{,}923$ qubits, compared with $2{,}172$ and $3{,}063$ qubits for the matched Huang et al.\ and Chen et al.\ module schedules, respectively. All three schedules retain the same scalar inputs. The Toffoli bound for a capped run is below $2^{60}$. A $32$-bit window reduces the allocation to $1{,}618$ qubits, with a Toffoli bound of approximately $2^{70.43}$ and at most $2^{36}$ classical table entries. Rotation synthesis is charged separately. These estimates quantify an explicit space--time tradeoff.