Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Resetting a register of a product state factors out its squared norm

Proved
OPI.lawP_resets

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

lean-formalizationquantum-algorithmstwo-fold-opi-construction

Programs here are oracle-free adaptive quantum programs over {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT} on NNN qubits, with ccc bits of classical memory and out\mathit{out}out output bits. For a program PPP, an event EEE on outcomes, an (unnormalized) pure state fff and a memory content mem\mathit{mem}mem, lawP(P,E,f,mem)\mathrm{lawP}(P,E,f,\mathit{mem})lawP(P,E,f,mem) is the probability weight with which PPP, started from ∣f⟩⟨f∣|f\rangle\langle f|∣f⟩⟨f∣, halts with an outcome in EEE. It is linear in the density, so it scales with ∥f∥2\|f\|^2∥f∥2. The program resetsxs(P)\mathrm{resets}_{xs}(P)resetsxs​(P) re-initializes each qubit of the list xsxsxs to ∣0⟩|0\rangle∣0⟩ and then runs PPP.

Statement. Let xsxsxs be a list of distinct qubits, AAA an amplitude function on bit strings of length ∣xs∣|xs|∣xs∣, and φ\varphiφ any vector on NNN qubits. Consider the product state f(y)=A(y∣xs) φ(y with xs cleared)f(y)=A(y|_{xs})\,\varphi(y\text{ with }xs\text{ cleared})f(y)=A(y∣xs​)φ(y with xs cleared), i.e. AAA on the register xsxsxs times φ\varphiφ on the rest. Then

lawP(resetsxs(P),E,f,mem)=(∑v∈{0,1}∣xs∣∣A(v)∣2)⋅lawP(P,E,φ∣xs=0,mem),\mathrm{lawP}\big(\mathrm{resets}_{xs}(P),E,f,\mathit{mem}\big)=\Big(\sum_{v\in\{0,1\}^{|xs|}}|A(v)|^2\Big)\cdot\mathrm{lawP}\big(P,E,\varphi|_{xs=0},\mathit{mem}\big),lawP(resetsxs​(P),E,f,mem)=(v∈{0,1}∣xs∣∑​∣A(v)∣2)⋅lawP(P,E,φ∣xs=0​,mem),

where φ∣xs=0\varphi|_{xs=0}φ∣xs=0​ is φ\varphiφ restricted to the configurations in which every qubit of xsxsxs is 000.

So resetting a register in a product state leaves the rest untouched and multiplies the law by the squared norm of the discarded factor. It is used when a rejected trial resets the system before retrying, and when a repeat-until-success attempt is reset.

Preamble
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI
open QAlgorithms QAlgorithms.OPI Matrix
open scoped ComplexConjugate
variable {N c out : ℕ}
Formal statement
theorem OPI.lawP_resets (xs : List (Fin N)) (hnd : xs.Nodup) (P : Prog N c out)
    (event : Option (Fin out → Bool) → Prop) (A : List Bool → ℂ) (φ : Qubits N → ℂ)
    (mem : Fin c → Bool) :
    lawP (resets xs P) event (fun y => A (xs.map y) * φ (clr xs y)) mem =
      patSum xs.length A *
        lawP P event (fun y => if ∀ a ∈ xs, y a = false then φ y else 0) mem := by sorry
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/Rus.lean#L173-L217

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