Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — meet in the middle: U∈Sl  ⟺  S⌊l/2⌋†U∩S⌈l/2⌉≠∅U\in S_l \iff S^\dagger_{\lfloor l/2\rfloor}U\cap S_{\lceil l/2\rceil}\neq\emptysetU∈Sl​⟺S⌊l/2⌋†​U∩S⌈l/2⌉​=∅

Proved
MITMSynthesis.lemma1

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 (closed under inverses), n∈Nn \in \mathbb Nn∈N, and let Si⊆U(2n)S_i \subseteq U(2^n)Si​⊆U(2n) be the set of unitaries implementable in depth iii over G\mathcal GG. For every unitary U∈U(2n)U \in U(2^n)U∈U(2n) and every l∈Nl \in \mathbb Nl∈N, there is a circuit over G\mathcal GG of depth lll implementing UUU if and only if

S⌊l/2⌋† U  ∩  S⌈l/2⌉≠∅,S^\dagger_{\lfloor l/2\rfloor}\, U \;\cap\; S_{\lceil l/2\rceil} \neq \emptyset,S⌊l/2⌋†​U∩S⌈l/2⌉​=∅,

that is, iff there are X∈S⌊l/2⌋X \in S_{\lfloor l/2\rfloor}X∈S⌊l/2⌋​ and W∈S⌈l/2⌉W \in S_{\lceil l/2\rceil}W∈S⌈l/2⌉​ with W=X†UW = X^\dagger UW=X†U.

This is the observation behind the algorithm: circuits of depth lll can be found by generating only circuits of depth at most ⌈l/2⌉\lceil l/2\rceil⌈l/2⌉ and looking for a collision.

Formalization Note ⌈l/2⌉\lceil l/2\rceil⌈l/2⌉ and ⌊l/2⌋\lfloor l/2\rfloor⌊l/2⌋ are the natural-number quotients (l + 1) / 2 and l / 2.

Differences from the source:

  • reading: there exists a circuit over G of depth l implementing U → U ∈ S_l, a product of exactly l elements of V_{n,G}; reason: the lemma's own S_i are the unitaries implementable in depth i, built on p. 6 as S_0 = {I}, S_i = V_{n,G}S_{i−1}
  • encoding: S†{⌊l/2⌋}U ∩ S{⌈l/2⌉} ≠ ∅ → ∃ W ∈ S_{(l+1)/2}, ∃ X ∈ S_{l/2}, W = X† U; reason: the same set membership written out; ⌈l/2⌉ = (l+1)/2 and ⌊l/2⌋ = l/2 in ℕ
Preamble
import Mathlib
import Definitions.Def_MITMSynthesis_Gate
import Definitions.Def_MITMSynthesis_depthOneSet
import Definitions.Def_MITMSynthesis_S
Formal statement
namespace MITMSynthesis

/-- **Lemma 1 (meet in the middle).** Amy–Maslov–Mosca–Roetteler, arXiv:1206.0758v3, Lemma 1,
p. 5. Let `S_i` be the set of unitaries implementable in depth `i` over `G`. A unitary `U` is
implementable by a circuit over `G` of depth `l` iff `S_{⌊l/2⌋}† U ∩ S_{⌈l/2⌉} ≠ ∅`, i.e. iff some
`W ∈ S_{⌈l/2⌉}` equals `X† U` for some `X ∈ S_{⌊l/2⌋}`.
In ℕ, `⌈l/2⌉ = (l + 1) / 2` and `⌊l/2⌋ = l / 2`. -/
theorem lemma1 {n : ℕ} {G : Set Gate} (hG : IsInstructionSet G) (l : ℕ)
    (U : Matrix (Q n) (Q n) ℂ) (hU : U ∈ Matrix.unitaryGroup (Q n) ℂ) :
    U ∈ S (depthOneSet n G) l ↔
      ∃ W ∈ S (depthOneSet n G) ((l + 1) / 2), ∃ X ∈ S (depthOneSet n G) (l / 2),
        W = star X * U := 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, Lemma 1, p. 5

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