Theorem 14 — bounded-arity real decision simulation
OpenDepthOptQC.Synth.Supplement.theorem_14computational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationreal-quantum-circuits
Uniform constants and work for both QUNC and its Fan-Out variant QUNCf. If is a depth- circuit and bounds its gate count and width, then for every there is a QRNC circuit —or QRNCf in the Fan-Out case—such that
for every input . Its depth is at most
and its size is at most .
In contrast to Theorem 12, the size is polynomial in rather than in .
Differences from the source:
- reading: and → uniform witnesses , using the positive scales and ; reason: explicit uniform asymptotics without weakening the precision dependence
- encoding: two separately stated model pairs → one Boolean index selecting QUNC/QRNC or QUNCf/QRNCf; reason: retains both clauses exactly
Preamble
import Definitions.Def_DepthOptQC_Synth_Supplement_CircuitModel set_option autoImplicit false
Formal statement
namespace DepthOptQC.Synth.Supplement
open QAlgorithms
/-- **Theorem 14 (Bounded-Arity Real Decision Simulation)** — Vasconcelos,
arXiv:2609.34659, p.65, Eq. (313). QUNC decision circuits have QRNC simulations with additive
`O(log log(s/ε))` depth and size polynomial in `s` and `log(1/ε)`; the same holds for the Fan-Out
pair QUNCf/QRNCf.
**Formalization Note.** The Boolean `withFanout` states both source clauses without dropping either.
`precLog ε=log₂(2/ε)` and `loglogScale` give positive uniform representatives of the two printed
asymptotic logarithms. -/
theorem theorem_14 :
∃ K : ℝ, 0 < K ∧ ∃ k : ℕ,
∀ (withFanout : Bool) (n d s : ℕ)
(C : DecisionCircuit (if withFanout then quncfGateSet else quncGateSet) n),
2 ≤ s → C.depth = d → C.size ≤ s → C.width ≤ s →
∀ ε : ℝ, 0 < ε → ε < 1 / 2 →
∃ Ctilde : DecisionCircuit (if withFanout then qrncfGateSet else qrncGateSet) n,
(Ctilde.depth : ℝ) ≤
K * ((d : ℝ) + loglogScale ((s : ℝ) / ε)) ∧
(Ctilde.size : ℝ) ≤ K * ((s : ℝ) + DepthOptQC.Synth.precLog ε) ^ k ∧
∀ x : Qubits n, |Ctilde.acceptance x - C.acceptance x| ≤ ε := by sorry
end DepthOptQC.Synth.Supplement
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Theorem 14, p.65 (PDF p.67), Eq. (313)