Abstract main construction, pinned to §2.1.2, circuit (16) and (17)
ProvedQAlgorithms.Papers.Independent.Extend50.P44.baseConstructionLet , let be the physical sparsity-register dimension, and let . Fix reversible row and column label maps, a range predicate enumerating each structural matrix position once, and unitary preparations uniform on and supported sparsity states. These choices precede the real data values . Let count the supplied table slots; padded data values are fixed to zero, and .
The circuit (16), consisting of column uncomputation, one multiplexed RX data loader, range deletion and row computation between the two preparations, is unitary and satisfies
It loads data items and has flag qubits. Arithmetic efficiency is conditional on the supplied oracle implementations. This construction separates the matrix pattern from its numerical values.
import Definitions.Def_QAlgorithms_Papers_Independent_Extend50_P44
noncomputable section
namespace QAlgorithms.Papers.Independent.Extend50.P44
open scoped BigOperators ComplexConjugate Matrix
open QAlgorithms.Papers.Independent.Frontier18.P11 (complexMatrix)
open QAlgorithms.Papers.Independent.Information100.P34 (permutationMatrix)
open QAlgorithms.Papers.Independent.Next46.P21 (tCount)
variable {n s d m : ℕ}
/-- PDF pp.1,6-7, (16)-(17): full base construction for padded arithmetic labels.
No claim of efficient arithmetic is made without its implementation hypothesis. -/
theorem baseConstruction (B : Scheme n s d m) (a : Fin (2 ^ d) → ℝ)
(active : Finset (Fin (2 ^ d))) (hactive : active.Nonempty)
(hpadding : ∀ j, j ∉ active → a j = 0)
(ha : 0 < tableMax a) :
QAlgorithms.IsBlockEncoding ((false, false), 0) (B.baseCircuit a)
(B.baseAlpha a) 0 (B.matrix a) ∧
loadingCost (baseLoadingSchedule active.card) = active.card ∧
Fintype.card ((Bool × Bool) × Fin (2 ^ s)) = 2 ^ (s + 2) := by sorry
end QAlgorithms.Papers.Independent.Extend50.P44
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For natural numbers , write and . Let supply , bijections , Boolean validity , nonempty slot sets , and unitaries whose first columns are uniform positive amplitudes on those sets and zero elsewhere; valid labels map into the corresponding slot sets, and their column and row system positions jointly determine them uniquely. Let , and let be nonempty, with for every , and . Define
Let have diagonal entries and off-diagonal entries . Define on two Boolean flags and labels by
Let implement the label bijections while preserving both flags, and let apply to the slot index while preserving the flags and system index. After regrouping indices as , set . The conclusion is that is unitary and
Also, the sum of the one-entry loading schedule is , and the ancilla index set of two Boolean flags and one slot has cardinality . Entries inside may be zero; positivity of requires at least one nonzero table entry.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.