TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

Writing an N-bit output costs at least N bit operations

Statement

In an output-interface model with $N$ designated output positions, where one bit operation can write at most one position and every output position must be written, emitting an $N$ -bit classical string costs at least $N$ bit operations. This lower bound concerns the output interface; it is not a lower bound on preparing a quantum state or on producing a succinct circuit description.

Facts & Assumptions

Given: An integer $N \geq 0$ and the output-interface convention in the Statement.

[F1]

Classical output, quantum-state output, and access costs: a classical string output is a finite bit string in a declared encoding, and its cost includes every output bit written.

Proof

1.1givenF1cases

If $N = 0$ , the empty string requires no output positions and the lower bound is $0$ . If $N > 0$ , the output has $N$ distinct designated positions by [F1] and the stated interface.

2.1givenstep 1.1algebra∎

Each bit operation writes at most one position, while all $N$ positions must be written. Hence any execution that emits the string uses at least $N$ bit operations.

Depends on

Classical output, quantum-state output, and access costs

Used by

Quantum-state output does not mean an amplitude list was written Counterexample

Dependency tree · two levels

8 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

Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)