Finite cyclic discrete-logarithm problem and costed encoding

A finite cyclic discrete-logarithm instance consists of a cyclic group $G=⟨g⟩$ of known exact order $q\ge 2$ and an element $x\in G$. Its answer is the unique integer $a\in \{0,\dots ,q-1\}$ satisfying $g^a=x$. Uniqueness follows because $g^u=g^v$ exactly when $u\equiv v(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

For a quantum or bit-cost claim, the instance additionally declares an injective fixed-length encoding $\mathrm{enc}:G\to \{0,1{\}}^w$, with $w\ge \lceil {\log }_{2}q\rceil$, and one of the following operation profiles:

1. explicit reversible circuits for multiplication, equality, and any controlled multiplication used by the algorithm, with gate and clean-work costs; or
2. named group-operation oracles with a separate query charge for each operation. A controlled call is available only if that controlled operation is explicitly supplied and charged.

The associated hidden-subgroup function is $f:{\mathbb{Z}}_q\times {\mathbb{Z}}_q\to G$, $f(u,v)=g^u{x}^v$. A direct coherent XOR oracle for its fixed-length encoding is a separate supplied interface; if it is supplied, one call costs one $f$ query. Group-operation oracles do not automatically supply this function oracle, a controlled call, an inverse call, a gate implementation, or a classical bit-cost bound. No efficient implementation is asserted for every abstract finite cyclic group.

The problem definition does not require $q$ to be prime. For $x=g^a$, the function $f$ is analyzed by the separate hidden-subgroup lemma on this page.