Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Abstract main construction, pinned to §2.1.2, circuit (16) and (17)

Proved
QAlgorithms.Papers.Independent.Extend50.P44.baseConstruction

by Gohan · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let N=2nN=2^nN=2n, let 2s2^s2s be the physical sparsity-register dimension, and let 2d2m=N2s2^d2^m=N2^s2d2m=N2s. Fix reversible row and column label maps, a range predicate enumerating each structural matrix position once, and unitary preparations uniform on ScS_cSc​ and SrS_rSr​ supported sparsity states. These choices precede the real data values aja_jaj​. Let DDD count the supplied table slots; padded data values are fixed to zero, and Ma=max⁡j∣aj∣>0M_a=\max_j|a_j|>0Ma​=maxj​∣aj​∣>0.

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

(⟨0∣⊗I)U(∣0⟩⊗I)=AScSr Ma.(\langle0|\otimes I)U(|0\rangle\otimes I)=\frac{A}{\sqrt{S_cS_r}\,M_a}.(⟨0∣⊗I)U(∣0⟩⊗I)=Sc​Sr​​Ma​A​.

It loads DDD data items and has s+2s+2s+2 flag qubits. Arithmetic efficiency is conditional on the supplied oracle implementations. This construction separates the matrix pattern from its numerical values.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Extend50_P44
Formal statement
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
Source
Block-encoding structured matrices for data input in quantum computing, arXiv:2302.10949v2, PDF p. 7, Abstract main construction, pinned to §2.1.2, circuit (16) and (17)
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For natural numbers n,s,d,mn,s,d,mn,s,d,m, write Jt={0,…,2t−1}J_t=\{0,\ldots,2^t-1\}Jt​={0,…,2t−1} and L=Jd×JmL=J_d\times J_mL=Jd​×Jm​. Let BBB supply d+m=s+nd+m=s+nd+m=s+n, bijections C,R:L→Js×JnC,R:L\to J_s\times J_nC,R:L→Js​×Jn​, Boolean validity vvv, nonempty slot sets Sc,SrS_c,S_rSc​,Sr​, and unitaries Hc,HrH_c,H_rHc​,Hr​ 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 a:Jd→Ra:J_d\to\mathbb Ra:Jd​→R, and let active⊆Jd\mathrm{active}\subseteq J_dactive⊆Jd​ be nonempty, with aj=0a_j=0aj​=0 for every j∉activej\notin\mathrm{active}j∈/active, and M=max⁡j∣aj∣>0M=\max_j|a_j|>0M=maxj​∣aj​∣>0. Define

Aij=∑ℓ∈L1v(ℓ)=true, R(ℓ)2=i, C(ℓ)2=j aℓ1,α=∣Sc∣∣Sr∣ M.A_{ij}=\sum_{\ell\in L} \mathbf1_{v(\ell)=\mathrm{true},\,R(\ell)_2=i,\,C(\ell)_2=j}\,a_{\ell_1}, \qquad \alpha=\sqrt{|S_c||S_r|}\,M.Aij​=ℓ∈L∑​1v(ℓ)=true,R(ℓ)2​=i,C(ℓ)2​=j​aℓ1​​,α=∣Sc​∣∣Sr​∣​M.

Let D(q)D(q)D(q) have diagonal entries qqq and off-diagonal entries −i1−q2-\mathrm i\sqrt{1-q^2}−i1−q2​. Define KKK on two Boolean flags and labels by

K((b,e),ℓ),((c,f),k)=1ℓ=k 1 e=(f if v(k) else ¬f) D(ak1/M)b,c.K_{((b,e),\ell),((c,f),k)} =\mathbf1_{\ell=k}\, \mathbf1_{\,e=(f\text{ if }v(k)\text{ else }\neg f)}\,D(a_{k_1}/M)_{b,c}.K((b,e),ℓ),((c,f),k)​=1ℓ=k​1e=(f if v(k) else ¬f)​D(ak1​​/M)b,c​.

Let PC,PRP_C,P_RPC​,PR​ implement the label bijections while preserving both flags, and let D(H)\mathcal D(H)D(H) apply HHH to the slot index while preserving the flags and system index. After regrouping indices as (((b,e),t),i)(((b,e),t),i)(((b,e),t),i), set U=D(Hr)†PRKPC†D(Hc)U=\mathcal D(H_r)^\dagger P_RKP_C^\dagger\mathcal D(H_c)U=D(Hr​)†PR​KPC†​D(Hc​). The conclusion is that UUU is unitary and

∥α[U(((false,false),0),i), (((false,false),0),j)]i,j−A∥op≤0.\left\|\alpha\bigl[U_{(((\mathrm{false},\mathrm{false}),0),i),\,(((\mathrm{false},\mathrm{false}),0),j)}\bigr]_{i,j}-A\right\|_{\mathrm{op}}\le0.​α[U(((false,false),0),i),(((false,false),0),j)​]i,j​−A​op​≤0.

Also, the sum of the one-entry loading schedule [∣active∣][|\mathrm{active}|][∣active∣] is ∣active∣|\mathrm{active}|∣active∣, and the ancilla index set of two Boolean flags and one JsJ_sJs​ slot has cardinality 2s+22^{s+2}2s+2. Entries inside active\mathrm{active}active may be zero; positivity of MMM requires at least one nonzero table entry.

Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 30, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me