Exact quantum factoring, part 3 of 38 (port of OpenAI's formalization)
DefinitionOAI_QuantumFactoring_Part03Part 3 of 38 of a port of OpenAI's Lean formalization of the manuscript Exact quantum factoring over a fixed finite gate set (OpenAI, September 25, 2026). This part contains the modules TriangularAlgebra, HornerEncoding, RegisterCircuit, RegisterBasis, EncodedStates, RegisterEncoded, BooleanOracle, OracleLayout, PackedPrograms, PackedEncoding, CoherentSampling, AppendRegister, ControlledTranslation, RowNetwork.
Attribution. The code is adapted from the OpenAI "math" repository, commit adc7f1241b42e322a6451854ab7e4b4c146bf78a, directory lean/OAI/Computability/QuantumFactoring. It is © OpenAI and licensed under the Apache License 2.0; the adapted code is redistributed under the same license.
Modifications. Modules are concatenated in dependency order, with their imports replaced by the previous part. The model definitions come from the platform definition ExactQuantumFactoring, which is identical to upstream Basic.lean.
The development is split into 38 parts only so that each compiles within the platform's time limit. Together the parts supply the circuit family PhysicalTree.finalCircuit and its specification, used to prove OAI.ExactQuantumFactoring.zero_amplitude_core.
/-
Exact quantum factoring development (port of OpenAI's formalization), part 3 of 38.
Adapted from the OpenAI "math" repository (https://github.com/openai/math, commit
adc7f1241b42e322a6451854ab7e4b4c146bf78a), lean/OAI/Computability/QuantumFactoring/: TriangularAlgebra.lean, HornerEncoding.lean, RegisterCircuit.lean, RegisterBasis.lean, EncodedStates.lean, RegisterEncoded.lean, BooleanOracle.lean, OracleLayout.lean, PackedPrograms.lean, PackedEncoding.lean, CoherentSampling.lean, AppendRegister.lean, ControlledTranslation.lean, RowNetwork.lean
These files formalize the manuscript "Exact quantum factoring over a fixed finite gate set"
(OpenAI, September 25, 2026). Copyright OpenAI. Licensed under the Apache License, Version 2.0
(http://www.apache.org/licenses/LICENSE-2.0); the adapted code is distributed under the same license,
on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND.
Modifications: modules concatenated in dependency order with their import lines removed; the model
definitions (Basic.lean) come from the platform definition `ExactQuantumFactoring`, to which upstream
Basic.lean is identical; the final assembly (Main.lean) is omitted.
-/
import Mathlib
import Definitions.Def_OAI_QuantumFactoring_Part02
set_option autoImplicit false
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/TriangularAlgebra.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring.Triangular
open scoped BigOperators
lemma pathShift_prefix {A : Type*} [AddCommGroup A] {b : ℕ}
(δ : Fin b → Bits b → A) (x y : Bits b) (k : ℕ) (hk : k ≤ b) :
pathShift δ x y k hk =
∑ j : Fin k, δ (j.castLE hk) (hybrid x y (j.val+1)) := by
induction k with
| zero => simp [pathShift]
| succ k ih =>
rw [pathShift, ih (by omega), Fin.sum_univ_castSucc]
rfl
lemma pathShift_full_sum {A : Type*} [AddCommGroup A] {b : ℕ}
(δ : Fin b → Bits b → A) (x y : Bits b) :
pathShift δ x y b le_rfl = ∑ j : Fin b, δ j (hybrid x y (j.val+1)) := by
rw [pathShift_prefix]
rfl
lemma pathWeight_prefix {b : ℕ} (x y : Bits b) (k : ℕ) (hk : k ≤ b) :
pathWeight x y k hk = ∏ j : Fin k, hEntry (x (j.castLE hk)) (y (j.castLE hk)) := by
induction k with
| zero => simp [pathWeight]
| succ k ih => rw [pathWeight, ih (by omega), Fin.prod_univ_castSucc]; rfl
def dot {b : ℕ} (x y : Bits b) : ℕ := ∑ i : Fin b, (x i).toNat*(y i).toNat
lemma hEntry_pow (a c : Bool) :
hEntry a c = (-1:ℂ)^(a.toNat*c.toNat) * (Real.sqrt 2 : ℂ)⁻¹ := by
cases a <;> cases c <;> simp [hEntry, div_eq_mul_inv]
lemma pathWeight_full {b : ℕ} (x y : Bits b) :
pathWeight x y b le_rfl = (-1:ℂ)^dot x y * (Real.sqrt 2 : ℂ)⁻¹^b := by
rw [pathWeight_prefix]
simp only [hEntry_pow, Fin.castLE_refl, Finset.prod_mul_distrib,
Finset.prod_pow_eq_pow_sum, Finset.prod_const, Finset.card_univ, Fintype.card_fin]
rfl
lemma selected_evolve {A : Type*} [AddCommGroup A] [Fintype A] {b : ℕ}
(δ : Fin b → Bits b → A) (x y : Bits b) (χ : A → ℂ) :
(∑ z, star (χ z) * evolve δ x χ b le_rfl y z) =
pathWeight x y b le_rfl *
∑ z, star (χ (z+pathShift δ x y b le_rfl)) * χ z := by
simp only [evolve_full]
calc
_ = pathWeight x y b le_rfl * ∑ z, star (χ z) * χ (z-pathShift δ x y b le_rfl) := by
rw [Finset.mul_sum]
apply Finset.sum_congr rfl
intro z _
ring
_ = _ := by
congr 1
symm
simpa only [Equiv.coe_addRight, add_sub_cancel_right] using
Equiv.sum_comp (Equiv.addRight (pathShift δ x y b le_rfl))
(fun z => star (χ z) * χ (z-pathShift δ x y b le_rfl))
/-- The input word is reversed physically, while the output wire j is k_j. -/
def inputNumber {b : ℕ} (x : Bits b) : ℕ := ∑ i, 2^(b-1-i.val)*(x i).toNat
def outputNumber {b : ℕ} (y : Bits b) : ℕ := ∑ j, 2^j.val*(y j).toNat
def lowTerm {b : ℕ} (x y : Bits b) (i j : Fin b) : ℕ :=
if j.val < i.val then 2^(b-1-i.val+j.val)*(x i).toNat*(y j).toNat else 0
def highTerm {b : ℕ} (x y : Bits b) (i j : Fin b) : ℕ :=
if i.val < j.val then 2^(j.val-i.val-1)*(x i).toNat*(y j).toNat else 0
lemma productTerm {b : ℕ} (x y : Bits b) (i j : Fin b) :
(2^(b-1-i.val)*(x i).toNat) * (2^j.val*(y j).toNat) =
lowTerm x y i j +
(if i=j then 2^(b-1)*(x i).toNat*(y i).toNat else 0) +
2^b*highTerm x y i j := by
have he : (2^(b-1-i.val)*(x i).toNat) * (2^j.val*(y j).toNat) =
2^(b-1-i.val+j.val)*(x i).toNat*(y j).toNat := by rw [pow_add]; ring
rw [he]
by_cases hij : i.val < j.val
· have hn : i ≠ j := by intro h; subst j; omega
have hw : b-1-i.val+j.val = b+(j.val-i.val-1) := by have := i.isLt; omega
simp only [lowTerm, highTerm, ite_eq_right (by omega : ¬j.val < i.val), ite_eq_left hij,
ite_eq_right hn, hw, pow_add]
ring
· by_cases hji : j.val < i.val
· have hn : i ≠ j := by intro h; subst j; omega
simp [lowTerm, highTerm, hij, hji, hn]
· have heq : i=j := Fin.ext (by omega)
subst j
have hw : b-1-i.val+i.val = b-1 := by have := i.isLt; omega
simp [lowTerm, highTerm, hw]
lemma product_decomposition {b : ℕ} (x y : Bits b) :
inputNumber x * outputNumber y =
(∑ i, ∑ j, lowTerm x y i j) + 2^(b-1)*dot x y +
2^b*(∑ i, ∑ j, highTerm x y i j) := by
unfold inputNumber outputNumber
rw [Finset.sum_mul]
simp_rw [Finset.mul_sum, productTerm, Finset.sum_add_distrib]
simp only [Finset.sum_ite_eq, Finset.mem_univ, ite_true]
simp only [dot, Finset.mul_sum]
congr 2
apply Finset.sum_congr rfl
intro i _
ring
/-- One shift after H_j combines all the prescribed mutually commuting
controlled power-of-two shifts in that row. -/
def rowShift {b : ℕ} (j : Fin b) (z : Bits b) : ℕ :=
∑ i, if j.val < i.val then 2^(b-1-i.val+j.val)*(z i).toNat*(z j).toNat else 0
lemma rowShift_hybrid {b : ℕ} (x y : Bits b) (j : Fin b) :
rowShift j (hybrid x y (j.val+1)) = ∑ i, lowTerm x y i j := by
unfold rowShift
apply Finset.sum_congr rfl
intro i _
unfold lowTerm
by_cases hi : j.val < i.val
· simp [hi, hybrid, show ¬i.val < j.val+1 by omega]
· simp [hi]
lemma pathShift_rows {A : Type*} [Ring A]
{b : ℕ} (x y : Bits b) :
pathShift (fun j z => (rowShift j z : A)) x y b le_rfl =
((∑ i, ∑ j, lowTerm x y i j : ℕ) : A) := by
rw [pathShift_full_sum]
simp only [rowShift_hybrid, Nat.cast_sum]
exact Finset.sum_comm
end ExactQuantumFactoring.Triangular
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/HornerEncoding.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
namespace BitArithmetic
lemma horner_sum {b : ℕ} (e : Basis b) (k : ℕ) (hk : k ≤ b) :
horner e k hk = ∑ i : Fin k, 2^(k-1-i.val)*(e (i.castLE hk)).toNat := by
induction k with
| zero => simp [horner]
| succ k ih =>
rw [horner,ih (by omega),Fin.sum_univ_castSucc,Finset.mul_sum]
congr 1
· apply Finset.sum_congr rfl
intro i _
have he : k+1-1-i.val = (k-1-i.val)+1 := by have := i.isLt; omega
rw [show (i.castSucc : Fin (k+1)).val = i.val from rfl,he,pow_succ]
have hi : ((i.castSucc).castLE hk) = i.castLE (by omega : k ≤ b) := Fin.ext rfl
rw [hi]
ring
· simp only [Fin.val_last,Nat.add_sub_cancel,Nat.sub_self,pow_zero,one_mul]
rfl
lemma horner_full {b : ℕ} (e : Basis b) :
horner e b le_rfl = Triangular.inputNumber e := by
rw [horner_sum]
rfl
end BitArithmetic
lemma Triangular.outputNumber_value {b : ℕ} (x : Basis b) :
outputNumber x = (bitsValue x).toNat := (bitsValue_toNat x).symm
/-- The physical input word reversal is an explicit wire permutation. -/
def reverseBits (b : ℕ) : Equiv.Perm (Basis b) where
toFun x := x ∘ Fin.rev
invFun x := x ∘ Fin.rev
left_inv x := by funext i; simp
right_inv x := by funext i; simp
lemma Triangular.inputNumber_reverse {b : ℕ} (x : Basis b) :
inputNumber x = (bitsValue (reverseBits b x)).toNat := by
rw [bitsValue_toNat]
unfold inputNumber
rw [← Equiv.sum_comp (Fin.revPerm : Equiv.Perm (Fin b))]
apply Finset.sum_congr rfl
intro i _
change 2^(b-1-(b-(i.val+1)))*(x (Fin.rev i)).toNat =
2^i.val*(x (Fin.rev i)).toNat
have he : b-1-(b-(i.val+1)) = i.val := by have := i.isLt; omega
rw [he]
lemma Triangular.inputNumber_lt {b : ℕ} (x : Basis b) : inputNumber x < 2^b := by
rw [inputNumber_reverse]
exact (bitsValue _).isLt
lemma Triangular.inputNumber_bijective (b : ℕ) :
Function.Bijective (fun x : Basis b =>
(⟨inputNumber x,inputNumber_lt x⟩ : Fin (2^b))) := by
have h := (bitsEquiv b).bijective.comp (reverseBits b).bijective
have he : (fun x : Basis b => (⟨inputNumber x,inputNumber_lt x⟩ : Fin (2^b))) =
fun x => ((bitsEquiv b (reverseBits b x)).toFin) := by
funext x
apply Fin.ext
exact inputNumber_reverse x
rw [he]
exact (BitVec.equivFin (m := b)).bijective.comp h
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/RegisterCircuit.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators Kronecker
/-- A physical placement of a register uses distinct existing qubits. -/
abbrev Register (p q : ℕ) := Fin p ↪ Fin q
namespace Register
abbrev Unused {p q : ℕ} (w : Register p q) := {i : Fin q // ∀ j, w j ≠ i}
noncomputable def split {p q : ℕ} (w : Register p q) :
Basis q ≃ Basis p × (w.Unused → Bool) := by
classical
exact {
toFun := fun x => (x ∘ w, fun i => x i.val)
invFun := fun x i => if h : ∃ j, w j = i then x.1 h.choose
else x.2 ⟨i, by simpa only [not_exists] using h⟩
left_inv := by
intro x; funext i; dsimp
split_ifs with h
· simp only [h.choose_spec]
· rfl
right_inv := by
intro x; apply Prod.ext
· funext j; dsimp
have h : ∃ j', w j' = w j := ⟨j,rfl⟩
rw [dite_eq_left h]
exact congrArg x.1 (w.injective h.choose_spec)
· funext i; dsimp
rw [dite_eq_right (by simpa only [not_exists] using i.property)] }
noncomputable def liftMatrix {p q : ℕ} (w : Register p q)
(A : Matrix (Basis p) (Basis p) ℂ) : Matrix (Basis q) (Basis q) ℂ :=
Matrix.reindex w.split.symm w.split.symm
(A ⊗ₖ (1 : Matrix (w.Unused → Bool) (w.Unused → Bool) ℂ))
lemma liftMatrix_one {p q : ℕ} (w : Register p q) : w.liftMatrix 1 = 1 := by
classical
rw [liftMatrix, Matrix.one_kronecker_one]
exact map_one (Matrix.reindexAlgEquiv ℂ ℂ w.split.symm)
lemma liftMatrix_mul {p q : ℕ} (w : Register p q)
(A B : Matrix (Basis p) (Basis p) ℂ) :
w.liftMatrix (A * B) = w.liftMatrix A * w.liftMatrix B := by
classical
change (Matrix.reindexAlgEquiv ℂ ℂ w.split.symm)
((A * B) ⊗ₖ (1 : Matrix (w.Unused → Bool) (w.Unused → Bool) ℂ)) =
(Matrix.reindexAlgEquiv ℂ ℂ w.split.symm) (A ⊗ₖ 1) *
(Matrix.reindexAlgEquiv ℂ ℂ w.split.symm) (B ⊗ₖ 1)
rw [← map_mul (Matrix.reindexAlgEquiv ℂ ℂ w.split.symm)]
congr 1
rw [← Matrix.mul_kronecker_mul, Matrix.one_mul]
lemma liftMatrix_unitary {p q : ℕ} (w : Register p q)
(A : Matrix (Basis p) (Basis p) ℂ) (hA : A ∈ Matrix.unitaryGroup (Basis p) ℂ) :
w.liftMatrix A ∈ Matrix.unitaryGroup (Basis q) ℂ :=
unitary_reindex _ _ (tensor_unitary _ _ hA (one_mem _))
end Register
def Instruction.place {p q : ℕ} (w : Register p q) (o : Instruction p) : Instruction q :=
⟨o.gate, w ∘ o.wire, w.injective.comp o.distinct⟩
lemma Instruction.place_matrix {p q : ℕ} (w : Register p q) (o : Instruction p) :
(o.place w).matrix = w.liftMatrix o.matrix := by
classical
ext x y
let A := ∀ i : Fin q, (∀ j, w (o.wire j) ≠ i) → x i = y i
let B := ∀ i : Fin p, (∀ j, o.wire j ≠ i) → x (w i) = y (w i)
let C := (fun i : w.Unused => x i.val) = (fun i : w.Unused => y i.val)
have he : A ↔ B ∧ C := by
constructor
· intro h
constructor
· intro i hi
apply h (w i)
intro j hh
exact hi j (w.injective hh)
· funext i
apply h i.val
intro j
exact i.property (o.wire j)
· rintro ⟨hB,hC⟩ i hi
by_cases hh : ∃ j, w j = i
· obtain ⟨j,rfl⟩ := hh
exact hB j (fun k hk => hi k (congrArg w hk))
· exact congrFun hC ⟨i,by simpa only [not_exists] using hh⟩
change (if A then o.gate.matrix (List.ofFn (x ∘ w ∘ o.wire))
(List.ofFn (y ∘ w ∘ o.wire)) else 0) =
(if B then o.gate.matrix (List.ofFn (x ∘ w ∘ o.wire))
(List.ofFn (y ∘ w ∘ o.wire)) else 0) * if C then 1 else 0
simp only [he]
split_ifs <;> simp_all
lemma programMatrix_place {p q : ℕ} (w : Register p q) (ops : List (Instruction p)) :
programMatrix (ops.map (Instruction.place w)) = w.liftMatrix (programMatrix ops) := by
induction ops with
| nil => simp [programMatrix_nil, Register.liftMatrix_one]
| cons o ops ih =>
rw [List.map_cons, programMatrix_cons, programMatrix_cons, ih,
Instruction.place_matrix, Register.liftMatrix_mul]
/-- Tensor states in the actual physical wire order. -/
noncomputable def Register.pairState {p q : ℕ} (w : Register p q)
(v : State p) (z : (w.Unused → Bool) → ℂ) : State q :=
fun x => v (w.split x).1 * z (w.split x).2
lemma Register.liftMatrix_pairState {p q : ℕ} (w : Register p q)
(A : Matrix (Basis p) (Basis p) ℂ) (v : State p) (z : (w.Unused → Bool) → ℂ) :
(w.liftMatrix A).mulVec (w.pairState v z) = w.pairState (A.mulVec v) z := by
classical
ext x
change (∑ y, (A (w.split x).1 (w.split y).1 *
if (w.split x).2 = (w.split y).2 then 1 else 0) *
(v (w.split y).1 * z (w.split y).2)) =
(∑ u, A (w.split x).1 u * v u) * z (w.split x).2
rw [← Equiv.sum_comp w.split.symm]
simp only [Equiv.apply_symm_apply, Fintype.sum_prod_type]
simp [Finset.sum_mul, mul_assoc]
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/RegisterBasis.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
/-- Replace just one placed register, keeping every other physical wire. -/
noncomputable def Register.replace {p q : ℕ} (w : Register p q) (x : Basis q) (y : Basis p) : Basis q :=
w.split.symm (y, (w.split x).2)
lemma Register.replace_inside {p q : ℕ} (w : Register p q) (x : Basis q) (y : Basis p)
(i : Fin p) : w.replace x y (w i) = y i := by
have h := congrArg Prod.fst (w.split.apply_symm_apply (y, (w.split x).2))
exact congrFun h i
lemma Register.replace_outside {p q : ℕ} (w : Register p q) (x : Basis q) (y : Basis p)
(i : w.Unused) : w.replace x y i.val = x i.val := by
have h := congrArg Prod.snd (w.split.apply_symm_apply (y, (w.split x).2))
exact congrFun h i
lemma Register.pairState_basis {p q : ℕ} (w : Register p q) (x : Basis q) :
w.pairState (basisVector (x ∘ w)) (basisVector (w.split x).2) = basisVector x := by
classical
funext y
change (if (w.split y).1 = (w.split x).1 then (1 : ℂ) else 0) *
(if (w.split y).2 = (w.split x).2 then 1 else 0) = if y = x then 1 else 0
by_cases hy : y = x
· subst y; simp
· have hh : ¬ ((w.split y).1 = (w.split x).1 ∧ (w.split y).2 = (w.split x).2) := by
intro h; exact hy (w.split.injective (Prod.ext h.1 h.2))
rcases not_and_or.mp hh with h | h <;> simp [hy,h]
lemma Register.pairState_replace_basis {p q : ℕ} (w : Register p q) (x : Basis q) (v : Basis p) :
w.pairState (basisVector v) (basisVector (w.split x).2) = basisVector (w.replace x v) := by
have h := w.pairState_basis (w.replace x v)
have he : w.split (w.replace x v) = (v, (w.split x).2) := w.split.apply_symm_apply _
change w.pairState (basisVector (w.split (w.replace x v)).1)
(basisVector (w.split (w.replace x v)).2) = _ at h
simpa only [he] using h
lemma placed_basis {p q : ℕ} (w : Register p q) (ops : List (Instruction p))
(x : Basis q) (v : Basis p)
(h : (programMatrix ops).mulVec (basisVector (x ∘ w)) = basisVector v) :
(programMatrix (ops.map (Instruction.place w))).mulVec (basisVector x) =
basisVector (w.replace x v) := by
rw [programMatrix_place, ← w.pairState_basis x, w.liftMatrix_pairState, h,
w.pairState_replace_basis]
/-- SWAP is three named CNOT gates, not an extra primitive. -/
def swapAt {q : ℕ} (a b : Fin q) (h : a ≠ b) : List (Instruction q) :=
[cnotAt a b h, cnotAt b a h.symm, cnotAt a b h]
lemma swapAt_basis {q : ℕ} (a b : Fin q) (h : a ≠ b) (x : Basis q) :
(programMatrix (swapAt a b h)).mulVec (basisVector x) =
basisVector (x ∘ Equiv.swap a b) := by
rw [swapAt, programMatrix_cons, programMatrix_cons, programMatrix_singleton,
← Matrix.mulVec_mulVec, ← Matrix.mulVec_mulVec,
cnotAt_basis, cnotAt_basis, cnotAt_basis]
congr 1
funext i
by_cases ha : i = a
· subst i; simp only [Function.comp_apply, Function.update_self,
Function.update_of_ne h, Function.update_of_ne h.symm, Equiv.swap_apply_left]
cases x a <;> cases x b <;> rfl
· by_cases hb : i = b
· subst i; simp [Function.comp_apply, h, h.symm]
· simp [Function.comp_apply, Equiv.swap_apply_of_ne_of_ne ha hb,
Function.update_of_ne ha, Function.update_of_ne hb]
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/EncodedStates.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
/-- Embed a logical finite state in concrete basis words, including clean work. -/
noncomputable def encodeState {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (ψ : α → ℂ) : State q := by
classical
exact ∑ a, ψ a • basisVector (e a)
lemma encodeState_apply {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (ψ : α → ℂ) (x : Basis q) :
encodeState e ψ x = ∑ a, if x=e a then ψ a else 0 := by
classical
simp only [encodeState, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, basisVector]
apply Finset.sum_congr rfl
intro a _
split_ifs <;> simp
lemma encodeState_at {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (he : Function.Injective e) (ψ : α → ℂ) (a : α) :
encodeState e ψ (e a) = ψ a := by
classical
rw [encodeState_apply]
simp [he.eq_iff]
lemma encodeState_outside {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (ψ : α → ℂ) (x : Basis q) (hx : x ∉ Set.range e) :
encodeState e ψ x = 0 := by
classical
rw [encodeState_apply]
apply Finset.sum_eq_zero
intro a _
rw [ite_eq_right]
intro h
exact hx ⟨a,h.symm⟩
lemma encodeState_basis {α : Type*} [Fintype α] [DecidableEq α] {q : ℕ}
(e : α → Basis q) (a : α) : encodeState e (basisVector a) = basisVector (e a) := by
classical
simp [encodeState, basisVector, ite_smul]
lemma encodeState_add {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (ψ χ : α → ℂ) :
encodeState e (ψ+χ) = encodeState e ψ + encodeState e χ := by
classical
simp only [encodeState, Pi.add_apply, add_smul, Finset.sum_add_distrib]
lemma encodeState_smul {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (c : ℂ) (ψ : α → ℂ) :
encodeState e (c • ψ) = c • encodeState e ψ := by
classical
simp only [encodeState, Pi.smul_apply, smul_eq_mul, mul_smul, Finset.smul_sum]
lemma encodeState_sum {α β : Type*} [Fintype α] [Fintype β] {q : ℕ}
(e : α → Basis q) (ψ : β → α → ℂ) :
encodeState e (∑ b, ψ b) = ∑ b, encodeState e (ψ b) := by
classical
simp only [encodeState, Finset.sum_apply, Finset.sum_smul]
exact Finset.sum_comm
/-- A basis-level implementation law extends to every coherent superposition. -/
lemma matrix_encodeState {α β : Type*} [Fintype α] [Fintype β] {p q : ℕ}
(e : α → Basis p) (f : β → Basis q) (U : Matrix (Basis q) (Basis p) ℂ)
(V : Matrix β α ℂ)
(h : ∀ a, U.mulVec (basisVector (e a)) = encodeState f (fun b => V b a))
(ψ : α → ℂ) : U.mulVec (encodeState e ψ) = encodeState f (V.mulVec ψ) := by
classical
rw [encodeState, Matrix.mulVec_sum]
simp only [Matrix.mulVec_smul, h]
simp_rw [← encodeState_smul]
rw [← encodeState_sum]
congr 1
funext b
simp only [Finset.sum_apply, Matrix.mulVec, dotProduct]
apply Finset.sum_congr rfl
intro a _
simp only [Pi.smul_apply, smul_eq_mul]
ring
lemma matrix_encode_permutation {α : Type*} [Fintype α] [DecidableEq α] {q : ℕ}
(e : α → Basis q) (U : Matrix (Basis q) (Basis q) ℂ) (v : Equiv.Perm α)
(h : ∀ a, U.mulVec (basisVector (e a)) = basisVector (e (v a)))
(ψ : α → ℂ) : U.mulVec (encodeState e ψ) = encodeState e (ψ ∘ v.symm) := by
classical
rw [encodeState, Matrix.mulVec_sum]
simp only [Matrix.mulVec_smul, h]
unfold encodeState
simpa only [Function.comp_apply, Equiv.symm_apply_apply] using
Equiv.sum_comp v (fun a => (ψ ∘ v.symm) a • basisVector (e a))
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/RegisterEncoded.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
lemma Register.replace_injective {p q : ℕ} (w : Register p q) (x : Basis q) :
Function.Injective (w.replace x) := by
intro u v h
funext i
have hh := congrFun h (w i)
simpa only [Register.replace_inside] using hh
lemma Register.placed_basis_state {p q : ℕ} (w : Register p q)
(ops : List (Instruction p)) (x : Basis q) :
(programMatrix (ops.map (Instruction.place w))).mulVec (basisVector x) =
encodeState (w.replace x) ((programMatrix ops).mulVec (basisVector (x ∘ w))) := by
classical
rw [programMatrix_place, ← w.pairState_basis x, w.liftMatrix_pairState]
unfold encodeState
simp_rw [← w.pairState_replace_basis]
funext y
simp only [Register.pairState, Finset.sum_apply, Pi.smul_apply, smul_eq_mul,
basisVector]
simp
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/BooleanOracle.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
namespace BoolNet
/-- Only the actual trace, not unrelated output registers, must start at zero. -/
lemma program_eval_range {n k q : ℕ} (p : BoolNet n k) (h : k ≤ q) (x : Basis q)
(hfresh : ∀ i : Fin q, n ≤ i.val → i.val < k → x i = false) :
(∀ i : Fin k, (BooleanProgram.eval (p.program h) x) (i.castLE h) =
p.eval (fun j => x (j.castLE (p.input_le.trans h))) i) ∧
(∀ i : Fin q, k ≤ i.val → (BooleanProgram.eval (p.program h) x) i = x i) := by
induction p with
| input => exact ⟨fun _ => rfl, fun _ _ => rfl⟩
| @add k p o ih =>
have hk : k ≤ q := by omega
obtain ⟨hpre, hrest⟩ := ih hk (fun i hi hik => hfresh i hi (by omega))
have hy : (BooleanProgram.eval (p.program hk) x) ⟨k, by omega⟩ = false := by
rw [hrest _ (by simp)]
exact hfresh _ p.input_le (by simp)
have hv : (o.compileOp h).value (BooleanProgram.eval (p.program hk) x) =
o.eval (p.eval (fun j => x (j.castLE (p.input_le.trans hk)))) := by
rw [BoolNode.compileOp_value]
congr 1
funext i
exact hpre i
have heval : BooleanProgram.eval ((p.add o).program h) x =
Function.update (BooleanProgram.eval (p.program hk) x) ⟨k, by omega⟩
(o.eval (p.eval (fun j => x (j.castLE (p.input_le.trans hk))))) := by
simp only [program, BooleanProgram.eval, List.foldl_append, List.foldl_cons, List.foldl_nil]
change (o.compileOp h).eval (BooleanProgram.eval (p.program hk) x) = _
rw [BooleanOp.eval_fresh _ _ hy, hv]
rfl
rw [heval]
constructor
· intro i
refine Fin.lastCases ?_ (fun j => ?_) i
· rw [eval_add_last]
exact Function.update_self _ _ _
· rw [eval_add_castSucc]
rw [Function.update_of_ne (by intro he; have hh := congrArg Fin.val he; change j.val = k at hh; omega)]
exact hpre j
· intro i hi
rw [Function.update_of_ne (by intro he; have hh := congrArg Fin.val he; change i.val = k at hh; omega)]
exact hrest i (by omega)
end BoolNet
namespace BooleanNetwork
/-- Copy disjoint source wires into a separate target register, by XOR. -/
def copyPrefix {k m : ℕ} (source : Fin m → Fin k) : (t : ℕ) → t ≤ m → BooleanProgram (k+m)
| 0, _ => []
| t+1, h => copyPrefix source t (by omega) ++
[⟨Fin.natAdd k ⟨t, by omega⟩, .copy ((source ⟨t, by omega⟩).castAdd m)
(by intro he; have hh := congrArg Fin.val he; simp at hh; omega)⟩]
lemma copyPrefix_length {k m : ℕ} (source : Fin m → Fin k) (t : ℕ) (h : t ≤ m) :
(copyPrefix source t h).length = t := by
induction t with
| zero => rfl
| succ t ih => simp [copyPrefix, ih]
lemma copyPrefix_eval {k m : ℕ} (source : Fin m → Fin k) (t : ℕ) (h : t ≤ m)
(x : Basis (k+m)) (i : Fin (k+m)) :
(copyPrefix source t h).eval x i =
if hi : k ≤ i.val ∧ i.val < k+t then
Bool.xor (x i) (x ((source ⟨i.val-k, by omega⟩).castAdd m)) else x i := by
induction t generalizing i with
| zero => simp [copyPrefix, BooleanProgram.eval]
| succ t ih =>
simp only [copyPrefix, BooleanProgram.eval, List.foldl_append, List.foldl_cons, List.foldl_nil]
change (BooleanOp.copy ((source ⟨t, by omega⟩).castAdd m) _).eval
((copyPrefix source t (by omega)).eval x) i = _
by_cases hit : i.val = k+t
· have he : i = Fin.natAdd k ⟨t, Nat.lt_of_succ_le h⟩ := Fin.ext hit
subst i
rw [BooleanOp.eval_at]
simp only [BooleanOp.value]
rw [ih, ih]
simp only [Fin.val_natAdd, Fin.val_castAdd]
rw [dite_eq_right (by omega), dite_eq_right (by have := (source ⟨t, by omega⟩).isLt; omega),
dite_eq_left (by omega)]
simp
· rw [BooleanOp.eval_away _ _ (by intro he; exact hit (congrArg Fin.val he))]
rw [ih]
by_cases hn : k ≤ i.val ∧ i.val < k+t
· rw [dite_eq_left hn, dite_eq_left (by omega)]
· rw [dite_eq_right hn, dite_eq_right (by omega)]
/-- Actual fixed-gate compute/copy/uncompute, with all trace wires restored. -/
def oracle {n m : ℕ} (c : BooleanNetwork n m) : List (Instruction (c.width+m)) :=
let p := c.net.program (Nat.le_add_right c.width m)
p.compile ++ (copyPrefix c.output m le_rfl).compile ++
p.compile.reverse.map Instruction.reverse
lemma oracle_length {n m : ℕ} (c : BooleanNetwork n m) :
c.oracle.length ≤ 4*c.net.count + 2*m := by
unfold oracle
simp only [List.length_append, List.length_map, List.length_reverse]
have hp := c.net.compile_length (Nat.le_add_right c.width m)
have hc := BooleanProgram.compile_length (copyPrefix c.output m le_rfl)
rw [copyPrefix_length] at hc
omega
/-- The basis-state whose trace is zero and whose target is toggled by c(x). -/
def oracleOutput {n m : ℕ} (c : BooleanNetwork n m) (x : Basis (c.width+m)) : Basis (c.width+m) :=
fun i => if h : c.width ≤ i.val then
Bool.xor (x i) (c.eval (fun j => x (j.castLE (c.net.input_le.trans (Nat.le_add_right _ _))))
⟨i.val-c.width, by omega⟩) else x i
lemma oracle_basis {n m : ℕ} (c : BooleanNetwork n m) (x : Basis (c.width+m))
(hfresh : ∀ i : Fin (c.width+m), n ≤ i.val → i.val < c.width → x i = false) :
(programMatrix c.oracle).mulVec (basisVector x) = basisVector (c.oracleOutput x) := by
let p := c.net.program (Nat.le_add_right c.width m)
have hx := c.net.program_eval_range (Nat.le_add_right c.width m) x hfresh
have hout (i : Fin (c.width+m)) (hi : i.val < c.width) : c.oracleOutput x i = x i := by
simp only [oracleOutput, dite_eq_right (Nat.not_le.mpr hi)]
have hy := c.net.program_eval_range (Nat.le_add_right c.width m) (c.oracleOutput x)
(fun i hin hik => (hout i hik).trans (hfresh i hin hik))
have hin : (fun j : Fin n => c.oracleOutput x
(j.castLE (c.net.input_le.trans (Nat.le_add_right _ _)))) =
(fun j => x (j.castLE (c.net.input_le.trans (Nat.le_add_right _ _)))) := by
funext j
apply hout
change j.val < c.width
exact j.isLt.trans_le c.net.input_le
rw [hin] at hy
have he : (copyPrefix c.output m le_rfl).eval (p.eval x) = p.eval (c.oracleOutput x) := by
funext i
rw [copyPrefix_eval]
by_cases hi : c.width ≤ i.val
· rw [dite_eq_left ⟨hi, i.isLt⟩, hx.2 i hi, hy.2 i hi]
have hs : p.eval x ((c.output ⟨i.val-c.width, by omega⟩).castAdd m) =
c.net.eval (fun j => x (j.castLE (c.net.input_le.trans (Nat.le_add_right _ _))))
(c.output ⟨i.val-c.width, by omega⟩) := hx.1 _
rw [hs]
simp only [oracleOutput, dite_eq_left hi, eval, Function.comp_apply]
· rw [dite_eq_right (by tauto)]
have hik : i.val < c.width := by omega
exact (hx.1 ⟨i.val,hik⟩).trans (hy.1 ⟨i.val,hik⟩).symm
change (programMatrix (p.compile ++ (copyPrefix c.output m le_rfl).compile ++
p.compile.reverse.map Instruction.reverse)).mulVec (basisVector x) = _
rw [programMatrix_append, programMatrix_append, ← Matrix.mulVec_mulVec,
← Matrix.mulVec_mulVec, BooleanProgram.compile_basis, BooleanProgram.compile_basis, he,
BooleanProgram.uncompute]
end BooleanNetwork
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/OracleLayout.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring.BooleanNetwork
/-- Input, output, then zero work space; this same layout is used by the
classical subroutines inside the coherent controller. -/
def packed {n m : ℕ} (r : ℕ) (x : Basis n) (y : Basis m) : Basis (n+m+r) :=
fun i => if h : i.val < n then x ⟨i.val,h⟩
else if h' : i.val < n+m then y ⟨i.val-n,by omega⟩ else false
lemma packed_input {n m r : ℕ} (x : Basis n) (y : Basis m) (i : Fin n) :
packed r x y ⟨i.val,by omega⟩ = x i := by simp [packed, i.isLt]
lemma packed_target {n m r : ℕ} (x : Basis n) (y : Basis m) (i : Fin m) :
packed r x y ⟨n+i.val,by omega⟩ = y i := by simp [packed, i.isLt]
lemma packed_work {n m r : ℕ} (x : Basis n) (y : Basis m) (i : Fin (n+m+r))
(hi : n+m ≤ i.val) : packed r x y i = false := by
simp [packed, show ¬ i.val<n by omega, show ¬ i.val<n+m by omega]
def oracleIndex (n m width i : ℕ) : ℕ :=
if i < n then i else if i < width then n+m+(i-n) else n+(i-width)
/-- Place the oracle's retained trace after its output rather than between the
input and output. A larger reservoir of work wires is permitted. -/
def oraclePlacement {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r) :
Register (c.width+m) (n+m+r) where
toFun i := ⟨oracleIndex n m c.width i.val, by
have := c.net.width_eq
have := i.isLt
unfold oracleIndex
split_ifs <;> omega⟩
inj' := by
intro i j he
apply Fin.ext
have hh : oracleIndex n m c.width i.val = oracleIndex n m c.width j.val :=
congrArg Fin.val he
unfold oracleIndex at hh
split_ifs at hh <;> have hi := i.isLt <;> have hj := j.isLt <;>
have hn := c.net.input_le <;> omega
lemma oraclePlacement_val {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(i : Fin (c.width+m)) :
(oraclePlacement c hr i).val = oracleIndex n m c.width i.val := rfl
lemma oraclePlacement_input {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(i : Fin n) :
oraclePlacement c hr (i.castLE (c.net.input_le.trans (Nat.le_add_right _ _))) =
⟨i.val,by omega⟩ := by
apply Fin.ext
simp [oraclePlacement_val, oracleIndex, i.isLt]
lemma oraclePlacement_target {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(i : Fin m) :
oraclePlacement c hr ⟨c.width+i.val,by omega⟩ = ⟨n+i.val,by omega⟩ := by
have hn := c.net.input_le
apply Fin.ext
simp [oraclePlacement_val, oracleIndex, show ¬c.width+i.val<n by omega]
lemma oraclePlacement_work {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(i : Fin (c.width+m)) (hin : n ≤ i.val) (hiw : i.val < c.width) :
n+m ≤ (oraclePlacement c hr i).val := by
rw [oraclePlacement_val]
simp only [oracleIndex, ite_eq_right (Nat.not_lt.mpr hin), ite_eq_left hiw]
omega
def oracleOn {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r) :
List (Instruction (n+m+r)) := c.oracle.map (Instruction.place (oraclePlacement c hr))
lemma oracleOn_length {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r) :
(oracleOn c hr).length ≤ 4*c.net.count+2*m := by
simpa [oracleOn] using oracle_length c
lemma oracleOn_basis {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(x : Basis n) (y : Basis m) :
(programMatrix (oracleOn c hr)).mulVec (basisVector (packed r x y)) =
basisVector (packed r x (fun i => Bool.xor (y i) (c.eval x i))) := by
let w := oraclePlacement c hr
have hz : ∀ i : Fin (c.width+m), n ≤ i.val → i.val < c.width →
(packed r x y ∘ w) i = false := by
intro i hin hiw
exact packed_work x y _ (oraclePlacement_work c hr i hin hiw)
rw [oracleOn, placed_basis w c.oracle (packed r x y) _ (oracle_basis c _ hz)]
congr 1
have heval : (fun j : Fin n => (packed r x y ∘ w)
(j.castLE (c.net.input_le.trans (Nat.le_add_right _ _)))) = x := by
funext j
rw [Function.comp_apply, oraclePlacement_input, packed_input]
funext i
by_cases hi : ∃ j, w j = i
· obtain ⟨j,rfl⟩ := hi
rw [Register.replace_inside]
unfold oracleOutput
rw [heval]
by_cases hj : c.width ≤ j.val
· rw [dite_eq_left hj]
have hw : w j = (⟨n+(j.val-c.width),by have := j.isLt; omega⟩ : Fin (n+m+r)) := by
apply Fin.ext
simp only [w, oraclePlacement_val, oracleIndex,
ite_eq_right (show ¬j.val<n by have := c.net.input_le; omega),
ite_eq_right (Nat.not_lt.mpr hj)]
change ((packed r x y) (w j) ^^ c.eval x ⟨j.val-c.width,by omega⟩) = _
rw [hw, packed_target x y ⟨j.val-c.width,by omega⟩,
packed_target x (fun i => y i ^^ c.eval x i) ⟨j.val-c.width,by omega⟩]
· rw [dite_eq_right hj]
by_cases hn : j.val < n
· have hj' : j = (⟨j.val,hn⟩ : Fin n).castLE
(c.net.input_le.trans (Nat.le_add_right _ _)) := rfl
rw [hj', Function.comp_apply, oraclePlacement_input, packed_input, packed_input]
· rw [Function.comp_apply, packed_work x y _ (oraclePlacement_work c hr j (by omega) (by omega)),
packed_work x _ _ (oraclePlacement_work c hr j (by omega) (by omega))]
· have hout : ∀ j, w j ≠ i := by simpa only [not_exists] using hi
rw [Register.replace_outside w _ _ ⟨i,hout⟩]
have hir : n+m ≤ i.val := by
by_contra hn
by_cases hin : i.val < n
· exact hi ⟨(⟨i.val,hin⟩ : Fin n).castLE
(c.net.input_le.trans (Nat.le_add_right _ _)), by
rw [oraclePlacement_input]⟩
· exact hi ⟨⟨c.width+(i.val-n),by omega⟩, by
rw [oraclePlacement_target c hr ⟨i.val-n,by omega⟩]
apply Fin.ext; dsimp; omega⟩
rw [packed_work x y i hir, packed_work x _ i hir]
end ExactQuantumFactoring.BooleanNetwork
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/PackedPrograms.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
open BooleanNetwork
def firstRegister (n m r : ℕ) : Register n (n+m+r) where
toFun i := ⟨i.val,by omega⟩
inj' := by
intro i j h
apply Fin.ext
exact congrArg (fun t : Fin (n+m+r) => t.val) h
lemma packed_first {n m r : ℕ} (x : Basis n) (y : Basis m) :
packed r x y ∘ firstRegister n m r = x := by
funext i
exact packed_input x y i
lemma packed_injective {n m r : ℕ} (y : Basis m) :
Function.Injective (fun x : Basis n => packed r x y) := by
intro x z h
have hh := congrArg (fun t => t ∘ firstRegister n m r) h
simpa only [packed_first] using hh
lemma packed_replace_first {n m r : ℕ} (x u : Basis n) (y : Basis m) :
(firstRegister n m r).replace (packed r x y) u = packed r u y := by
funext i
by_cases hi : i.val<n
· have he : i = firstRegister n m r ⟨i.val,hi⟩ := rfl
rw [he, Register.replace_inside]
exact (packed_input u y ⟨i.val,hi⟩).symm
· have hout : ∀ j : Fin n, firstRegister n m r j ≠ i := by
intro j he
have hh := congrArg Fin.val he
change j.val = i.val at hh
omega
rw [Register.replace_outside _ _ _ ⟨i,hout⟩]
simp [packed,hi]
def firstProgram {n : ℕ} (m r : ℕ) (ops : List (Instruction n)) :
List (Instruction (n+m+r)) := ops.map (Instruction.place (firstRegister n m r))
lemma firstProgram_length {n : ℕ} (m r : ℕ) (ops : List (Instruction n)) :
(firstProgram m r ops).length = ops.length := by simp [firstProgram]
lemma firstProgram_state {n m r : ℕ} (ops : List (Instruction n)) (y : Basis m)
(ψ : State n) :
(programMatrix (firstProgram m r ops)).mulVec (encodeState (fun x => packed r x y) ψ) =
encodeState (fun x => packed r x y) ((programMatrix ops).mulVec ψ) := by
refine matrix_encodeState (fun x => packed r x y) (fun x => packed r x y)
(programMatrix (firstProgram m r ops)) (programMatrix ops) ?_ ψ
intro x
rw [firstProgram, Register.placed_basis_state, packed_first]
have he : (fun u => (firstRegister n m r).replace (packed r x y) u) =
(fun u => packed r u y) := funext (fun u => packed_replace_first x u y)
exact congrArg₂ (fun (e : Basis n → Basis (n+m+r)) (v : State n) => encodeState e v)
he (matrix_basisVector (programMatrix ops) x)
lemma firstProgram_basis {n m r : ℕ} (ops : List (Instruction n)) (y : Basis m)
(x : Basis n) :
(programMatrix (firstProgram m r ops)).mulVec (basisVector (packed r x y)) =
encodeState (fun z => packed r z y) ((programMatrix ops).mulVec (basisVector x)) := by
rw [← encodeState_basis (fun z => packed r z y) x]
exact firstProgram_state ops y _
lemma BooleanNetwork.oracleOn_state {n m r : ℕ} (c : BooleanNetwork n m)
(hr : c.net.count ≤ r) (ψ : State n) :
(programMatrix (oracleOn c hr)).mulVec
(encodeState (fun x => packed r x (fun _ => false)) ψ) =
encodeState (fun x => packed r x (c.eval x)) ψ := by
classical
rw [encodeState, Matrix.mulVec_sum]
simp only [Matrix.mulVec_smul, oracleOn_basis, Bool.false_xor]
rfl
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/PackedEncoding.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring.BooleanNetwork
open scoped BigOperators
lemma packed_injective {n m r : ℕ} :
Function.Injective (fun xy : Basis n × Basis m => packed r xy.1 xy.2) := by
intro x y h
apply Prod.ext
· funext i
have hh := congrFun h (⟨i.val,by omega⟩ : Fin (n+m+r))
simpa only [packed_input] using hh
· funext i
have hh := congrFun h (⟨n+i.val,by omega⟩ : Fin (n+m+r))
simpa only [packed_target] using hh
lemma packed_update_input {n m r : ℕ} (x : Basis n) (y : Basis m) (j : Fin n) (c : Bool) :
Function.update (packed r x y) (⟨j.val,by omega⟩ : Fin (n+m+r)) c =
packed r (Function.update x j c) y := by
funext i
by_cases hi : i.val=j.val
· have he : i = (⟨j.val,by omega⟩ : Fin (n+m+r)) := Fin.ext hi
simp only [he, Function.update_self, packed_input]
· rw [Function.update_of_ne (by intro h; exact hi (congrArg Fin.val h))]
unfold packed
split_ifs with hn hm
· rw [Function.update_of_ne]
intro h; exact hi (congrArg Fin.val h)
· rfl
· rfl
lemma packed_update_target {n m r : ℕ} (x : Basis n) (y : Basis m) (j : Fin m) (c : Bool) :
Function.update (packed r x y) (⟨n+j.val,by omega⟩ : Fin (n+m+r)) c =
packed r x (Function.update y j c) := by
funext i
by_cases hi : i.val=n+j.val
· have he : i = (⟨n+j.val,by omega⟩ : Fin (n+m+r)) := Fin.ext hi
simp only [he, Function.update_self, packed_target]
· rw [Function.update_of_ne (by intro h; exact hi (congrArg Fin.val h))]
unfold packed
split_ifs with hn hm
· rfl
· rw [Function.update_of_ne]
intro h
have hh := congrArg Fin.val h
dsimp at hh
omega
· rfl
lemma append_update_left {p b : ℕ} (d : Basis p) (z : Basis b) (j : Fin p) (c : Bool) :
Function.update (Fin.append d z) (j.castAdd b) c = Fin.append (Function.update d j c) z := by
funext i
refine Fin.addCases (fun k => ?_) (fun k => ?_) i
· by_cases hk : k = j
· subst k; simp
· rw [Function.update_of_ne (by intro h; apply hk; apply Fin.ext; exact congrArg (fun i : Fin (p+b) => i.val) h),
Fin.append_left, Fin.append_left, Function.update_of_ne hk]
· rw [Function.update_of_ne (by intro h; have hh := congrArg Fin.val h; simp at hh; omega),
Fin.append_right, Fin.append_right]
/-- Taking an adjoint and reading a basis outcome implements exactly the
correlation with the prepared state, without an idealized projection gate. -/
lemma encoded_adjoint_test {α : Type*} [Fintype α] {q : ℕ}
(e : α → Basis q) (he : Function.Injective e)
(U : Matrix (Basis q) (Basis q) ℂ) (v : Basis q) (χ ψ : α → ℂ)
(h : U.mulVec (basisVector v) = encodeState e χ) :
U.conjTranspose.mulVec (encodeState e ψ) v = ∑ a, star (χ a)*ψ a := by
classical
rw [encodeState, Matrix.mulVec_sum]
simp only [Matrix.mulVec_smul, Finset.sum_apply, Pi.smul_apply, smul_eq_mul,
matrix_basisVector, Matrix.conjTranspose_apply]
rw [matrix_basisVector] at h
apply Finset.sum_congr rfl
intro a _
have ha := congrFun h (e a)
rw [encodeState_at e he] at ha
rw [ha]
ring
end ExactQuantumFactoring.BooleanNetwork
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/CoherentSampling.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
open BooleanNetwork
lemma packed_eq_iff {n m r : ℕ} (x z : Basis n) (y u : Basis m) :
packed r x y = packed r z u ↔ x=z ∧ y=u := by
constructor
· intro h
have hh := BooleanNetwork.packed_injective (n := n) (m := m) (r := r)
(a₁ := (x,y)) (a₂ := (z,u)) h
exact ⟨congrArg Prod.fst hh,congrArg Prod.snd hh⟩
· rintro ⟨rfl,rfl⟩
rfl
lemma encoded_packed_coordinate {n m r : ℕ} (y u : Basis m) (ψ : State n)
(z : Basis n) :
encodeState (fun x => packed r x y) ψ (packed r z u) = if u=y then ψ z else 0 := by
classical
rw [encodeState_apply]
simp only [packed_eq_iff]
by_cases hu : u=y
· simp [hu]
· simp [hu]
/-- Retain the modular value register while interfering the exponent register;
no copy of the exponent or hidden measurement is inserted. -/
def sampleProgram {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(ops : List (Instruction n)) : List (Instruction (n+m+r)) :=
oracleOn c hr ++ firstProgram m r ops
lemma sampleProgram_length {n m r : ℕ} (c : BooleanNetwork n m) (hr : c.net.count ≤ r)
(ops : List (Instruction n)) :
(sampleProgram c hr ops).length ≤ 4*c.net.count+2*m+ops.length := by
have h := oracleOn_length c hr
simp only [sampleProgram,List.length_append,firstProgram_length]
omega
lemma sampleProgram_amplitude {n m r : ℕ} (c : BooleanNetwork n m)
(hr : c.net.count ≤ r) (ops : List (Instruction n)) (ψ : State n)
(z : Basis n) (u : Basis m) :
(programMatrix (sampleProgram c hr ops)).mulVec
(encodeState (fun x => packed r x (fun _ => false)) ψ) (packed r z u) =
∑ x, if c.eval x=u then programMatrix ops z x * ψ x else 0 := by
classical
rw [sampleProgram,programMatrix_append,← Matrix.mulVec_mulVec,oracleOn_state]
rw [encodeState,Matrix.mulVec_sum]
simp_rw [Matrix.mulVec_smul,firstProgram_basis]
simp only [Finset.sum_apply,Pi.smul_apply,smul_eq_mul,encoded_packed_coordinate,
matrix_basisVector]
apply Finset.sum_congr rfl
intro x _
by_cases h : c.eval x=u
· simp only [h,ite_true]
ring
· simp only [h,ite_false,show u ≠ c.eval x from Ne.symm h,mul_zero]
/-- Coherent sampling on an explicitly encoded logical subspace. Inactive
quantum registers stay present; normalization need not be inferred by analogy
with a stochastic oracle. -/
lemma sampleProgram_encoded_amplitude {α : Type*} [Fintype α]
{n m r : ℕ} (e : α → Basis n) (c : BooleanNetwork n m)
(hr : c.net.count ≤ r) (ops : List (Instruction n)) (ψ : α → ℂ)
(z : Basis n) (u : Basis m) :
(programMatrix (sampleProgram c hr ops)).mulVec
(encodeState (fun x => packed r (e x) (fun _ => false)) ψ) (packed r z u) =
∑ x, if c.eval (e x)=u then programMatrix ops z (e x) * ψ x else 0 := by
classical
rw [sampleProgram,programMatrix_append,← Matrix.mulVec_mulVec]
rw [encodeState,Matrix.mulVec_sum]
simp only [Matrix.mulVec_smul,oracleOn_basis,Bool.false_xor]
rw [Matrix.mulVec_sum]
simp_rw [Matrix.mulVec_smul,firstProgram_basis]
simp only [Finset.sum_apply,Pi.smul_apply,smul_eq_mul,encoded_packed_coordinate,
matrix_basisVector]
apply Finset.sum_congr rfl
intro x _
by_cases h : c.eval (e x)=u
· simp only [h,ite_true]
ring
· simp only [h,ite_false,show u ≠ c.eval (e x) from Ne.symm h,mul_zero]
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/AppendRegister.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open scoped BigOperators
def rightRegister (p q : ℕ) : Register q (p+q) := ⟨Fin.natAdd p, Fin.natAdd_injective q p⟩
lemma append_rightRegister {p q : ℕ} (x : Basis p) (y : Basis q) :
Fin.append x y ∘ rightRegister p q = y := by
funext i
exact Fin.append_right _ _ i
lemma append_right_injective {p q : ℕ} (x : Basis p) :
Function.Injective (Fin.append x : Basis q → Basis (p+q)) := by
intro y z h
have hh := congrArg (fun v => v ∘ rightRegister p q) h
simpa only [append_rightRegister] using hh
lemma append_replace_right {p q : ℕ} (x : Basis p) (y z : Basis q) :
(rightRegister p q).replace (Fin.append x y) z = Fin.append x z := by
funext i
refine Fin.addCases (fun j => ?_) (fun j => ?_) i
· have hj : ∀ k, rightRegister p q k ≠ j.castAdd q := by
intro k h
have hh := congrArg Fin.val h
change p+k.val=j.val at hh
have := j.isLt
omega
rw [Register.replace_outside _ _ _ ⟨j.castAdd q,hj⟩]
simp only [Fin.append_left]
· change (rightRegister p q).replace (Fin.append x y) z (rightRegister p q j) = _
rw [Register.replace_inside,Fin.append_right]
def rightProgram {q : ℕ} (p : ℕ) (ops : List (Instruction q)) :
List (Instruction (p+q)) := ops.map (Instruction.place (rightRegister p q))
lemma rightProgram_basis {p q : ℕ} (ops : List (Instruction q)) (x : Basis p) (y : Basis q) :
(programMatrix (rightProgram p ops)).mulVec (basisVector (Fin.append x y)) =
encodeState (Fin.append x) ((programMatrix ops).mulVec (basisVector y)) := by
rw [rightProgram,Register.placed_basis_state,append_rightRegister]
congr 1
funext z
exact append_replace_right x y z
lemma rightProgram_entry {p q : ℕ} (ops : List (Instruction q)) (x : Basis p) (y z : Basis q) :
programMatrix (rightProgram p ops) (Fin.append x z) (Fin.append x y) =
programMatrix ops z y := by
have hh := congrFun (rightProgram_basis ops x y) (Fin.append x z)
simpa only [encodeState_at _ (append_right_injective x),matrix_basisVector] using hh
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/ControlledTranslation.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring
open BooleanNetwork
namespace ControlledTranslation
def dataPart {p b : ℕ} (x : Basis (p+b)) : Basis p := fun i => x (i.castAdd b)
def phasePart {p b : ℕ} (x : Basis (p+b)) : Basis b := fun i => x (Fin.natAdd p i)
def addInput {p b : ℕ} (δ : BooleanNetwork p b) : BooleanNetwork (p+b) (b+b) :=
(select (Fin.natAdd p)).pair ((select (fun i => i.castAdd b)).comp δ)
def forward {p b : ℕ} (δ : BooleanNetwork p b) : BooleanNetwork (p+b) (p+b) :=
(select (fun i => i.castAdd b)).pair ((addInput δ).comp (BitArithmetic.add b))
def backward {p b : ℕ} (δ : BooleanNetwork p b) : BooleanNetwork (p+b) (p+b) :=
(select (fun i => i.castAdd b)).pair ((addInput δ).comp (BitArithmetic.sub b))
def translate {p b : ℕ} (δ : Basis p → BitVec b) (x : Basis (p+b)) : Basis (p+b) :=
Fin.append (dataPart x) (fun i => (bitsValue (phasePart x) + δ (dataPart x)).getLsbD i.val)
def untranslate {p b : ℕ} (δ : Basis p → BitVec b) (x : Basis (p+b)) : Basis (p+b) :=
Fin.append (dataPart x) (fun i => (bitsValue (phasePart x) - δ (dataPart x)).getLsbD i.val)
lemma input_words {p b : ℕ} (δ : BooleanNetwork p b) (x : Basis (p+b)) :
BitArithmetic.leftWord ((addInput δ).eval x) = bitsValue (phasePart x) ∧
BitArithmetic.rightWord ((addInput δ).eval x) = bitsValue (δ.eval (dataPart x)) := by
simp only [addInput, eval_pair, eval_comp, eval_select, BitArithmetic.leftWord,
BitArithmetic.rightWord, Function.comp_apply, Fin.append_left, Fin.append_right]
exact ⟨rfl,rfl⟩
lemma forward_correct {p b : ℕ} (δ : BooleanNetwork p b) (x : Basis (p+b)) :
(forward δ).eval x = translate (fun d => bitsValue (δ.eval d)) x := by
rw [forward, eval_pair, eval_comp]
unfold translate
congr 1
funext i
rw [BitArithmetic.add_correct, (input_words δ x).1, (input_words δ x).2]
lemma backward_correct {p b : ℕ} (δ : BooleanNetwork p b) (x : Basis (p+b)) :
(backward δ).eval x = untranslate (fun d => bitsValue (δ.eval d)) x := by
rw [backward, eval_pair, eval_comp]
unfold untranslate
congr 1
funext i
rw [BitArithmetic.sub_correct, (input_words δ x).1, (input_words δ x).2]
@[simp] lemma dataPart_append {p b : ℕ} (d : Basis p) (z : Basis b) :
dataPart (Fin.append d z) = d := by funext i; simp [dataPart]
@[simp] lemma phasePart_append {p b : ℕ} (d : Basis p) (z : Basis b) :
phasePart (Fin.append d z) = z := by funext i; simp [phasePart]
lemma untranslate_translate {p b : ℕ} (δ : Basis p → BitVec b) (x : Basis (p+b)) :
untranslate δ (translate δ x) = x := by
simp only [untranslate, translate, dataPart_append, phasePart_append, bitsValue_bits,
BitVec.add_sub_cancel, bitsValue_bit]
exact Fin.append_castAdd_natAdd
lemma translate_untranslate {p b : ℕ} (δ : Basis p → BitVec b) (x : Basis (p+b)) :
translate δ (untranslate δ x) = x := by
simp only [untranslate, translate, dataPart_append, phasePart_append, bitsValue_bits,
BitVec.sub_add_cancel, bitsValue_bit]
exact Fin.append_castAdd_natAdd
lemma forward_backward {p b : ℕ} (δ : BooleanNetwork p b) (x : Basis (p+b)) :
(backward δ).eval ((forward δ).eval x) = x := by
rw [backward_correct, forward_correct, untranslate_translate]
lemma forward_count {p b : ℕ} (δ : BooleanNetwork p b) :
(forward δ).net.count ≤ δ.net.count+86*b+6 := by
simp only [forward, addInput, count_pair, count_comp, count_select, Nat.zero_add]
have := BitArithmetic.add_count b
omega
lemma backward_count {p b : ℕ} (δ : BooleanNetwork p b) :
(backward δ).net.count ≤ δ.net.count+158*b+6 := by
simp only [backward, addInput, count_pair, count_comp, count_select, Nat.zero_add]
have := BitArithmetic.sub_count b
omega
end ControlledTranslation
end ExactQuantumFactoring
end
end OAI
-- ===== Adapted from lean/OAI/Computability/QuantumFactoring/RowNetwork.lean =====
namespace OAI
section
open scoped BigOperators
namespace ExactQuantumFactoring.Triangular
open scoped BigOperators
open BooleanNetwork
def rowIndex {b : ℕ} (j e : Fin b) : Fin b :=
⟨(b-1+j.val-e.val)%b, Nat.mod_lt _ (by have := j.isLt; omega)⟩
lemma rowIndex_val {b : ℕ} (j e : Fin b) (h : j.val ≤ e.val) :
(rowIndex j e).val = b-1+j.val-e.val := by
apply Nat.mod_eq_of_lt
have := j.isLt
omega
/-- Combining one triangular row is just a bit permutation and masked ANDs;
no arbitrary phase or exponentially large truth table is present. -/
def rowNetwork {b : ℕ} (j : Fin b) : BooleanNetwork b b :=
vector (fun e => if j.val ≤ e.val ∧ e.val < b-1 then
(bit (rowIndex j e)).band (bit j)
else constant false)
lemma rowNetwork_count {b : ℕ} (j : Fin b) : (rowNetwork j).net.count = b := by
rw [rowNetwork, count_vector]
have h : ∀ e : Fin b, (if j.val ≤ e.val ∧ e.val < b-1 then
(bit (rowIndex j e)).band (bit j)
else constant false).net.count = 1 := by
intro e
by_cases he : j.val ≤ e.val ∧ e.val < b-1
· rw [ite_eq_left he]; simp
· rw [ite_eq_right he]; rfl
simp only [h, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, mul_one]
lemma rowNetwork_bit {b : ℕ} (j e : Fin b) (z : Bits b) :
(rowNetwork j).eval z e = if j.val ≤ e.val ∧ e.val < b-1 then
z (rowIndex j e) && z j else false := by
rw [rowNetwork, eval_vector]
split_ifs <;> simp_all
lemma rowNetwork_number {b : ℕ} (j : Fin b) (z : Bits b) :
(bitsValue ((rowNetwork j).eval z)).toNat = rowShift j z := by
classical
rw [bitsValue_toNat]
unfold rowShift
simp_rw [rowNetwork_bit]
have hand (a c : Bool) : (a && c).toNat = a.toNat*c.toNat := by
cases a <;> cases c <;> rfl
simp only [apply_ite Bool.toNat, Bool.toNat_false, mul_ite, mul_zero, hand, ← mul_assoc]
rw [← Finset.sum_filter, ← Finset.sum_filter]
apply Finset.sum_bij (fun e _ => rowIndex j e)
· intro e he
have h := (Finset.mem_filter.mp he).2
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
rw [rowIndex_val j e h.1]
omega
· intro e he f hf hef
have h₁ := (Finset.mem_filter.mp he).2
have h₂ := (Finset.mem_filter.mp hf).2
have hv := congrArg Fin.val hef
rw [rowIndex_val j e h₁.1, rowIndex_val j f h₂.1] at hv
exact Fin.ext (by omega)
· intro i hi
have h := (Finset.mem_filter.mp hi).2
let e : Fin b := ⟨b-1-i.val+j.val,by have := i.isLt; omega⟩
have he : j.val ≤ e.val ∧ e.val < b-1 := by dsimp [e]; have := i.isLt; omega
refine ⟨e, Finset.mem_filter.mpr ⟨Finset.mem_univ _,he⟩, ?_⟩
apply Fin.ext
rw [rowIndex_val j e he.1]
dsimp [e]
have := i.isLt
omega
· intro e he
have h := (Finset.mem_filter.mp he).2
rw [rowIndex_val j e h.1]
have hw : b-1-(b-1+j.val-e.val)+j.val = e.val := by
have := e.isLt
omega
rw [hw]
end ExactQuantumFactoring.Triangular
end
end OAI