Lemma 4.3.2 — the inductive subsystem lemma (corrected: and every )
ProvedBaconThesis.Universality.lemma_4_3_2lie-groupsp2o-correctedp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computingquantum-information
Let and let be a Hilbert space with subsystems, of dimension
Let be any set of unitary operators on (a gate set). Two subsystems are computationally connected when every operator with acting on is densely generated by . If the graph on whose edges are the computationally connected pairs is connected, then densely generates the special unitary group of the whole space:
where is the closure of the set of finite products of gates from .
The lemma reduces universality of a gate set on many subsystems to universality on the pairs of a connected graph; the book applies it to the controlled-not plus single-qubit gates (§4.3.2).
Differences from the source:
- correction: any number n of subsystems → 2 ≤ n; reason: for n = 1 the one-vertex graph is connected with no edge, and G = ∅ with d₁ = 2 does not densely generate SU(2) (it generates only {I})
- correction: each subsystem H_i of dimension d_i (d_i ≥ 1) → 2 ≤ d_i for every i; reason: for n = 3, d = (2, 1, 2) and G = {SU(2) ⊗ I on subsystems 1, 2} ∪ {I ⊗ SU(2) on subsystems 2, 3}, both pairs (1,2) and (2,3) are computationally connected, so the graph 1 – 2 – 3 is connected, but G generates the closed group SU(2) ⊗ SU(2), which does not contain SU(4)
- reading: subsystem structure H = ⊕_{i=1}^n H_i → the tensor product ⊗_i H_i; reason: the lemma speaks of H_a ⊗ H_b and concludes SU(∏ d_i); a direct sum has dimension Σ d_i and cannot carry SU(∏ d_i)
- reading: the gate set can densely generate SU(∏_{i=1}^n d_i) → SU(∏ d_i) ⊆ closure of the finite products of gates; reason: gates may carry global phases, so the densely generated set can be larger than SU; containment is the content of "can densely generate"
- generalization: operators on the combined Hilbert space H_a ⊗ H_b densely generate SU(d_a d_b) → every element of SU(d_a d_b) ⊗ I on the pair is densely generated by all of G; reason: the book's condition implies this one, so the book's graph is a subgraph of the Lean graph and connectedness of the book's graph gives the hypothesis
- generalization: a gate set (finite, Definition 4.3.1) → any set G of unitaries; reason: finite gate sets are a special case
- encoding: subsystems 1, …, n → Fin n (0, …, n−1); the graph via SimpleGraph.fromRel (symmetrized); reason: Lean convention; computational connectedness is symmetric, so same graph
Preamble
import Mathlib import Definitions.Def_BaconThesis_Universality_denseGen import Definitions.Def_BaconThesis_Universality_compGraph
Formal statement
namespace BaconThesis.Universality
/-- **Lemma 4.3.2 (the inductive subsystem lemma), corrected: `n ≥ 2` and every `d_i ≥ 2`.**
Bacon, *Decoherence, Control, and Symmetry in Quantum Computers*, arXiv:quant-ph/0305025v1,
§4.3.1, Lemma 4.3.2, p.52 (PDF p.69): "Suppose one is given a Hilbert space H with a subsystem
structure H = ⊕_{i=1}^n Hi, each subsystem Hi of dimension di. We say that two subsystems Ha and Hb
of dimensions da and db are computationally connected if operators on the combined Hilbert space
Ha ⊗ Hb densely generate SU(dadb). Let G be the graph of computationally connected subsystems for a
given gate set. If this graph is connected, then the gate set can densely generate
SU(∏_{i=1}^n di)."
Let `n ≥ 2` subsystems have dimensions `d_0, …, d_{n-1}`, each at least `2`, and let `G` be any set
of unitaries on `H = ⊗_i ℂ^{d_i}`. If the graph of computationally connected subsystems of `G`
(`compGraph d G`) is connected, then every element of `SU(∏_i d_i)` is a limit of finite products
of gates from `G`.
**Formalization Note.** The subsystem structure is read as a tensor product (the printed `⊕` is
inconsistent with `H_a ⊗ H_b` and with `SU(∏ d_i)`). Two hypotheses correct the printed lemma,
which is false without them: `2 ≤ n` (for `n = 1` the one-vertex graph is connected with no edge;
`G = ∅`, `d_0 = 2` generates only `{I}`), and `2 ≤ d i` (for `n = 3`, `d = (2, 1, 2)`, the gates
`SU(2) ⊗ I` on subsystems `0, 1` and `I ⊗ SU(2)` on subsystems `1, 2` make the path `0 – 1 – 2`
connected but generate only the closed group `SU(2) ⊗ SU(2) ⊉ SU(4)`). The conclusion is
containment in the densely generated set; gates may carry global phases, so equality with
`SU(∏ d_i)` is not claimed. `G` may be infinite. Subsystems are indexed from `0`. -/
theorem lemma_4_3_2 {n : ℕ} (hn : 2 ≤ n) (d : Fin n → ℕ) (hd : ∀ i, 2 ≤ d i)
(G : Set (Matrix.unitaryGroup ((i : Fin n) → Fin (d i)) ℂ))
(hG : (compGraph d G).Connected) :
(Matrix.specialUnitaryGroup ((i : Fin n) → Fin (d i)) ℂ : Set (Matrix _ _ ℂ)) ⊆
denseGen G := by sorry
end BaconThesis.Universality
Source
Bacon, Decoherence, Control, and Symmetry in Quantum Computers, arXiv:quant-ph/0305025v1, Lemma 4.3.2, p.52 (PDF p.69)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.