Theorem 9 — depth lower bound for channels
OpenDepthOptQC.Synth.Supplement.theorem_9lower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-circuitsquantum-information
Fix integers and . There is a constant such that the following holds uniformly for every finite alphabet of at most unitary gates, each acting on at most qubits. For , let be the least depth at which, for every , some circuit over with any number of clean ancillas and a designated output induces a channel satisfying
If no such depth exists, set . Then
The bound shows that the base mission's doubly-logarithmic bounded-width synthesis depth is asymptotically optimal.
Differences from the source:
- encoding: when no depth works →
rotationDepthis anERealinfimum whose empty value is ; reason: this represents the paper's convention without a default natural number - reading: → one positive constant chosen after but before and , with base-two logarithms; reason: this is the uniform meaning of the subscript and the logarithm base only rescales the constant
- encoding: is a set of quantum gates →
Gate.IsUnitaryis required for every member; reason: the sharedGatesyntax does not bundle the paper's standing unitarity convention
Preamble
import Definitions.Def_DepthOptQC_Synth_Supplement_CircuitModel set_option autoImplicit false
Formal statement
namespace DepthOptQC.Synth.Supplement
open QAlgorithms
/-- **Theorem 9 (Depth Lower-Bound)** — Vasconcelos, *Depth-Optimal Quantum Compilation*,
arXiv:2609.34659, p.28, Eqs. (118)–(121). Uniformly over every finite unitary gate alphabet of
cardinality at most `g` and arity at most `r`, the worst-case depth for diamond-norm approximation
of all `Rz` channels is `Ω_{g,r}(log log(1/ε))`. Arbitrarily many clean ancillas are allowed and
only the designated output is retained.
**Formalization Note.** `rotationDepth` is `+∞` when no depth works. The base-two logarithm fixes
an immaterial logarithm base. The positive constant is chosen after `g,r` but before the alphabet
and precision, which is the uniform meaning of the subscript `Ω_{g,r}`. -/
theorem theorem_9 :
∀ g r : ℕ, 1 ≤ g → 2 ≤ r → ∃ c : ℝ, 0 < c ∧
∀ G : Set Gate, G.Finite → G.ncard ≤ g → (∀ q ∈ G, q.IsUnitary) →
(∀ q ∈ G, q.arity ≤ r) → ∀ ε : ℝ, 0 < ε → ε ≤ 1 / 16 →
((c * Real.logb 2 (Real.logb 2 (1 / ε)) : ℝ) : EReal) ≤ rotationDepth G ε := by sorry
end DepthOptQC.Synth.Supplement
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Theorem 9, p.28 (PDF p.30), Eqs. (118)–(121)