§8, unnumbered: number of bounded-denominator operators
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.operator_countFor and , let be the set of distinct unitary -qubit matrices for which is a denominator exponent, meaning has entries in . The set is finite and
Matrices are counted with absolute phase retained. The exponent need not be least, so these are nested sets as increases. Taking logarithms yields the source's information-size interpretation for positive . This is a count of operators, not a lower bound on the complexity of every individual operator.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Section 8, PDF p.7: finite number of distinct operators with a valid denominator k. -/
theorem operator_count (n k : ℕ) (positive : 1 ≤ n) :
Finite (boundedOperators n k) ∧
2 ^ (2 ^ (n - 1) * k) ≤ Nat.card (boundedOperators n k) ∧
Nat.card (boundedOperators n k) ≤ 2 ^ (4 ^ n * (4 + 2 * k)) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number and every natural number , let , let , and let be the set of unitary complex matrices indexed by the -bit strings such that for every pair of indices . Then is finite and its cardinality satisfies
The exponent need not be the least exponent with this property. The statement includes , when the lower bound is , and makes no assertion for .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.