CounterexampleConstruction: Literature-sourcedVerification: 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.

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

Statement refuted

An efficient circuit that outputs an $n$ -qubit state necessarily outputs its full classical amplitude list in polynomial time.

Facts & Assumptions

Given: An integer $n \geq 1$ , the computational basis on $n$ qubits, and the full-list output convention in the Statement.

[F1]

Classical output, quantum-state output, and access costs: a quantum-state output and a classical bit-string output are distinct types; writing a classical string charges its output positions.

[F2]

Writing an N-bit output costs at least N bit operations: writing an $N$ -bit string in the declared output interface costs at least $N$ bit operations.

Counterexample

1.1givenF1construct

Use the quantum-state output type from [F1] and the empty circuit. It leaves $∣ 0^{n} ⟩$ unchanged using zero gate occurrences. The full amplitude vector has $N = 2^{n}$ entries, one equal to $1$ and the remaining $2^{n} - 1$ equal to $0$ ; encode these entries by one bit each.

2.1step 1.1F2algebra∎

The explicit list has $2^{n}$ designated output bits, so [F2] gives at least $2^{n}$ bit operations to write it. The empty circuit has zero gate occurrences, so the state output does not entail a polynomial-time amplitude-list output.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)