Finite cyclic discrete logarithm by Fourier sampling

Input a promised instance $(G,g,x,q)$ from Finite cyclic discrete-logarithm problem and costed encoding and a rational confidence target $\delta =p\mathrm{/}v$ supplied as binary positive integers $p<v$, together with supplied exact uniform-state preparation and product-QFT circuits for ${\mathbb{Z}}_q^2$, including their full-register extensions and declared costs as required by One finite abelian hidden-subgroup Fourier sample. If the direct coherent $f$ oracle is unavailable, first check that the supplied interfaces support profile 2 of Costed coherent evaluation of cyclic group powers, including classical repeated squaring and the forward and inverse-constant controlled multiplications. If they do not, return UNSUPPORTED_ACCESS before sampling. Otherwise construct that profile's explicit compute-XOR-uncompute oracle and precompute its repeated-squaring constants once for all samples. Let $L=\lceil {\log }_{2}q\rceil$, computed as the bit length of $q-1$. Let $D$ be the least integer $d\ge 0$ with $2^d\delta \ge 1$, found by testing $d=0,1,\dots$ using exact rational comparisons, and set $t=(1+L)D$. Repeat the following $t$ times, with fresh registers and independent measurements:

1. Use One finite abelian hidden-subgroup Fourier sample once on ${\mathbb{Z}}_q\times {\mathbb{Z}}_q$ with hiding function $f(u,v)=g^u{x}^v$, obtaining a character label $(c,d)$.
2. Use Extended-Euclidean modular inverse with bounded bit cost on $(q,c)$. If it returns NO_INVERSE, discard this sample and continue; otherwise its output is $c^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}q)$.
3. Set $\tilde{a}=d{c}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}q)$.
4. Compute $g^{\tilde{a}}$ by binary repeated squaring using the supplied multiplication interface, then compare it with $x$ using the equality interface. Return $\tilde{a}$ only if they agree.

If no iteration returns a verified value, return FAIL. A direct coherent oracle for $f$ costs one $f$ query per sample only when explicitly supplied; on the supported fallback branch, charge the controlled group operations, gates, and classical precomputation of Costed coherent evaluation of cyclic group powers. The algorithm does not infer controlled access from an uncontrolled oracle.