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.
Computational basis states have an extended stabilizer tableau
Statement
For and a bit string , the basis state has rows indexed by given by and for each . Their labels satisfy the extended tableau pairing conditions.
Facts & Assumptions
Given: The ordered computational basis of an -qubit register and .
Finite registers and their ordered computational bases: the ordered tensor register has the lexicographically ordered computational basis; for it is with basis .
Big-endian encoding of ordered bit strings: the first wire is the most significant bit and coordinate occupies factor position , which is Pauli wire by [F9].
Pauli group on the empty register: when , the ambient Pauli group is scalar and the empty generator list generates .
The computational basis is orthonormal: the computational basis of each factor is orthonormal.
Phase-aware stabilizer tableau: a row represents and row pairings are computed by .
Binary Pauli quotient isomorphism: a nonzero binary label cannot represent a scalar Pauli.
Pauli matrix algebra and trace identities and The Pauli matrices: on the one-qubit basis, and , and both are Hermitian involutions.
Pauli commutator is symplectic pairing: Pauli rows commute exactly when their label pairing is zero.
Phase aware n qubit pauli group: Pauli wire is tensor factor ; its and operators act on that factor.
Ordered tensor registers, their inner product, and wire permutations: elementary tensors of factor basis vectors form a basis, and their inner product is the product of factor inner products. For the space is , with .
Proof
Given: The data in the Statement.
By [F4] and [F10], for computational words , including the empty product when . Thus this basis is orthonormal and is normalized. For each , [F7] and [F9] give , so fixes . In the same basis each is a real diagonal involution and each flips bit , an involutive permutation; hence all these rows are Hermitian involutions.
For , the labels of are and of are . Therefore , which is the required pairing ; pairings within either family vanish by [F5]. By [F8], the stabilizer rows commute. Since they are involutions, every generated element is a product over a subset of the rows. A nonempty subset has nonzero label by independence and the label homomorphism [F6], so is not scalar; the empty subset gives . Thus the generated group excludes . For , the empty row families generate by [F3], and all pairing and independence conditions hold vacuously.
Sources
Aaronson–Gottesman §III, PDF pp. 3–4, gives the identity tableau for computational-basis input. De Wolf §20.1, PDF p. 185, notes that every basis state is a stabilizer state: https://arxiv.org/pdf/quant-ph/0406196; https://arxiv.org/pdf/1907.09415.
Depends on
- Phase-aware stabilizer tableau
- Phase aware n qubit pauli group
- Finite registers and their ordered computational bases
- Big-endian encoding of ordered bit strings
- The computational basis is orthonormal
- Ordered tensor registers, their inner product, and wire permutations
- The Pauli matrices
- Pauli matrix algebra and trace identities
- Binary Pauli label and quotient
- Binary Pauli quotient isomorphism
- Binary symplectic form
- Pauli commutator is symplectic pairing
Used by
Dependency tree · two levels
39 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
- Scott Aaronson and Daniel Gottesman, Improved Simulation of Stabilizer Circuits, §III (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes, §20.1 (standard reference, not scraped)