Corollary 1: necessary body order for universality
OpenQAlgorithms.Papers.Independent.Intakenext100.P38.universality_body_thresholdLet denote the number of qubits, with computational basis indexed by . Write for the unnormalized sum of distinct phase-zero Pauli words with copies of , copies of the standard , and copies of . All Lie closures, linear spans, and dimensions below are over ; commutators are .
Write for the skew-Hermitian commutant of the qubit-permuting representation of , for its total-trace-zero subalgebra, and for its derived algebra, equivalently the algebra with independently traceless multiplicity blocks. Let , , and let be any set, finite or infinite, of Hermitian permutation-equivariant operators. Assume each member is a real linear combination of Pauli words of weight at most , where weight counts nonidentity factors. If its actual real dynamical Lie algebra is universal up to a global phase, meaning , then
This is a necessary condition for arbitrary allowed generator sets; it asserts no sufficiency for those sets.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P38
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P38
open scoped BigOperators
open QAlgorithms.Papers.Independent.Support50.P30
(QnnOperator qubitPermutationMatrix PermutationEquivariant)
attribute [local instance] LieRing.ofAssociativeRing
/-- PDF p.6, Corollary 1: necessity for EVERY set of Hermitian equivariant
Pauli-degree-at-most-k generators, including infinite sets. No sufficiency for
arbitrary sets is claimed. Odd n uses k>=n-1; even n uses k=n. -/
theorem universality_body_threshold {n k : ℕ} (hn : 1 ≤ n) (hkn : k ≤ n)
(G : Set (QnnOperator n))
(hG : ∀ H ∈ G, H.IsHermitian ∧ PermutationEquivariant H ∧ H ∈ pauliDegreeSpace n k)
(hU : IsEquivariantlyUniversal (generatedSkewLie G).toSubmodule) :
(Even n → k = n) ∧ (Odd n → n - 1 ≤ k) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be natural numbers with and , and let be any set of complex matrices on the computational basis . Write for the identity and standard Pauli matrices. For nonnegative integers , let be the sum of all tensor products of factors from having exactly factors , factors , and factors , with no normalization; this sum is zero when there are no such products. For a permutation of the positions, let be the matrix sending to . Let be the real linear span of all matrices satisfying and for every , and let be the real linear span of the traceless elements of . Assume that every is Hermitian, commutes with every , and lies in the real linear span of the individual Pauli tensor products having at most nonidentity factors. Let be the smallest real Lie subalgebra of the complex matrix algebra, with bracket , containing for every , and assume
Then both implications hold: if is even, ; and if is odd, . The quantification permits and an empty , subject to all the stated hypotheses; at , the odd-case conclusion is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.