Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Vn,GV_{n,\mathcal G}Vn,G​ is closed under adjoints

Proved
MITMSynthesis.star_mem_depthOneSet

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

circuit-synthesismeet-in-the-middlequantum-circuits

Let G\mathcal GG be an instruction set, that is, a set of gates containing the inverse of each of its gates. Then for every nnn,

M∈Vn,G  ⟹  M†∈Vn,G.M \in V_{n,\mathcal G} \implies M^\dagger \in V_{n,\mathcal G}.M∈Vn,G​⟹M†∈Vn,G​.

This is the step of the proof of Lemma 1 showing that the adjoint of a depth-iii circuit is again a depth-iii circuit; it is why the inverse-closure of the instruction set is required.

Differences from the source: none.

Preamble
import Mathlib
import Definitions.Def_MITMSynthesis_Gate
import Definitions.Def_MITMSynthesis_depthOneSet
import Definitions.Def_MITMSynthesis_S
Formal statement
namespace MITMSynthesis

/-- **`V_{n,G}` is closed under `†`.** Amy–Maslov–Mosca–Roetteler, arXiv:1206.0758v3, proof of
Lemma 1, pp. 5–6: "As G is closed under inversion, U₁†, U₂†, …, U_i† ∈ V_{n,G}". If the instruction
set `G` contains the inverse of each of its gates, the adjoint of every depth-one unitary over `G`
is again a depth-one unitary over `G`. -/
theorem star_mem_depthOneSet {n : ℕ} {G : Set Gate} (hG : IsInstructionSet G)
    {M : Matrix (Q n) (Q n) ℂ} (hM : M ∈ depthOneSet n G) : star M ∈ depthOneSet n G := by sorry

end MITMSynthesis
Source
Amy, Maslov, Mosca, Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, arXiv:1206.0758v3, proof of Lemma 1, pp. 5–6 ("As G is closed under inversion, U_1†, U_2†, ..., U_i† ∈ V_{n,G}")

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