TheoremStatement: AI-adaptedProof: AI-generatedPipeline-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.

Finite abelian hidden-subgroup query and circuit costs

Statement

Let $N = ∣ G ∣$ . For $N \geq 2$ , let $M$ be the integer supplied to the reconstruction algorithm. If the supplied preparation and product-QFT circuits make no access to the hiding oracle, then in a named-oracle query model the algorithm makes exactly $M$ coherent hiding-oracle queries; this query count is separate from ordinary gate costs. Let $C_{P}$ and $C_{Q}$ be the ordinary gate counts of the supplied exact uniform-state preparation and product-QFT circuits. If the hiding function is instead compiled from an explicit reversible Boolean circuit with $C_{F}$ gates per evaluation, the total ordinary gate count is $M (C_{P} + C_{Q} + C_{F})$ ; a named oracle query is not silently counted as an elementary gate. Each sample measures a $b$ -bit character label, where $b = \sum_{i} ⌈ \log_{2} n_{i} ⌉$ . The output list therefore uses $M b$ bits and writing it costs $O (M b) = O (M \log_{2} N)$ classical bit operations, once $M$ and the circuits are supplied. If a model assigns separate per-sample costs $C_{m e a s}$ to label measurement and $C_{d i s c}$ to discarding the output register, the corresponding coordinates are $M C_{m e a s}$ and $M C_{d i s c}$ ; they remain separate from gates and queries. If supplied invariant-factor circuits satisfy $C_{P} + C_{Q} = O (\log^{2} N)$ and the hiding-oracle circuit has $C_{F}$ gates per evaluation, the ordinary gate count is $O (M (C_{F} + \log^{2} N))$ , while the named-oracle query count remains $M$ under the same no-access condition. For $N = 1$ the algorithm uses zero oracle queries and outputs the trivial common kernel with constant control work. Computing the integer $M$ , generating circuit descriptions, and converting the implicit list to subgroup generators are separate costs; no polynomial-time implementation claim is made without those explicit inputs and bounds.

Facts & Assumptions

Given: The common-kernel output encoding, exact sample/reconstruction procedures, and the cost coordinates declared by Circuit-family and computation cost model and Coherent XOR function oracle.

[F1]

For $N \geq 2$ and positive integer input $M$ , the reconstruction procedure makes $M$ independent sample calls and outputs their character list, with no generator conversion. For $N = 1$ it returns the empty list denoting $G$ immediately, without sample calls or oracle queries. (Finite abelian hidden-subgroup common-kernel reconstruction)

[F2]

The character dual of a product is indexed by the product of the cyclic character labels, and a cyclic factor of order $n$ has exactly $n$ character labels. (Characters of a finite product factor coordinatewise, A cyclic group of order n has exactly n additive characters)

[F3]

The cost model keeps named oracle queries, finite-basis gates, uniform-family generation, and classical bit costs as separate coordinates. (Circuit-family and computation cost model)

[F4]

A supplied XOR oracle invocation is one named oracle call; compiling an explicit Boolean function requires reversible-gate costs. (Coherent XOR function oracle)

[F5]

For $N \geq 2$ , one sample invokes the supplied preparation, hiding oracle, product QFT, output-register discard, and character-label measurement once. For $N = 1$ it returns the trivial character without these operations. (One finite abelian hidden-subgroup Fourier sample)

[F6]

The group and character labels use fixed-width binary coordinates with $b = \sum_{i} ⌈ \log_{2} n_{i} ⌉$ bits. (Finite abelian hidden-subgroup promise and output encoding)

[F7]

Under the query-count hypothesis in the Statement, the preparation and product-QFT circuits make no access to the hiding oracle; the sample procedure's only such access is its explicit call to $O_{F}$ . (One finite abelian hidden-subgroup Fourier sample)

Proof

1.1F1F4F7

For $N \geq 2$ , the reconstruction algorithm executes exactly $M$ independent sample procedures by [F1]. Under [F7], each sample's explicit call to the hiding oracle is its only hiding-oracle access, so the query coordinate is exactly $M$ . If the oracle is compiled from a Boolean circuit, its $M$ evaluations contribute $M C_{F}$ ordinary gates by [F4].

1.2F2F6algebra

Still assuming $N \geq 2$ , write $G = \prod_{i = 1}^{r} Z / n_{i} Z$ with each $n_{i} \geq 2$ . By [F2] and [F6], each character is represented by one tuple with coordinate $k_{i} \in Z / n_{i} Z$ and its fixed-width binary encoding uses $b = \sum_{i} ⌈ \log_{2} n_{i} ⌉ \leq \log_{2} N + r \leq 2 \log_{2} N$ bits, since $r \leq \log_{2} N$ . Thus the output list has $M b = O (M \log_{2} N)$ bits, and writing those bits takes the same order of classical bit operations.

1.3F1F3F4F5F7algebra

For $N \geq 2$ , by [F5], one sample uses one preparation, one QFT, one label measurement, one output-register discard, and one explicit hiding-oracle evaluation. Under [F7], that is one hiding-oracle query per sample. Sequentially composing $M$ samples multiplies each additive per-sample coordinate by $M$ : the named-query coordinate is $M$ , and the ordinary gate count is $M (C_{P} + C_{Q} + C_{F})$ when an explicit oracle circuit is used. Measurements and discarding are charged in their own declared coordinates; they are not added to gate or query counts. The cost model [F3] also keeps description generation and the classical computation of $M$ separate.

2.1F1step 1.3algebra∎

If $C_{P} + C_{Q} = O (\log^{2} N)$ and the oracle is compiled with $C_{F}$ gates per evaluation, the gate count in step 1.3 is $O (M (C_{F} + \log^{2} N))$ ; the query and classical-output bounds remain separate. For $N = 1$ , [F1] gives the immediate empty-list return, denoting $G$ , with zero queries and constant control work.

Remarks

The $O (\log^{2} N)$ premise is conditional on actual exact circuits for the supplied invariant-factor preparation and QFT, including any encoding extension. It does not assert that such circuits exist over an arbitrary fixed finite gate alphabet.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

44 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)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)