Lemma 1 — meet in the middle:
ProvedMITMSynthesis.lemma1circuit-synthesismeet-in-the-middlequantum-circuits
Let be an instruction set (closed under inverses), , and let be the set of unitaries implementable in depth over . For every unitary and every , there is a circuit over of depth implementing if and only if
that is, iff there are and with .
This is the observation behind the algorithm: circuits of depth can be found by generating only circuits of depth at most and looking for a collision.
Formalization Note and 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