Size bound
ProvedMITMSynthesis.buildS_length_lealgorithm-analysiscircuit-synthesismeet-in-the-middlequantum-circuits
Let be a set of gates, , and let vs be a duplicate-free list of (layer, unitary) pairs enumerating . For every ,
both for the set of unitaries implementable in depth and for the list that MITM-factor builds from vs (starting from and multiplying by every element of vs).
This bound is what converts the per-iteration cost of the algorithm into a bound in terms of .
Differences from the source:
- generalization: |S_i| ≤ |V_{n,G}|^i for the set S_i → the bound for the set S_i and for the list buildS vs i that the algorithm builds; reason: the second conjunct is the source's claim for the set; the first is the same bound for the list representation used by MITM-factor
Preamble
import Mathlib import Definitions.Def_MITMSynthesis_Gate import Definitions.Def_MITMSynthesis_depthOneSet import Definitions.Def_MITMSynthesis_S import Definitions.Def_MITMSynthesis_mitmFactor
Formal statement
namespace MITMSynthesis
/-- **Size of `S_i`.** Amy–Maslov–Mosca–Roetteler, arXiv:1206.0758v3, §3, p. 6: "|S_i| ≤ |V_{n,G}|^i".
If `vs` enumerates `V_{n,G}` duplicate-free, then for every `i` both the set `S_i` of unitaries
implementable in depth `i` and the list `S_i` built by MITM-factor (`buildS vs i`) have at most
`|V_{n,G}|^i` elements. -/
theorem buildS_length_le {n : ℕ} {G : Set Gate}
(vs : List (List (Placement n) × Matrix (Q n) (Q n) ℂ)) (hvs : IsLayerEnumeration G vs)
(i : ℕ) :
(buildS vs i).val.length ≤ (depthOneSet n G).ncard ^ i ∧
(S (depthOneSet n G) i).ncard ≤ (depthOneSet n G).ncard ^ i := 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, §3, p. 6 ("As |S_i| ≤ |V_{n,G}|^i")