LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Dihedral hidden-state pair combination

Statement

Let $N \geq 2$ , $s \in Z / N Z$ , and

∣ ψ_{k} ⟩ : = \frac{∣ 0 ⟩ + \exp (2 π i k s / N) ∣ 1 ⟩}{\sqrt{2}}

for $k \in Z / N Z$ . On two ordered qubits define $C ∣ a, b ⟩ = ∣ a, b \oplus a ⟩$ for $a, b \in {0, 1}$ . Apply $C$ to $∣ ψ_{k} ⟩ \otimes ∣ ψ_{ℓ} ⟩$ and projectively measure the second qubit in its computational basis. Each outcome has probability $1 / 2$ . After discarding the measured qubit, outcome $0$ leaves the first qubit in $∣ ψ_{k + ℓ} ⟩$ ; outcome $1$ leaves it in $∣ ψ_{k - ℓ} ⟩$ up to a global phase. The readout is implemented by the Lüders projective instrument of the stated computational-basis projections, so the conditional-state claims refer to its normalized branches.

Facts & Assumptions

Given: $N \geq 2$ , $s, k, ℓ \in Z / N Z$ , the two normalized states above, the specified ordered two-qubit basis, and the specified two-outcome measurement.

[F1]

A finite projective measurement has outcome weights $tr (ρ P_{b})$ , and those weights are nonnegative and sum to one (Finite projective measurements, Projective measurement outcome weights are probabilities).

[F2]

The ordered computational basis of a finite register is orthonormal, and the ordered tensor basis retains the factor order (The computational basis is orthonormal, Ordered tensor registers, their inner product, and wire permutations).

[F3]

The Dirac rank-one operator $∣ x ⟩ ⟨ y ∣$ acts by $z \mapsto ⟨ z, y ⟩_{r o o t} x$ (Dirac Notation Conversion).

[F4]

The circuit denotation composes the supplied chronological gate actions on the specified ordered wires (Finite circuit syntax and ordered wire labels, Denotational semantics of a finite layered circuit).

[F5]

The matrix of a rank-one operator $∣ x ⟩ ⟨ y ∣$ in ordered orthonormal bases is $[x] [y]^{†}$ (Dirac Notation Coordinate Identity).

[F6]

An endomorphism trace is the sum of its diagonal entries in an ordered basis (The basis-independent trace of an endomorphism of a finite-dimensional vector space).

[F7]

For real $θ$ , $∣ \exp (i θ) ∣ = 1$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F8]

The complex exponential satisfies $\exp (z + w) = \exp (z) \exp (w)$ ( $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential).

[F9]

A finite projective measurement's orthogonal projections form a POVM: each $P_{b}$ is nonnegative because $P_{b} = P_{b}^{*} = P_{b}^{2}$ gives $⟨ P_{b} v, v ⟩ = ⟨ P_{b} v, P_{b} v ⟩ \geq 0$ , and their sum is the identity. Its positive square roots are the projections themselves. The Lüders maps are $I_{b} (X) = P_{b} X P_{b}$ ; for $p_{b} = tr (ρ P_{b}) > 0$ , the conditional state is $ρ_{b} = P_{b} ρ P_{b} / p_{b}$ . The maps form an instrument by the Lüders-instrument theorem, and the displayed conditional-state formula is the projective conditional-state rule (Finite POVMs and their outcome law, Finite instruments and conditional states, The square-root Lüders maps form an instrument, A non-negative operator has a unique non-negative square root, Conditional state for a projective measurement, Non-negative and positive operators).

[F10]

Discarding the second factor contracts its matching basis index by the partial-trace rule (Partial trace over a finite tensor factor).

Proof

1.1givenF2F4F8algebra

Put $α = \exp (2 π i k s / N)$ and $β = \exp (2 π i ℓ s / N)$ . By [F8], $α β = \exp (2 π i (k + ℓ) s / N)$ . Expanding the input gives $\frac{1}{2} (∣ 00 ⟩ + β ∣ 01 ⟩ + α ∣ 10 ⟩ + α β ∣ 11 ⟩)$ . The map $C$ permutes the four orthonormal basis vectors by an involution, so it is unitary by [F2]. Its action sends this vector to $\frac{1}{2} (∣ 00 ⟩ + β ∣ 01 ⟩ + α β ∣ 10 ⟩ + α ∣ 11 ⟩)$ , in accordance with the ordered circuit semantics [F4].

2.1givenF1F3F5F6F7F9F10step 1.1algebra

The second-qubit-zero projection leaves $\frac{1}{2} (∣ 0 ⟩ + α β ∣ 1 ⟩) \otimes ∣ 0 ⟩$ . Its squared norm is $(1 + ∣ α β ∣^{2}) / 4 = 1 / 2$ , since [F7] gives $∣ α ∣ = ∣ β ∣ = 1$ . By [F3], the pure-state density is the rank-one operator; [F5] gives its coordinate matrix and [F6] its trace, so the trace of the projected rank-one state is this squared norm. [F1] identifies it with the projective outcome weight. The Lüders conditional-state rule [F9] normalizes the joint branch; its product form and the partial trace [F10] leave first-qubit state $∣ ψ_{k + ℓ} ⟩$ .

3.1givenF1F3F5F6F7F8F9F10step 1.1algebra∎

The second-qubit-one projection leaves $\frac{1}{2} (β ∣ 0 ⟩ + α ∣ 1 ⟩) \otimes ∣ 1 ⟩$ . Its squared norm is $(∣ β ∣^{2} + ∣ α ∣^{2}) / 4 = 1 / 2$ by [F7]. As in step 2.1, [F3], [F5], and [F6] identify that squared norm with the trace weight, and [F1] gives the projective outcome probability. The Lüders conditional-state rule [F9] normalizes this joint branch; [F10] discards the measured second qubit. Since $β \neq 0$ , the normalized first-qubit vector is $β / ∣ β ∣$ times $(∣ 0 ⟩ + α \overline{β} ∣ 1 ⟩) / \sqrt{2}$ ; the factor is a global phase. By [F7] and [F8], $α \overline{β} = α β^{- 1} = \exp (2 π i (k - ℓ) s / N)$ . Thus the residual ray is $∣ ψ_{k - ℓ} ⟩$ . This calculation includes $k = ℓ$ and either zero label.

Depends on

Used by

Power-of-two dihedral hidden-subgroup sieve Algorithm
Kuperberg dihedral hidden-subgroup scope and resource claim Theorem

Dependency tree · two levels

71 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

Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)