Lemma 2 — integer approximation: with
ProvedDepthOptQC.Synth.lemma_2circuit-complexitygate-synthesisp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-circuitsquantum-computing
Fix and . For every integer there exist nonnegative integers with
such that
The four integers are the sizes of four intervals partitioning the addresses of a uniform superposition; on them the circuit applies , so the resulting block is with , an approximate block encoding of .
Formalization Note The integers are a function ; is a natural number compared with the integer ceiling.
Differences from the source:
- encoding: nonnegative integers n₀, n₁, n₂, n₃ and an integer m ≥ ⌈log₂(2√2/ε)⌉ → n : Fin 4 → ℕ and m : ℕ with ⌈log₂(2√2/ε)⌉ ≤ (m : ℤ); reason: same instances: the ceiling is at least 2 on (0,1), so every admissible m is a natural number
Preamble
import Mathlib
Formal statement
namespace DepthOptQC.Synth
/-- **Lemma 2 (Integer Approximation)** (Vasconcelos, *Depth-Optimal Quantum Compilation*,
arXiv:2609.34659, Lemma 2, p.15). Fix `θ ∈ ℝ` and `ε ∈ (0, 1)`. For any integer
`m ≥ ⌈log₂(2√2/ε)⌉` there are nonnegative integers `n₀, n₁, n₂, n₃` with
`n₀ + n₁ + n₂ + n₃ = 2^m` (20) and
`|((n₀ − n₁) + i(n₂ − n₃))/2^m − ½ e^{iθ/2}| ≤ ε` (21).
**Formalization Note.** The four integers are `n : Fin 4 → ℕ`; `m` is a natural number, compared with
the integer ceiling `⌈log₂(2√2/ε)⌉` in `ℤ` (that ceiling is at least `2` on `(0, 1)`). -/
theorem lemma_2 (θ ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) (m : ℕ)
(hm : ⌈Real.logb 2 (2 * Real.sqrt 2 / ε)⌉ ≤ (m : ℤ)) :
∃ n : Fin 4 → ℕ, ∑ j, n j = 2 ^ m ∧
‖(((n 0 : ℂ) - n 1) + Complex.I * ((n 2 : ℂ) - n 3)) / 2 ^ m
- Complex.exp (((θ / 2 : ℝ) : ℂ) * Complex.I) / 2‖ ≤ ε := by sorry
end DepthOptQC.Synth
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Lemma 2, p.15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.