TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Correctness and clean-work cost of cyclic power evaluation

Statement

For every valid encoded cyclic-group input $(G, g, x, q)$ with $q \geq 2$ and every $u, v \in {0, \dots, q - 1}$ , the explicit-circuit branch of Costed coherent evaluation of cyclic group powers writes the encoding of $g^{u} x^{v}$ into the accumulator, leaves the exponent registers unchanged, and returns every clean work and temporary target register to zero. If $L = ⌈ \log_{2} q ⌉$ and each controlled multiplication by a known constant has gate cost at most $C_{G}$ , the circuit uses $2 L$ controlled multiplications and $O (L C_{G})$ gates per evaluation, in addition to the separately charged classical precomputation. The compute-XOR-uncompute wrapper in that algorithm implements the full target-XOR action on valid exponent codes, with its declared total extension elsewhere. If each forward and inverse-constant controlled multiplication costs at most $C_{G}$ , that wrapper uses $4 L$ such calls and at most $3 w$ additional $X$ /CNOT gates, hence $O (L C_{G} + w)$ gates, and restores its auxiliary registers to zero.

Facts & Assumptions

Given: A cyclic group $G = ⟨ g ⟩$ of exact order $q \geq 2$ , $x \in G$ , valid exponent codes $u, v$ , and the explicit circuit branch of Costed coherent evaluation of cyclic group powers.

[F1]

$G = ⟨ g ⟩$ has exact order $q$ and $x \in G$ , so every element of $G$ is a power of $g$ (Finite cyclic discrete-logarithm problem and costed encoding).

[F2]

Every integer in ${0, \dots, q - 1}$ has an $L$ -bit binary expansion with $L = ⌈ \log_{2} q ⌉$ (Big-endian encoding of ordered bit strings).

[F3]

Group powers satisfy $g^{a + b} = g^{a} g^{b}$ and $(g^{a})^{b} = g^{a b}$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[F4]

Each controlled multiplication by a known constant acts exactly on valid codes and restores its clean work to zero (Clean reversible controlled multiplication by a cyclic constant).

[F5]

The algorithm processes every bit of $u$ and $v$ once, applying the corresponding controlled multiplications in its chronological circuit order (Costed coherent evaluation of cyclic group powers, Denotational semantics of a finite layered circuit).

Proof

1.1givenF2F3algebra

Write $u = \sum_{j = 0}^{L - 1} u_{j} 2^{j}$ and $v = \sum_{j = 0}^{L - 1} v_{j} 2^{j}$ using [F2]. Repeated squaring with [F3] gives the classically precomputed constants $g_{j} = g^{2^{j}}$ and $x_{j} = x^{2^{j}}$ : the base constants are $g_{0} = g$ and $x_{0} = x$ , and squaring $g_{j}, x_{j}$ gives $g_{j + 1}, x_{j + 1}$ .

2.1givenF1F3F4F5step 1.1inductionalgebra

After processing the first $j$ bits of each exponent, the accumulator is $g^{\sum_{i < j} u_{i} 2^{i}} x^{\sum_{i < j} v_{i} 2^{i}}$ . It is the identity at $j = 0$ . At stage $j$ , [F4] multiplies it by $g_{j}$ exactly when $u_{j} = 1$ and by $x_{j}$ exactly when $v_{j} = 1$ . Since [F1] places both elements in the cyclic group generated by $g$ , their powers commute; [F3] therefore gives the same formula with the sums extended through $i = j$ . Induction proves the invariant through $j = L$ .

3.1F2F4F5step 2.1algebra

At $j = L$ , the binary sums are $u$ and $v$ , so the accumulator is $g^{u} x^{v}$ . Each controlled multiplication in step 2.1 restores its internal work and temporary target by [F4], while no operation changes the exponent registers. Thus the stated output and clean-work identities hold.

4.1F2F4F5step 2.1algebra∎

There are exactly $L$ controlled multiplications for the bits of $u$ and $L$ for the bits of $v$ . Each costs at most $C_{G}$ gates, so their total is at most $2 L C_{G} = O (L C_{G})$ ; precomputing the constants is classical work and is charged separately. For the full XOR wrapper, prepare the identity code with at most $w$ flips, perform these $2 L$ calls, copy each output bit into the arbitrary target, and apply the inverse calls in reverse order. The exponent registers are unchanged and the copied target is not an input to the reversed computation, so its accumulator returns to the identity code and every internal work bit returns to zero. Undoing the identity-code flips clears the accumulator. There are $4 L$ controlled calls and at most $2 w + w = 3 w$ extra elementary gates, yielding the stated wrapper cost and clean XOR action by linearity on the computational basis.

Depends on

Used by

Finite cyclic discrete-log correctness, success and costs Theorem

Dependency tree · two levels

38 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)
Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (standard reference, not scraped)