Lemma 1, preliminary claim: iff
ProvedMITMSynthesis.star_mem_S_iffcircuit-synthesismeet-in-the-middlequantum-circuits
Let be an instruction set (closed under inverses), , and let be the set of -qubit unitaries implementable in depth over . For every and every matrix ,
This is the claim proved at the start of the proof of Lemma 1: the set of depth- unitaries is closed under taking adjoints.
Differences from the source:
- reading: U can be implemented in depth i over G → U ∈ S_i, a product of exactly i elements of V_{n,G}; reason: the paper's S_i ("the set of all unitaries implementable in depth i") is built as S_0 = {I}, S_i = V_{n,G}S_{i−1} on p. 6, i.e. products of exactly i elements
Preamble
import Mathlib import Definitions.Def_MITMSynthesis_Gate import Definitions.Def_MITMSynthesis_depthOneSet import Definitions.Def_MITMSynthesis_S
Formal statement
namespace MITMSynthesis
/-- **Lemma 1, preliminary claim.** Amy–Maslov–Mosca–Roetteler, arXiv:1206.0758v3, proof of
Lemma 1, p. 5: "U ∈ S_i† = {U† | U ∈ S_i} if and only if U can be implemented in depth i over G."
For an instruction set `G` (closed under inverses) and every depth `i`, `U ∈ S_i†` iff `U ∈ S_i`. -/
theorem star_mem_S_iff {n : ℕ} {G : Set Gate} (hG : IsInstructionSet G) (i : ℕ)
(U : Matrix (Q n) (Q n) ℂ) :
U ∈ star '' S (depthOneSet n G) i ↔ U ∈ S (depthOneSet n G) 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, proof of Lemma 1, p. 5 ("U ∈ S_i† = {U†|U ∈ S_i} if and only if U can be implemented in depth i over G")