Costed coherent evaluation of cyclic group powers

Inputs are a valid instance from Finite cyclic discrete-logarithm problem and costed encoding, exponent registers $u,v\in \{0,\dots ,q-1\}$, and one of these access profiles:

1. a supplied coherent XOR oracle for $f(u,v)=g^u{x}^v$; initialize a fresh output target to $0^w$, invoke the oracle once, and return its output (the zero target need not be the encoding of the group identity); or
2. explicit reversible group-operation circuits, or separately charged named controlled-multiplication operations with the same complete-register action, for each classically specified constant and its inverse. Initialize a fresh accumulator to $\mathrm{enc}(e)$, the code of the group identity. Precompute $g_j=g^{2^j}$ and $x_j=x^{2^j}$ for $0\le j<L$, where $L=\lceil {\log }_{2}q\rceil$, by repeated squaring. For $j=0,\dots ,L-1$, use the bit $u_j$ to apply the clean controlled multiplication by $g_j$ to the accumulator, and use $v_j$ to apply the clean controlled multiplication by $x_j$. The procedure is the circuit of Clean reversible controlled multiplication by a cyclic constant applied at each control bit.

In profile 2, return the accumulator as the function value. The exponent registers are unchanged, all work and temporary target wires are returned to their declared initial states, and each direct oracle invocation or group-operation invocation is charged under its separately declared access profile. If only an uncontrolled black-box group operation is supplied, return UNSUPPORTED_ACCESS: it does not provide a controlled call.

To supply the total coherent XOR oracle required by the hidden-subgroup sampler, profile 2 is wrapped as follows. Prepare its $w$-bit accumulator from zero to $\mathrm{enc}(e)$ with at most $w$ Pauli-$X$ gates, execute the $2L$ controlled multiplications, copy the resulting $w$-bit value by CNOT into an arbitrary target $y$, then reverse the evaluation using the separately supplied inverse-constant controlled multiplications. Finally undo the initial $X$ gates. This implements $\mathrm{\mid }u,v,y⟩\mapsto \mathrm{\mid }u,v,y\oplus \mathrm{enc}(g^u{x}^v)⟩$ on valid exponent codes and restores every auxiliary wire to zero. The supplied total controlled operations also define its action on invalid exponent codes; these values are the declared Boolean extension. The wrapper uses $4L$ controlled multiplications and at most $3w$ extra $X$/CNOT gates; preparation, output copying, and inverse calls are charged.

The two explicit-circuit loops use $2L$ controlled multiplications per function evaluation. Their correctness and clean-work identity are proved in Correctness and clean-work cost of cyclic power evaluation. This algorithm makes no generic efficiency claim for abstract finite groups.