TheoremStatement: 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.

QC24 Explicit State-Preparation Cost Guarantee

Statement

For an integer $n \geq 0$ , $D = 2^{n}$ , and target amplitudes supplied by the explicit normalized amplitude-table model of QC24 State Preparation Cost Model, QC24 State Preparation reads the dense table and produces an exact target ray using at most $D - 1$ variable-control rotations and at most $D$ phases. The local clean Toffoli ladder yields $O ((n + 1) D)$ bounded-arity gates and serial depth using at most $\max {n - 1, 0}$ clean work bits in addition to the data register. If an integer $b \geq 1$ specifies a dense fixed-width table with $b$ bits for each real and imaginary coordinate that decodes exactly to the input amplitudes, it contains $2 D b = Θ (D b)$ input bits; this procedure's explicit full-table preprocessing scan reads those bits. The statement assumes neither QRAM nor exact arbitrary-angle implementation in a fixed finite gate alphabet. It gives no uniform bit-time bound.

Facts & Assumptions

Given: The declared cost model, a valid dense table with $D = 2^{n}$ entries, and its fixed-width encoding when a bit representation is specified.

[F1]

The model separates table length and classical preprocessing from continuous or finite-alphabet gates, width, ancillas and error metric; an encoding with $b$ bits per real/imaginary coordinate has $2 D b$ bits when it decodes exactly to the table (QC24 State Preparation Cost Model).

[F2]

The exact procedure reads an explicit table, computes all prefix norms and phases, and uses the specified bounded-arity flag construction (QC24 State Preparation).

[F3]

The exact target ray is prepared using at most $D - 1$ prefix rotations and at most $D$ leaf phases, with $O ((n + 1) D)$ bounded-arity gates and serial depth and at most $\max {n - 1, 0}$ clean work bits (QC24 State Preparation Rotation Level Upper Bound).

Proof

Given: As in Facts & Assumptions.

1.1F2F3algebra

By [F2] the table is a finite explicit classical input, and by [F3] its prefix procedure prepares the target ray. There are $\sum_{l < n} 2^{l} = D - 1$ prefix nodes before zero-norm branches are skipped, so the circuit uses at most $D - 1$ rotations; there are at most $D$ leaf phases. The same theorem supplies the bounded-arity gate, serial-depth and workspace counts.

1.2F1F2algebra

If the exact table is supplied in the fixed-width encoding of [F1], each of $D$ entries contains $b$ bits for its real coordinate and $b$ for its imaginary coordinate, with no per-entry index because the order is fixed. The procedure reads each encoded coordinate in its full-table preprocessing scan to form subtree norms and phases, so it reads exactly $2 D b$ input bits in this bit-read model. This is an input and preprocessing charge separate from coherent gate cost; no alternate oracle or compressed-input lower bound is asserted.

2.1F1F2∎

The gate construction uses continuous-angle operations under ideal exact arithmetic. A fixed finite alphabet only supplies the separate approximation claim once its compiler hypotheses are verified; the present exact gate-count statement makes no arbitrary-angle finite-set or uniform Turing-time claim.

Depends on

Used by

LCU block-encoding construction Algorithm
Classical output, quantum-state output, and access costs Definition

Dependency tree · two levels

17 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

Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov, Synthesis of Quantum Logic Circuits (standard reference, not scraped)
John Preskill, Quantum Computation, Chapter 5, Classical and Quantum Circuits (standard reference, not scraped)